A B. 5145. feladat (2021. január)

B. 5145. Mutassuk meg, hogy azoknak az \(\displaystyle n\) hosszúságú nullákból és egyesekből álló sorozatoknak a száma, amelyekben pontosan \(\displaystyle k\)-szor fordul elő, hogy \(\displaystyle 0\) után \(\displaystyle 1\) következik, éppen \(\displaystyle \binom{n+1}{2k+1}\).

(Angol olimpiai válogatóverseny feladata)

(4 pont)

A beküldési határidő 2021. február 15-én LEJÁRT.

Megoldás. A 0-1-sorozatokat úgy fogjuk megadni, hogy megmondjuk mely elemek után történik váltás. Ha például a sorozat \(\displaystyle a_1,a_2,\dots,a_n\), akkor \(\displaystyle a_i\)-nél akkor történik váltás, ha \(\displaystyle a_i\ne a_{i+1}\), vagyis ha \(\displaystyle a_i\) és \(\displaystyle a_{i+1}\) közül az egyik 0, a másik 1. A váltások helye azonban még nem határozza meg egyértelműen a sorozatot, hiszen nem tudjuk, hogy az 0-val vagy 1-gyel kezdődik. Ráadásul a váltások száma még \(\displaystyle a_1\) ismeretében is kétféle lehet, hiszen a legutolsó, \(\displaystyle k\)-adik 0-ról 1-re váltás után lehet, hogy még visszavált 0-ra, lehet, hogy nem. Ezen a két kisebb problémán segíthetünk, ha a sorozatot kiegészítjük egy 0-adik elemmel, \(\displaystyle a_0=1\)-gyel és egy \(\displaystyle (n+1)\)-edikkel, \(\displaystyle a_{n+1}=0\)-val. Ily módon az \(\displaystyle a_0,a_1,\dots,a_n,a_{n+1}\) sorozatban is ugyanannyi 0-ról 1-re váltás lesz, mint az \(\displaystyle a_1,\dots,a_n\) sorozatban. Ha a \(\displaystyle 0\)-ról 1-re váltások száma \(\displaystyle k\), akkor a bővített sorozatban összesen \(\displaystyle 2k+1\) váltás lesz, hiszen az első váltás 1-ről 0-ra történik, az utolsó úgyszintén, közben pedig felváltva vannak a 0-ról 1-re és az 1-ről 0-ra váltások.

Figyelembe véve, hogy \(\displaystyle a_0=1\), a váltások helye már egyértelműen meghatározza a sorozatot, így legfeljebb \(\displaystyle \binom{n+1}{2k+1}\) ilyen sorozat lehet (hiszen \(\displaystyle a_{n+1}\)-nél nem lehet váltás). Az \(\displaystyle \{a_0,a_1,\dots,a_n\}\) halmaz minden \(\displaystyle 2k+1\) elemű részhalmaza elő is állhat, mint a váltások halmaza, a megfelelő \(\displaystyle a_0,a_1,\dots,a_{n+1}\) sorozatot úgy kapjuk, hogy \(\displaystyle a_0=1\), majd ezután \(\displaystyle i>0\)-ra rekurzívan \(\displaystyle a_i=a_{i-1}\), ha \(\displaystyle a_{i-1}\)-nél nincs váltás és \(\displaystyle a_i=1-a_{i-1}\), ha \(\displaystyle a_{i-1}\)-nél van váltás. Mivel a váltások száma (\(\displaystyle 2k+1\)) páratlan, ezért valóban \(\displaystyle a_{n+1}=0\) lesz. A korábbiak alapján a 0-ról 1-re váltások mind az \(\displaystyle a_1,\dots,a_n\) részen helyezkednek el, és számuk \(\displaystyle k\).

Tehát a megfelelő sorozatok száma pontosan \(\displaystyle \binom{n+1}{2k+1}\).

Statisztika:

79 dolgozat érkezett.
4 pontot kapott:	61 versenyző.
3 pontot kapott:	9 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	3 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2021. januári matematika feladatai