A B. 4957. feladat (2018. május)

B. 4957. Egy pozitív egészekből álló halmazt nevezzünk tyű-de-jónak, ha a számok között nincs kettő, melyek különbsége 2. Hány tyű-de-jó részhalmaza van az \(\displaystyle \{1, 2, 3,\ldots, 10\}\) halmaznak?

Javasolta: Róka Sándor (Nyíregyháza)

(3 pont)

A beküldési határidő 2018. június 11-én LEJÁRT.

Megoldás. Ha \(\displaystyle A\subseteq\{1;2;\dots;10\}\) tyű-de-jó, akkor természetesen \(\displaystyle B:=A\cap\{1;3;5;7;9\}\) és \(\displaystyle C:=A\cap\{2;4;6;8;10\}\) is tyű-de-jók. Ez fordítva is igaz: ha \(\displaystyle B\subseteq \{1;3;5;7;9\}\) és \(\displaystyle C\subseteq\{2;4;6;8;10\}\) tyű-de-jók, akkor \(\displaystyle A=B\cup C\) is tyű-de-jó, és különböző tyű-de-jó \(\displaystyle (B,C)\) párokból különböző tyű-de-jó \(\displaystyle A=B\cup C\)-t kapunk.

Számoljuk meg, hány tyű-de-jó részhalmaza választható ki \(\displaystyle \{1;3;5;7;9\}\)-nek. Ha az 5-öt kiválasztjuk, akkor a 3-at és a 7-et nem szabad. Az 1-ről és a 9-ről viszont egymástól függetlenül eldönthetjük, kiválasztjuk-e, így ebben az esetben \(\displaystyle 2\cdot 2=4\) lehetőség van. Ha az 5-öt nem választjuk ki, akkor az \(\displaystyle \{1;3\}\)-nak és a \(\displaystyle \{7;9\}\)-nek egymástól függetlenül választható egy-egy valódi részhalmaza (vagyis \(\displaystyle \emptyset,\{1\}, \{3\}\), illetve \(\displaystyle \emptyset,\{7\}, \{9\}\) valamelyike). Így ebben az esetben \(\displaystyle 3\cdot 3=9\) lehetőség van. Ez azt jelenti, hogy \(\displaystyle \{1;3;5;7;9\}\)-nek \(\displaystyle 4+9=13\) tyű-de-jó részhalmaza van.

Ehhez hasonlóan kapjuk, hogy \(\displaystyle \{2;4;6;8;10\}\)-nek is 13 tyű-de-jó részhalmaza van, ugyanis \(\displaystyle B\subseteq \{1;3;5;7;9\}\) pontosan akkor tyű-de-jó, ha \(\displaystyle B'=B+1=\{b+1:b\in B\}\subseteq \{2;4;6;8;10\}\) tyű-de-jó.

Tehát a fenti \(\displaystyle A=B\cup C\) előállításnál \(\displaystyle B\)-re és \(\displaystyle C\)-re is \(\displaystyle 13-13\) lehetőség van, így \(\displaystyle \{1;2;\dots;10\}\)-nek összesen \(\displaystyle 13\cdot 13=169\) tyű-de-jó részhalmaza van.

Megjegyzés. Teljes indukcióval látható, hogy \(\displaystyle \{1;3;5;\dots;2n-1\}\) halmaznak \(\displaystyle F_{n+2}\) tyű-de-jó részhalmaza van, ahol \(\displaystyle F_{n+2}\) az \(\displaystyle (n+2)\)-edik Fibonacci-szám. Így \(\displaystyle \{1;2;\dots;2n\}\) tyű-de-jó részhalmazainak száma \(\displaystyle F_{n+2}^2\), míg \(\displaystyle \{1;2;\dots;2n-1\}\) tyű-de-jó részhalmazainak száma \(\displaystyle F_{n+1}F_{n+2}\).

Statisztika:

73 dolgozat érkezett.
3 pontot kapott:	51 versenyző.
2 pontot kapott:	15 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2018. májusi matematika feladatai