putnam-sets
Opgave - Putnam 1996 dag 2 vraag 1
(A)
Een verzameling/set van getallen noemen we een putnam-set als het aantal getallen in die set, zelfs als getal voorkomt in de set.
Bepaal het aantal putnam-sets die een deelverzameling zijn van
$ \{1,2,\cdots ,n\}$.
( vb. $1,4,5,6$ is een putnam-set)
****
(B)
Hoeveel Putnam sets zijn er die geen Putnam set als (strikte) deelverzameling hebben.
- login om te reageren
Oplossing
Bekijk het aantal sets met $1$ element: dit is er $1=\binom{n-1}{0}$.
Bekijk het aantal sets met $2$ elementen: dit zijn er $n-1=\binom{n-1}{1}$ omdat men één getal vrij kan kiezen uit $n-1$ getallen naast het getal $2$.
Bekijk het aantal sets met $3$ elementen: dit zijn er $\frac{(n-1)(n-2)}{2}=\binom{n-1}{2}$ omdat men twee getallen vrij kan kiezen uit $n-1$ getallen naast het getal $3$.
...
Bekijk het aantal sets met $n$ elementen: dit is er $1=\binom{n-1}{n-1}$ omdat men alle getallen tot $n$ moet gebruiken.
Tellen we deze getallen op, krijgen we volgens het binomium van Newton de uitwerking van $(1+1)^{n-1}=2^{n-1}$.
B
Bekijk het aantal sets met $1$ element: dit is enkel $\{1\}$.
Bekijk het aantal sets met $2$ elementen: dit zijn er $\binom{n-2}{1}$ omdat men één getal vrij kan kiezen uit $n-2$ getallen naast het getal $2$ (het getal $1$ mag niet gebruikt worden) .
Bekijk het aantal sets met $3$ elementen: dit zijn er $\binom{n-3}{2}$ omdat men twee getallen vrij kan kiezen uit $n-3$ getallen naast het getal $3$ (de getallen $1$ en $2$ mogen niet meer gebruikt worden).
Bekijk het aantal sets met $4$ elementen: dit zijn er $\binom{n-4}{3}$ omdat men drie getallen vrij kan kiezen uit $n-4$ getallen naast het getal $4$ (de getallen $1,2$ en $3$ mogen niet meer gebruikt worden).
...
De oplossing van de vraag is dus gelijk aan $1+\binom{n-2}{1} +\binom{n-3}{2} +\binom{n-4}{3} + ...$.
Met inductie kan nu bewezen worden dat dit gelijk is aan $F(n)$ waarbij $F(n)$ het $n$-de getal in de rij van Fibonacci is (beginnend met $1,1$)
Basis
$n=3$: $1+\binom{1}{1}=2=F(3)$
$n=4$ $1+\binom{2}{1}=2=F(4)$
Hypothese
Het geldt voor $n=k$ en $n=k+1$
Stap
Dan geldt voor $n=k+2$:
eerst tellen we alle sets zonder het getal $k+2$: dit zijn er
$1+\binom{k-1}{1} +\binom{k-2}{2} +\binom{k-3}{3} + ...$.
Het aantal sets mét het getal $k+2$:
Bekijk het aantal sets met $1$ element: dit zijn er geen.
Bekijk het aantal sets met $2$ elementen: dit is er $1$ omdat men de getallen $2$ en $k+2$ moet gebruiken.
Bekijk het aantal sets met $3$ elementen: dit zijn er $\binom{k-2}{1}$ omdat men één getal vrij kan kiezen uit $k-2$ getallen naast de getallen $3$ en $k+2$ (de getallen $1,2$ mogen niet gebruikt worden) .
Bekijk het aantal sets met $4$ elementen: dit zijn er $\binom{k-3}{2}$ omdat men twee getallen vrij kan kiezen uit $k-3$ getallen naast de getallen $4$ en $k+2$ (de getallen $1,2,3,$ mogen niet meer gebruikt worden).
Bekijk het aantal sets met $5$ elementen: dit zijn er $\binom{k-4}{3}$ omdat men drie getallen vrij kan kiezen uit $k-4$ getallen naast het getal $5$ en $k+2$ (de getallen $1,2,3,4$ mogen niet meer gebruikt worden).
...
Opgeteld krijgen we dan
$1+\binom{k-1}{1} +\binom{k-2}{2} +\binom{k-3}{3} + ...+1+\binom{k-2}{1} +\binom{k-3}{2} +\binom{k-4}{3} + ...$
Wat volgens de inductiehypothese gelijk is aan
$F(k+1)+F(k)=F(k+2)$
en we zijn klaar.