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

kombinatoriikka

#1

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.


sulki #2

avasi #3

#4

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}


#5

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}).

#6

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