Opgave 541 ^[oOO]

Er zijn een aantal manieren om dit te tellen, maar het eenvoudigste is om de waarden van $a$ en $b$ vast te leggen en daarna kijken hoeveel mogelijkheden er nog voor $c$ en $d$ zijn. We kunnen dan deze tabel maken:

$a$	$1$	$1$	$1$	$1$	$1$	$1$	$2$	$2$	$2$	$2$	$2$	$3$	$3$	$3$	$4$	$4$	$5$
$b$	$1$	$2$	$3$	$4$	$5$	$6$	$2$	$3$	$4$	$5$	$6$	$3$	$4$	$5$	$4$	$5$	$5$
aantal mogelijkheden $c$ en $d$	$9$	$7$	$6$	$4$	$3$	$1$	$7$	$5$	$4$	$2$	$1$	$5$	$3$	$2$	$3$	$1$	$1$

Als we alle waarden in de onderste rij optellen komen we op een totaal van $64$ oplossingen. 

Een alternatieve uitwerking is om te definiëren $w = a - 1, x = b - a, y = c - b, z = d - c$. Dan wordt de eis $1 \leq a \leq b \leq c \leq d$ omgezet in $w, x, y, z \geq 0$, en wordt de eis $a + b + c + d = 20$ omgezet in $4w + 3x + 2y  + z = 16$. We kunnen nu op een soortgelijke manier gaan tellen, maar ook een genererende functie opstellen:
$$    \frac{1}{(1-t)(1-t^2)(1-t^3)(1-t^4)} = 1 + t + 2t^2 + 3t^3 + 5t^4 + \ldots + 54t^{15} + 64t^{16} + 72t^{17} + \ldots$$
en als coefficiënt van $t^{16}$ lezen we af dat er precies $64$ oplossingen zijn. 

Opgave 542 ^[oOO]

We nummeren de rijen en kolommen zoals op een schaakbord, dus de kleine vierkantjes kunnen we dan als $A1$ t/m $D4$ aangeven. We maken onderscheid tussen drie soorten vakjes. Er zijn vier hoekvakjes ($A1$, $A4$, $D1$, $D4$), vier middenvakjes ($B2$, $B3$, $C2$, $C3$), en acht randvakjes (de rest). 

We bewijzen eerst dat we geen middenvakjes weg kunnen halen. Indien we een middenvakje weghalen neemt de omtrek toe met $4$, omdat er nu ineens een gat is. Als we dan een tweede vakje weghalen, dan zal de omtrek niet afnemen, ongeacht welk vakje we weghalen. Bij het weghalen van het derde vakje zou de omtrek dus met (minstens) $4$ moeten afnemen om weer op de originele omtrek uit te komen. Dit kan alleen als we een vakje $X$ weghalen dat nu niet meer verbonden is met een ander vakje, zodat de lengte van de rand met $4$ afneemt. Het vakje $X$ is nu niet verbonden, dus het grensde oorspronkelijk aan (maximaal) twee andere vakjes die we allemaal hebben weggehaald. Maar de enige vakjes die aan maximaal twee andere vakjes grenzen zijn de hoekvakjes, en die grenzen aan twee randvakjes, terwijl we maximaal een randvakje hebben verwijderd. Dit is een tegenspraak, dus we hebben geen middenvakjes verwijderd. 

We hebben dus alleen maar hoekvakjes en/of randvakjes verwijderd. We onderscheiden nu vier gevallen: 

• We hebben $3$ hoekvakjes weggehaald. Dit kan op $4$ manieren en in allevier de gevallen verandert de omtrek niet. We vinden dus $4$ oplossingen. 
• We hebben $2$ hoekvakjes weggehaald, dit kan op $6$ manieren. Dit verandert de omtrek niet. Nu moeten we nog een randvakje weghalen. Dit vakje moet dan grenzen aan een van de hoekvakjes zodat de omtrek niet verandert. Er zijn $4$ randvakjes die grenzen aan een hoekvakje. We vinden in totaal dus $6 \cdot 4 = 24$ oplossingen. 
• We hebben $1$ hoekvakje weggehaald, dit kan op $4$ manieren. Stel even zonder verlies van algemeenheid dat het $A1$ is. Dan kunnen we op drie manieren twee randvakjes weghalen, namelijk: $A2$ en $A3$, $B1$ en $C1$, of $A2$ en $B1$. We vinden dus bij ieder hoekvakje $3$ oplossingen dus in totaal $4 \cdot 3 = 12$ oplossingen. 

In totaal zijn er dus $4+24+12 = 40$ oplossingen. 

Opgave 543 ^[ooO]

Het antwoord is ja, zo'n ordening bestaat. We bewijzen een sterkere stelling namelijk dat er voor ieder positief geheel getal $n$ een ordening van de getallen $1$ t/m $n$ bestaat. We doen dit via een speciaal soort inductie. Als inductiebasis kunnen we het geval $n = 1$ nemen, waarvoor de enige mogelijke ordening voldoet. De inductiestap kunnen we in twee stappen doen:

