Viikkotehtävä: pienten kokonaislukujen määrä (viikko 40/2018)

kombinatoriikka

#1

Viikkotehtävä

Vastausaikaa su 7.10.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Olkoon k positiivinen kokonaisluku. Laske niiden kokonaislukukolmikoiden (x,y,z) lukumäärä, joille

\begin{cases} &|x| \le k,\quad &|y| \le k,\quad &|z| \le k,\\ &|x-y| \le k,\quad &|y-z| \le k,\quad &|z-x| \le k. \end{cases}

#2

#3

#4

Onko kellään ratkaisua tähän tehtävään?


#5

En ole keksinyt parempaa ratkaisua kuin seuraava aika tylsä tapaustarkastelu. Laskettavana on

S(k) = \sum_{x=-k}^{k} \sum_{y} \sum_{z} 1,

missä jälkimmäisten summien rajat ovat vähän turhan monimutkaisia kirjoittaa ala- ja yläindekseiksi: y:n alaraja on \max(-k,x-k) ja yläraja \min(k,x+k), z:n alaraja on \max(-k,x-k,y-k) ja yläraja \min(k,x+k,y+k). Jaetaan tämä kuuteen eri osasummaan, joille S(k) on osasummien summa ja joille nämä summausrajat muuttuvat helpommiksi:

\begin{cases} S_{0xy}(k), & 0\le x\le y, &y-k\le z\le k;\\ S_{x0y}(k), & x<0\le y, &y-k\le z\le x+k;\\ S_{xy0}(k), & x\le y<0, &-k\le z\le x+k;\\ S_{0yx}(k), & 0\le y< x, &x-k\le z\le k;\\ S_{y0x}(k), & y<0\le x, &x-k\le z\le y+k;\\ S_{yx0}(k), & y<x<0, &-k\le z\le y+k. \end{cases}

Sitten käännetään kampea ja jauhetaan:

\begin{align} S_{0xy}(k) &= \sum_{x=0}^{k} \sum_{y=x}^{k} \sum_{z=y-k}^{k} 1 \\ &= \sum_{x=0}^{k} \sum_{y=x}^{k} (1+2k-y) \\ &= \sum_{x=0}^{k} \left[ (1+k-x)(1+2k) - \frac12[k(k+1)] + \frac12[x(x-1)] \right] \\ &= \frac12 \sum_{x=0}^{k} \left[ 2(1+k-x)(1+2k) - k(k+1) + x(x-1) \right]\\ &= \frac12 \sum_{x=0}^{k} \left[ (1+k)[2(1+2k)-k] - (3+4k)x + x^2 \right]\\ &= \frac12 \sum_{x=0}^{k} \left[ (1+k)(2+3k) - (3+4k)x + x^2 \right] \\ &= \frac12\left[ (1+k)^2(2+3k) - \frac{(3+4k)k(k+1)}{2} + \frac{k(k+1)(2k+1)}{6} \right] \\ &= \frac{1+k}{12}\left[ 6(1+k)(2+3k) - 3k(3+4k) + k(2k+1) \right] \\ &= \frac{1+k}{12}\left( 12 + 30k + 18k^2 - 9k - 12k^2 + 2k^2 + k \right)\\ &= \frac{1+k}{12}( 12 + 22k + 8k^2 ) = \frac{(1+k)(2+k)(3+4k)}{6}. \end{align}

Tässä on huomionarvoista ainakin se, että \sum_{t=a}^b c=(1+b-a)c, kun c on vakio summattavan muuttujan suhteen, ja tunnetut kaavat \sum_{t=0}^n t = n(n+1)/2, \sum_{t=0}^n t^2 = n(n+1)(2n+1)/6. Muuten välivaiheissa lähinnä kerrottiin lausekkeita auki, siirreltiin termejä yhteen ja etsittiin yhteisiä tekijöitä. Jätetään seuraavista laskuista vähän näitä välivaiheita pois.

\begin{align} S_{x0y}(k) &= \sum_{x=-k}^{-1} \sum_{y=0}^{x+k} \sum_{z=y-k}^{x+k} 1 = \sum_{x=-k}^{-1} \sum_{y=0}^{x+k} (1+2k+x-y) \\ &= \sum_{x=-k}^{-1} \left[ (1+k+x)(1+2k+x) - \frac12 (x+k)(1+x+k) \right] = \frac13 k(1+k)(1+2k). \\ S_{xy0}(k) &= \sum_{x=-k}^{-1} \sum_{y=x}^{-1} \sum_{z=-k}^{x+k} 1 = \sum_{x=-k}^{-1} \sum_{y=x}^{-1} (1+2k+x) \\ &= \sum_{x=-k}^{-1} -x(1+2k+x) = \frac13 k(1+k)(1+2k) \\ S_{0yx}(k) &= \sum_{y=0}^{k} \sum_{x=y+1}^{k} \sum_{z=x-k}^{k} 1 = \sum_{y=0}^{k} \sum_{x=y+1}^{k} (1+2k-x) \\ &= \sum_{y=0}^{k} \left[ (k-y)(1+2k) - \frac12 k(1+k) + \frac12 y(1+y) \right]\\ &= \sum_{y=0}^{k} \frac12 \left[ k(1+3k) - y(1+4k) +y^2 \right] = \frac13 k(1+k)( 1 +2k ) \\ S_{y0x}(k) &= \sum_{x=0}^{k} \sum_{y=x-k}^{-1} \sum_{z=x-k}^{y+k} 1 = \sum_{x=0}^{k} \sum_{y=x-k}^{-1} (1+2k+y-x) \\ &= \sum_{x=0}^{k} \left[ (k-x)(1+2k-x) - \frac12 (k-x)(1+k-x) \right] = \frac13 k(1+k)(1+2k) \\ S_{yx0}(k) &= \sum_{y=-k}^{-1} \sum_{x=y+1}^{-1} \sum_{z=-k}^{y+k} 1 = \sum_{y=-k}^{-1} \sum_{x=y+1}^{-1} (1+y+2k) \\ &= \sum_{y=-k}^{-1} -(1+y)(1+y+2k) = -k(1+2k) +k(1+k)^2 - \frac16 k(1+k)(1+2k)\\ %= \frac{1}{6} k( 4k^2 - 3k - 1 ) &= \frac{1}{6} k(k-1)(1+4k) \end{align}

Yhteensä summa on siis

\begin{multline} S(k) = \frac16 (1+k)(2+k)(3+4k) + \frac43 k(1+k)(1+2k) + \frac16 k(k-1)(1+4k)\\ = 4k^3 + 6k^2 + 4k + 1 = (k+1)^4 - k^4. \end{multline}

#6

Minulla on muiden kiireiden takia vielä vastausten lukeminen kesken, mutta ainakin jollakulla vaikutti olevan pitkällisen tapaustarkastelun jälkeen kombinatorinen argumentti, jolla samaan kaavaan olisi määrä päästä lyhyemmin. Täytyyhän tähän jokin näppärä bijektio olla.


#7

Ratkaisu viikon 40 viikkotehtävään.pdf (74,5 Kt)
Siinä ratkaisuni. Alku, eli miten aluksi sain selville vastauksen, ei ole mielestäni yhtä pelottavan näköinen kuin jks:n mallivastauksessa, vaikka se onkin varmaan yhtä vaikea ymmärtää. Kun tiesi oikean vastauksen oli sitten helpompaa keksiä lyhyt ja mukava perustelu, joka löytyy ratkaisun lopusta.