Oplossing Olympiade 63-1

Opgave 505 [oOO]

We bewijzen dit uit het ongerijmde: stel dat er geen twee zulke gasten te vinden zijn. Laat $n$ het aantal gasten op het feest zijn. Iedere gast heeft met minstens $0$ en maximaal $n - 1$ andere gasten gesproken: dit zijn $n$ mogelijke waarden. Omdat geen twee gasten met het zelfde aantal mensen hebben gesproken, is er een gast die met $0$ mensen heeft gesproken, een met $1$, een met $2$, et cetera, en een met $n - 1$. Maar de gast die met $n - 1$ andere gasten heeft gesproken heeft met iedereen gesproken, dus ook met de gast die met $0$ andere mensen heeft gesproken, waaruit blijkt dat deze gast wel degelijk met minstens een iemand heeft gesproken. Dit duidelijk een tegenspraak, dus de aanname moet onjuist zijn geweest en er zijn wel twee gasten die met evenveel andere gasten hebben gesproken. 

Opgave 506 [oOO]

Het antwoord is nee, dit kan niet. Dit kunnen we bewijzen door modulo $8$ te kijken (dat wil zeggen, de rest na het delen door $8$). Een getal dat eindigt op $2023$ is van de vorm $10000k + 2023$, en dan weten we dat
\begin{equation*}
    10000k + 2023 \equiv 2023 \equiv 7 \mod 8
\end{equation*}
Stel nu dat $n$ even is, schrijf $n = 2j$. Dan is
\begin{equation*}
    3^n = 3^{2j} = (3^2)^j = 9^j \equiv 1^j = 1 \mod 8
\end{equation*}
en dit kan dus nooit op $2023$ eindigen, omdat het een andere rest modulo $8$ geeft. Stel nu dat $n$ oneven is (schrijf $n = 2j + 1$), dan is
\begin{equation*}
    3^{2j + 1} = 3 \cdot 9^j \equiv 3 \cdot 1^j = 3 \mod 8
\end{equation*}
en dat kan dus ook nooit op $2023$ eindigen. De conclusie is dat $3^n$ nooit op 2023 kan eindigen. 

Als je dit zo leest zal je je waarschijnlijk afvragen: waar haal je het vandaan en hoe verzin ik zelf zoiets? Nou, de bovenstaande uitwerking is niet iets dat ik zomaar ineens bedacht. Ik begon ermee om te kijken of een driemacht op een $3$ kon eindigen, en dat kon: elk getal $n$ van de vorm $n = 4a + 1$ bleek te werken, met als simpelste voorbeeld $n = 1$. Daarna ging ik kijken of een driemacht ook op $23$ kon eindigen. Met wat rekenwerk reduceerde ik dan dat $a = 5b + 3$, zodat $n = 20a + 13$ met als kleinste voorbeeld $n = 13$, zodat $3^n = 1354323$. Toen dat gelukt was ging ik kijken of een driemacht op $023$ kon eindigen. Dit lukte niet, omdat het honderdtal van een driemacht van de vorm $n = 20a + 13$ altijd oneven bleek te zijn, terwijl 0 een even getal is. En zo bedacht ik om modulo $8$ te gaan werken: het gaat bij de honderdtallen fout, en 100 is deelbaar door 4 maar niet door 8. Het bleek dat ik het bewijs daarmee veel korter kon maken, ook zonder af te leiden dat $n = 20a + 13$ bijvoorbeeld. Op deze manier kan je een kort maar krachtig bewijs vinden. 

Opgave 507 [ooO]

We bewijzen dit met inductie. Voor $n = 1$ is het triviaal dat het mogelijk is: dit is de inductiebasis. Stel nu dat het mogelijk is voor $n = k$: we kunnen dus een $2^k \times 2^k$ bord met een hoekje eraf betegelen. We kunnen dan vier $2^k \times 2^k$ borden samenvoegen, zodat in het midden precies een L-triomino overblijft, en ook precies een hoekje leeg is. In de leegte van een L-tromino plaatsen we dan nog een L-triomino en zo hebben we een betegeling voor een $2^{k+1} \times 2^{k+1}$ bord met een hoekje eraf. De inductiehypothese geldt dus ook voor $n = k + 1$, en met inductie concluderen we dat het mogelijk is voor alle $n$. 

Opgave 508 [ooO]

Deze som is op meerdere manieren uit te rekenen (bijvoorbeeld met inductie), maar de snelste is om in te zien dat
\begin{equation*}
    \frac{n - 1}{n!} = \frac{n}{n!} - \frac{1}{n!} = \frac{1}{(n-1)!} - \frac{1}{n!}
\end{equation*}
en zo vinden we dat
\begin{align*}
    \frac{0}{1!} + \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \ldots & = \left(\frac{1}{0!} - \frac{1}{1!}\right) + \left(\frac{1}{1!} - \frac{1}{2!}\right) + \left(\frac{1}{2!} - \frac{1}{3!}\right) + \left(\frac{1}{3!} - \frac{1}{4!}\right) + \ldots \\
    & = \frac{1}{0!} + \left(-\frac{1}{1!} + \frac{1}{1!}\right) + \left(-\frac{1}{2!} + \frac{1}{2!}\right) + \left(-\frac{1}{3!} + \frac{1}{3!}\right) + \ldots  \\
    & = \frac{1}{0!} \\
    & = 1
\end{align*}
waar we van stap 1 naar stap 2 mogen gaan omdat de termen naar 0 convergeren. De uitkomst van de oneindige som is dus 1.