Problem B. 5145. (January 2021)

B. 5145. Show that there are \(\displaystyle \binom{n+1}{2k+1}\) different strings of zeros and ones of length \(\displaystyle n\) in which it occurs exactly \(\displaystyle k\) times that a \(\displaystyle 0\) is followed by a \(\displaystyle 1\).

(Problem from a qualifying competition in England for the Olympiad)

(4 pont)

Deadline expired on February 15, 2021.

Sorry, the solution is available only in Hungarian. Google translation

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

Statistics:

79 students sent a solution.
4 points:	61 students.
3 points:	9 students.
2 points:	4 students.
1 point:	1 student.
0 point:	3 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, January 2021