brandt je lampje al?
Opgave - IMO 2008 dag 2 vraag 2
$n,k$ zijn natuurlijke getallen zodat $k\ge n$ en $2|k-n.$
We hebben $2n$ lampen geordend van $1$ tot $2n.$
Elke lamp kan aan of uit zijn. In het begin zijn alle
lampen uit. We bekijken rijtjes van handelingen: bij elke handeling wordt ofwel een lamp die aan is
uit gedaan, ofwel een lamp die uit is aan gedaan.
Het aantal manieren bestaande uit $k$ stappen om alle lampen van $1$ tot $n$ te doen branden en de andere gedoofd te laten, noemen we $N.$
( de lampen van $n+1$ tot $2n$ mogen aan zijn geweest, maar zijn bij het einde uit)
Het aantal manieren die behoren tot $N$, maar waarbij de lampen $n+1$ tot $2n$ allen gedurende de $k$ stappen gedoofd bleven, noemen we $M.$
Bepaal de verhouding $\frac{N}{M}.$
- login om te reageren
Oplossing
Zij $S=\{(a_1, a_2, \dots, a_n)\in \mathbb{Z}^n| \text{ Alle $a_i$ zijn positief, oneven en hun som is $k$}\}$
Voor alle $A=(a_1,\dots, a_n)\in S$ associëren we $T_A=\{(b_1, b_2, \dots, b_n)\in \mathbb{Z}^n| \text{ Alle $b_i$ zijn even en er geldt $0\le b_i < a_i$ voor alle $i$}\}$
We bewijzen eerst het volgende lemma:
Lemma: Zij $A\in S$. We hebben de volgende identiteit:
$$2^n\sum_{B\in T_A}\prod_{i=1}^n{a_i\choose b_i}=2^k$$
Bewijs: We beschouwen $2^n$ verzamelingen $T^0_A, T^1_A, T^2_A,\dots T^{2^n}_A$ van $n$-tupels. Er zijn $2^n$ binaire strings van lengte $n$, we associëren elke verzameling aan zo'n string waarbij de $i$-de bit (0 of 1) van die string de pariteit van $b_i$ bepaald (even/oneven), en $0\le b_i\le a_i$. (merk op $T^0_A=T_A$). Dan bevatten al deze verzamelingen uiteraard evenveel elementen (er zijn evenveel oneven getallen van $0$ tot $a_i$ als er even getallen in die range liggen) en omdat geldt dat ${n \choose k}={n \choose n-k}$ vinden we dat
\begin{align}2^n\sum_{B\in T_A}\prod_{i=1}^n{a_i\choose b_i}&=\sum_{k=1}^{2^n}\sum_{B\in T^k_A}\prod_{i=1}^n{a_i\choose b_i}\\
&=\sum_{0\le b_i \le a_i}\prod_{i=1}^n{a_i\choose b_i}\\
&=\prod_{i=1}^n\sum_{i=0}^{a_i}{a_i\choose i}\\
&=\prod_{i=1}^n2^{a_i}=2^{\sum_{i=1}^na_i}\\
&=2^k \end{align}
We gaan nu over naar het eigenlijke bewijs. We zien gemakkelijk in dat $M=\sum_{A\in S}{k \choose a_1,a_2,\cdots, a_n}$ door $a_i$ te interpreteren als het aantal keer dat lampje $i$ aan/uit ging. (hierbij is ${k \choose a_1,a_2,\cdots, a_n}=\frac{k!}{a_1!a_2!\cdots a_n!}$ )
Waaruit volgt dat
\begin{align} 2^{k-n}M&=\sum_{A\in S}\sum_{B\in T_A}\prod_{i=1}^n{a_i\choose b_i}{k \choose a_1,a_2,\cdots, a_n}\tag{lemma}\\
&=\sum_{A\in S, B\in T_A}{k \choose b_1,b_2,\cdots, b_n, c_1, c_2,\cdots, c_n}\end{align}
Met $c_i=a_i-b_i$.
En uiteindelijk, het is niet moeilijk in te zien dat deze laatste som gelijk is aan $N$: zij $c_i$ het aantal keer dat lampje $i$ aan/uit gaat (dit is oneven), en $b_i$ het aantal keer dat lampje $n+i$ verandert (even) en de claim volgt uit $b_1+b_2+\dots+b_n+c_1+\dots+c_n=k$.
Conclusie: \begin{equation}\boxed{\frac{N}{M}=2^{k-n}}\end{equation}
QED