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