Opgave 525 ^[oOO]

Om deze opgave op te lossen maken we een lijst van priemgetallen, en kijken we dan naar de verschillen tussen opeenvolgende priemgetallen: 
$$2 \stackrel{+1}{\longrightarrow} 3 \stackrel{+2}{\longrightarrow} 5 \stackrel{+2}{\longrightarrow} 7 \stackrel{+4}{\longrightarrow} 11 \stackrel{+2}{\longrightarrow} 13 \stackrel{+4}{\longrightarrow} 17 \stackrel{+2}{\longrightarrow} 19 \stackrel{+4}{\longrightarrow} 23 \stackrel{+6}{\longrightarrow} 29 \stackrel{+2}{\longrightarrow} 31 \stackrel{+6}{\longrightarrow} 37 \stackrel{+4}{\longrightarrow} 41 \stackrel{+2}{\longrightarrow} 43$$

$$43 \stackrel{+4}{\longrightarrow} 47 \stackrel{+6}{\longrightarrow} 53 \stackrel{+6}{\longrightarrow} 59 \stackrel{+2}{\longrightarrow} 61 \stackrel{+6}{\longrightarrow} 67 \stackrel{+4}{\longrightarrow} 71 \stackrel{+2}{\longrightarrow} 73 \stackrel{+4}{\longrightarrow} 77 \stackrel{+6}{\longrightarrow} 83 \stackrel{+6}{\longrightarrow} 89 \stackrel{+8}{\longrightarrow} 97.$$

Tussen $89$ en $97$ zien we voor het eerst een verschil groter dan $7$. Dus het kindje van Anne en Bob is minstens $89$ dagen oud. 

Opgave 526 ^[oOO]

Om een idee te krijgen kunnen we een paar waarden van $n$ uitproberen, om te zien of $n^{n+1}$ of $(n+1)^n$ groter is. 

$\color{white}{n}$	$\color{white}{n^{n+1}}$	$\color{white}{(n+1)^n}$
$\ \ 2\ \ $	$8$	$\underline{9}$
$\ \ 3\ \ $	$\underline{81}$	$64$
$\ \ 4\ \ $	$\underline{1024}$	$625$
$\ \ 5\ \ $	$\underline{15625}$	$7776$
$\ \ 6\ \ $	$\underline{279936}$	$117649$

We zien dat voor $n = 2$ geldt dat $(n+1)^n$ groter is, maar voor grotere $n$ is $n^{n+1}$ groter. We kunnen hieruit echter niet concluderen dat dit een algemeen patroon is! Een manier om het wel te bewijzen, is door naar het quotiënt te kijken. Voor $n \geq 3$ hebben we:
\begin{align*}
    \frac{(n+1)^n}{n^{n+1}} & = \frac{1}{n}\frac{(n+1)^n}{n^n} \\
    & = \frac{1}{n}\left(\frac{n+1}{n}\right)^n \\
    & = \frac{1}{n}\left(1 + \frac{1}{n}\right)^n \\
    & \leq \frac{1}{n} \cdot e \\
    & < \frac{1}{n} \cdot 3 \\
    & < 1
\end{align*}
waaruit volgt dat $(n+1)^n < n^{n+1}$ voor alle $n \geq 3$. Dus ook voor $n = 2024^{2024}$. Merk op dat we gebruik maakten van de bekende identiteit 
$$\lim_{n \rightarrow \infty}\left(1 + \frac{1}{n}\right)^n = e$$
en het eveneens bekende feit dat de reeks $\left(1 + \frac{1}{n}\right)^n $ stijgend is in $n$, waardoor $\left(1 + \frac{1}{n}\right)^n  \leq e$ voor alle $n$. De conclusie is dat $n^{n+1}$ groter is. 

Opgave 527 ^[ooO]

Het ligt hier voor de hand dat de optimale rij gegeven wordt door $1, 2, 4, 8, 16, \ldots, 524\,288$, maar het is nog best lastig om hier echt een waterdicht bewijs voor te geven. Voor het gemak noemen we een rijtje dat volledig uit positieve gehele getallen bestaat en waarvan ook alle verschilrijen volledig uit positieve gehele getallen bestaan \textbf{sterk positief}. Indien we $k$ keer de verschilrij pakken van een rijtje, spreken we van de $\textbf{k}$-de verschilrij. De eerste verschilrij noemen we ook wel gewoon 'de verschilrij'. We pakken het als volgt aan:

Lemma 1. Indien $a_1, a_2, \ldots, a_n$ een sterk positief rijtje is en $1 < m < n$, dan is $a_1, a_2, \ldots, a_m$ ook een sterk positief rijtje.

Bewijs. De originele rij $a_1, a_2, \ldots, a_m$ bestaat volledig uit positieve gehele getallen, omdat $a_1, a_2, \ldots, a_n$ dat ook bestaat.
De $k$-de verschilrij van $a_1, \ldots, a_m$ is precies de eerste $m - k$ elementen van de $k$-de verschilrij van $a_1, a_2, \ldots, a_n$. We concluderen dat alle verschilrijen van $a_1, a_2, \ldots, a_m$ bestaan uit positieve gehele getallen en dus is $a_1, a_2, \ldots, a_m$ zelf ook sterk positief.

