Viikkotehtävä: osajoukkojen summien jaollisuus (viikko 50/2018)

Viikkotehtävä

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

Tehtävä

Selvitä joukon \{\,1,2,\dots,2000\,\} niiden osajoukkojen lukumäärä, joiden sisältämien lukujen summa on viidellä jaollinen.

Alla on esitetty ratkaisuni tehtävään. Kirjoittanen jossain kohtaa joululomaa blogipostauksen, jossa käsittelen tarkemmin tätä tehtävää motivaatioiden näkökulmasta sekä muita lineaarisiin rekursioyhtälöihin liittyviä väitteitä.

Vastaus: \frac{2^{402} + 2^{2000}}{5}

Ratkaisu:

Tutkitaan yleisesti joukon \{1, 2, \ldots , 5n\} kuvatunlaisten osajoukkojen määrää. Merkitään tätä suureella a_n. Merkitään vielä niiden osajoukkojen määrää, joiden alkioiden summa on 1 (mod \ 5) suurella b_n. Määritellään vastaavasti c_n, d_n, e_n.

Lemma 1. b_n = e_n ja c_n = d_n kaikilla n.

Todistus: Valitaan jokin osajoukko, jonka alkioiden summa on 1 (mod \ 5). Tämän osajoukon komplementin alkioiden summa on 4 (mod \ 5). Tästä saadaan helppo bijektio tällaisten osajoukkojen välille, joten b_n = e_n kaikilla n. Vastaavasti c_n = d_n kaikilla n.

Lemma 2. a_1 = 8, b_1 = c_1 = 6.

Todistus. Suora lasku.

Lisäksi voidaan ajatella, että a_0 = 1, koska tyhjällä joukolla on osajoukko, joka on tyhjä, eli sen alkioiden summa on 0. Vastaavasti b_0 = c_0 = 0.

Muodostetaan sitten rekursiokaavat lukujonoille.

Lemma 3. a_{n+1} = 8a_n + 12b_n + 12c_n

Todistus. Valitaan jokin joukon \{1, 2, \ldots , 5n+5\} osajoukko. Tutkitaan tämän osajoukon sitä osaa, joka leikkaa joukkoa \{6, 7, \ldots , 5n + 5\}. Tämän osan alkioiden summa voi olla 0, 1, 2, 3, tai 4 mod 5. Näitä vastaavien mahdollisuuksien määrä on a_n, b_n, c_n, c_n, b_n. Joukkoa \{1, 2, 3, 4, 5\} leikkaavan osuuden alkioiden summalle mahdollisuuksien määrät on a_1, b_1, c_1, c_1, b_1. Siis
a_{n+1} = a_1a_n + b_1b_n + c_1c_n + c_1c_n + b_1b_n = 8a_n + 12b_n +12c_n.

Vastaavasti saadaan rekursiot b_{n+1} = 6a_n + 14b_n + 12c_n ja c_{n+1} = 6a_n + 12b_n + 14c_n.

Lemma 4. b_n = c_n kaikilla n.

Todistus. Edellisen nojalla b_{n+1} - c_{n+1} = 2(b_n - c_n). Helppo induktio todistaa väitteen.

Siis saadaan rekursioyhtälöt

a_{n+1} = 8a_n + 24b_n ja b_{n+1} = 6a_n + 26b_n.

Lemma 5. a_{n+2} = 34a_{n+1} - 64a_n

Todistus. Käyttäen annettuja yhtälöitä saadaan

a_{n+2} - 34a_{n+1} = 8a_{n+1} + 24b_{n+1} - 34a_{n+1} = 24b_{n+1} - 26a_{n+1} = 24(6a_n + 26b_n) - 26(8a_n + 24b_n) = -64a_n

Tämä osoittaa väitteen.

Tämä on lineaarinen rekursioyhtälö, jolle saadaan helposti yleinen muoto. Karakteristisen polynomin juuret ovat 2 ja 32, ja saadaan lopulta

a_n = \frac{2^{n+2} + 2^{5n}}{5}

Tästä saadaan a_{400} = \frac{2^{402} + 2^{2000}}{5}

1 tykkäys

Vaihtoehtoinen ratkaisu: tarkastellaan polynomia

P(x) = (1+x)(1+x^2)\dots(1+x^{2000}).

Kun polynomi kerrotaan auki mutta ei vielä sievennetä yhdistämällä termejä, termien x^{a_1+a_2+\dots+a_m} ja osajoukkojen \{\,a_1,a_2,\dots,a_m\,\} välillä on bijektio. Halutaan siis summata niiden termien kertoimet, joiden eksponentti on viiden monikerta.

Olkoon kompleksiluku \xi=e^{2\pi/5}. Silloin \xi^5=1 ja 1+\xi+\xi^2+\xi^3+\xi^4=0, koska summattavat ovat säännöllisen viisikulmion kärkipisteet. Siten tehtävän summa on

S = \frac15 \sum_{j=1}^5 P(\xi^j).

Jos nimittäin termi on muotoa c x^{5m}, sen kontribuutio summaan on c(\xi^{5m}+\xi^{2\cdot5m}+\xi^{3\cdot5m}+\xi^{4\cdot5m}+\xi^{5\cdot5m})=5c, ja jos muotoa cx^{5m+k} (1\le k\le 4), kontribuutio on c(\xi^{5m+k}+\xi^{2\cdot5m+2k}+\xi^{3\cdot5m+3k}+\xi^{4\cdot5m+4k}+\xi^{5\cdot5m+5k})=c(1+\xi+\xi^2+\xi^3+\xi^4)=0.

Luvut \xi,\xi^2,\xi^3,\xi^4 ja \xi^5 ovat polynomin Q(x)=x^5-1 juuret eli

Q(x) = (x-\xi)(x-\xi^2)(x-\xi^3)(x-\xi^4)(x-\xi^5).

Koska Q(-1)=-2, on

\begin{split} -2 = (-1-\xi)(-1-\xi^2)(-1-\xi^3)(-1-\xi^4)(-1-\xi^5) \\ = -(1+\xi)(1+\xi^2)(1+\xi^3)(1+\xi^4)(1+\xi^5), \end{split}

joten P(\xi)=2^{400}. Samoin P(\xi^j)=2^{400}, kun 2\le j\le 4, mutta P(\xi^5)=P(1)=2^{2000}. Siis

S = \frac15(4\cdot 2^{400}+2^{2000}) = \frac15(2^{402}+2^{2000}).

Mainittu blogipostaus näyttää ilmestyneen: Lineaariset rekursiot. Siinä on paljon lisää ajattelemisen aihetta rekursioyhtälöistä.