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.

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.