Lemma 2. Indien $a_1, a_2, \ldots, a_n$ een sterk positief rijtje is, dan is de verschilrij van $a_1, a_2, \ldots, a_n$ (noteer deze als $b_1, b_2, \ldots, b_{n-1}$) ook een sterk positief rijtje.

Bewijs. De $k$-de verschilrij van $b_1, b_2, \ldots, b_{n-1}$ is precies de $(k + 1)$-ste verschilrij van $a_1, a_2, \ldots, a_n$, en bestaat dus volledig uit positieve gehele getallen. De rij $b_1, b_2, \ldots, b_{n-1}$ is de (eerste) verschilrij van $a_1, a_2, \ldots, a_n$ en bestaat dus ook volledig uit positieve gehele getallen. Dus $b_1, b_2, \ldots, b_{n-1}$ is ook sterk positief.

Lemma 3. In een sterk positief rijtje $a_1, \ldots, a_n$ geldt dat $a_n \geq 2^{n-1}$.

Bewijs. We bewijzen dit met inductie naar $m$. Voor $m = 1$ is het waar, omdat $a_1$ positief en geheel moet zijn en dus $a_1 \geq 1 = 2^0$. Stel nu dat het waar is voor een zekere waarde $m$. Beschouw nu een sterk positief rijtje $a_1, a_2, \ldots, a_{m+1}$. Omdat dit rijtje sterk positief is, is het rijtje $a_1, a_2, \ldots, a_m$ ook sterk positief (wegens Lemma 1), en dus is $a_m \geq 2^{m-1}$ wegens de inductiehypothese. Als we naar de (eerste) verschilrij kijken dan het is $m$-de element $a_{m+1} - a_m$. Omdat de (eerste) verschilrij van $a_1, a_2, \ldots, a_{m+1}$ sterk positief is (wegens lemma 2), is dus het $m$-de element $a_{m+1} - a_m \geq 2^{m-1}$ (wegens de inductiehypothese). Dus $a_{m+1} \geq a_m + 2^{m-1} \geq 2^{m-1} + 2^{m-1} = 2^m$, waarmee de inductiestap voltooid is.

We concluderen dat voor een sterk positief rijtje van lengte 20 geldt dat $a_{20} \geq 2^{19}$. We moeten nu nog wel laten zien dat er ook daadwerkelijk een sterk positief rijtje is dat deze waarde behaalt. Neem het rijtje $1, 2, \ldots, 2^{19}$: dit bestaat volledig uit positieve gehele getallen. Dan is (met inductie) eenvoudig te bewijzen dat de $k$-de verschilrij precies $1, 2 \ldots, 2^{19-k}$ is, wat voor alle $1 \leq k \leq 19$ volledig uit positieve gehele getallen bestaat. We concluderen dat dit rijtje sterk positief is, en dus is $a_{20} = 2^{19} = 524288$ de kleinst mogelijke waarde. 

Opgave 528 ^[ooO]

We kiezen twee willekeurige punten in het rooster (dat wil zeggen, hoekpunten van een klein driehoekje). Indien deze twee punten niet op een roosterlijn liggen, dan kunnen we op precies een manier een parallellogram maken waarbij deze twee hoekpunten een hoek van $60^{\rm o}$ hebben. Omgekeerd bestaan er voor ieder parallellogram ook twee zulke roosterpunten (namelijk de twee hoekpunten met een hoek van $60^{\rm o}$) die niet op een lijn liggen. Het aantal parallellogrammen is dus precies gelijk aan het aantal manieren om twee roosterpunten te kiezen die niet op een lijn liggen. Dit is best lastig uit te rekenen, dus laten we het aantal manieren uitrekenen om twee roosterpunten te kiezen die wél op een lijn liggen:

1. Op een horizontale roosterlijn met $k$ roosterpunten kunnen we op $\tfrac{1}{2}k(k-1)$ manieren twee roosterpunten kiezen (namelijk $k$ manieren voor het eerste punt, $k - 1$ voor het tweede punt, en dan delen door twee omdat we anders dubbel tellen). De horizontale roosterlijnen hebben $1, 2, 3, \ldots, 19$ roosterpunten, dus hiervoor zijn $$\frac{1}{2} \cdot 1 \cdot (1-1) + \frac{1}{2} \cdot 2 \cdot (2-1) + \frac{1}{2} \cdot 3 \cdot (3-1) + \ldots + \frac{1}{2} \cdot 19 \cdot (19-1) = 1140$$ manieren. 
2. De roosterlijnen parallel aan de linker zijde van de driehoek kunnen op dezelfde manier worden behandeld: hier zijn er ook 1140 manieren. 
3. Idem voor de roosterlijnen parallel aan de rechterzijde van de driehoek: 1140 manieren. 

Kijken we naar de roosterlijnen, dan tellen we in totaal $1 + 2 + \ldots + 19 = \tfrac{1}{2} \cdot 19 \cdot 20 = 190$ roosterpunten. We kunnen dus op $\tfrac{1}{2} \cdot 190 \cdot (190-1) = 17955$ manieren twee punten kiezen. Echter in $3 \cdot 1140 = 3420$ gevallen zullen deze op een roosterlijn liggen en geen parallellogram vormen: in totaal vormen de twee punten dus op $17955 - 3420 = 14535$ manieren een parallellogram. En dat is dus ook het aantal parallellogrammen in de driehoek.