Claim. Indien er een ordening bestaat van $1$ t/m $n$ die voldoet, dan is er ook een ordening van $1$ t/m $2n$ die voldoet.

Bewijs. Laat $\mathbf{r} = (r_1, \ldots, r_n)$ de ordening zijn. Definieer de ordening $\mathbf{t} = (2r_1 - 1, 2r_2 - 1, \ldots, 2r_n - 1, 2r_1, 2r_2, \ldots, 2r_n)$. Stel nu dat er twee getallen $t_i, t_j$ in $\mathbf{t}$ zijn zodat het gemiddelde van $t_i, t_j$ geheel is en tussen $t_i$ en $t_j$ in staat. Dan onderscheiden we drie gevallen: 

1. $i \leq n$ en $j \leq n$. Dan staat $\frac{1}{2}(2r_i - 1 + 2r_j - 1) = r_i + r_j - 1$ tussen $2r_i - 1$ en $2r_j - 1$. Maar dan staat in de rij $\mathbf{r}$ dus ook $\frac{1}{2}(r_i + r_j)$ tussen $r_i$ en $r_j$, en dat is in tegenspraak met het feit dat $\mathbf{r}$ voldoet aan de gestelde eigenschap. Dit kan dus niet. 
2. $i > n$ en $j > n$. We vinden op precies dezelfde manier als in het vorige geval een tegenspraak met het feit dat $\mathbf{r}$ voldoet. 
3. $i < n$ en $j > n$ (of andersom). Maar dan is $t_i$ oneven en $t_j$ even, dus kan het gemiddelde van $t_i$ en $t_j$ nooit geheel zijn. Ook dit is dus een tegenspraak. 

In alledrie de gevallen vinden we een tegenspraak, dus we concluderen dat het rijtje $\mathbf{t}$ van lengte $2n$ voldoet aan de gestelde eigenschap. 

Claim. Indien er een ordening bestaat van $1$ t/m $n$ die voldoet, bestaat er ook een ordening van $1$ t/m $m$ voor alle $m < n$.

Bewijs. Verwijder alle getallen $m + 1, m + 2, \ldots, n$ uit de ordening van $1$ t/m $n$. Dit geeft een ordening van de getallen $1$ t/m $m$. 

Door deze twee eigenschappen te combineren kunnen we laten zien dat het voor alle natuurlijke getallen $n$ mogelijk is, en dus ook voor $n = 20$ en $n = 2025$. 

Opgave 544 ^[ooO]

We rekenen eerst even een paar waarden uit. Indien $M(1) = 1$ dan zou gelden $M(M(1)) = M(1) = 1$ en dat is in tegenspraak met het feit dat $M(M(1)) = 3$. Indien $M(1) \geq 3$ dan is $M(M(1)) \geq M(3)$, dus $M(3) \leq 3$, en dit is in strijd met $M(3) > M(1)$. De enige mogelijkheid is dus dat $M(1) = 2$ en uit $M(M(1)) = 3$ volgt dan dat $M(2) = 3$. We kunnen nu met inductie bewijzen dat $M(3^n) = 2 \cdot 3^n$ en $M(2 \cdot 3^n) = 3^{n+1}$ voor alle $n \geq 0$. De inductiebasis hebben we zojuist gelegd. De inductiestap gaat als volgt. Stel $M(3^k) = 2 \cdot 3^k$ en $M(2 \cdot 3^k) = 3^{k+1}$. Dan geldt $M(3^{k+1}) = M(M(2 \cdot 3^k)) = 2 \cdot 3^{k+1}$, en $M(2 \cdot 3^{k+1}) = M(M(3^{k+1})) = 3^{k+2}$ waarmee de inductiestap bewezen is. Omdat $M$ strikt stijgend is volgt uit $M(3^n) = 2 \cdot 3^n$ en $M(2 \cdot 3^{n}) = 3^{n+1}$ dat $M(3^n + \ell) = 2 \cdot 3^n + \ell$ voor alle $0 \leq \ell \leq 3^n$. Hieruit volgt tevens dat $M(2 \cdot 3^n + \ell) = M(M(3^n + \ell)) = 3^{n+1} + 3\ell$ voor alle $0 \leq \ell \leq 3^n$. Aangezien $2025 = 2 \cdot 3^6 + 567$ vinden we dat $M(2025) = 3 \cdot 3^6 + 3 \cdot 567 = 3888$. 

We kunnen het ook anders aanpakken. We weten dat $3M(n) = M(M(M(n))) = M(3n)$, en dus is $M(2025) = M(3^4 \cdot 25) = 3^4 \cdot M(25) = 81M(25)$. Vervolgens kunnen we met wat extra kleine gevalletjes uitrekenen dat $M(25) = 48$ en dus is $M(2025) = 81 \cdot 48 = 3888$.