Opgave 485 ^[oOO]

We noteren $x \mid y$ als $x$ een deler is van $y$. We gebruiken de rekenregel dat als $x \mid y$ en $x \mid z$, dan $x \mid y + z$ en $x \mid y - z$.

Stel dat er gehele getallen $a, b$ bestaan zodat $x^2 + ax + b$ altijd deelbaar is door 3. Als we $x = 0$ invullen krijgen we dat $3 \mid b$. Als we $x = 1$ invullen krijgen we $3 \mid 1 + a + b$, en omdat $3 \mid b$ vinden we dat $3 \mid 1 + a$. Als we $x = 2$ invullen krijgen we $3 \mid 4 + 2a + b$. Omdat $3 \mid b$ volgt hieruit dat $3 \mid 4 + 2a$ en omdat $3 \mid 1 + a$ volgt daaruit dat $3 \mid (4 + 2a) - 2(1 + a)$, dus $3 \mid 2$. Dit is een tegenspraak, omdat 3 geen deler is van 2.

Er bestaan wel gehele getallen $a, b, c$ zodat $x^3 + ax^2 + bx + c$ voor alle gehele $x$ deelbaar is door 3. Neem bijvoorbeeld $a = 3, b = 2, c = 0$. Dan krijgen we $x^3 + 3x^2 + 2x = x(x+1)(x+2)$. Van de drie getallen $x, x + 1$ en $x + 2$ is er altijd precies een deelbaar door 3, dus is $x(x+1)(x+2)$ altijd deelbaar door 3.

Opgave 486 ^[oOO]

Het idee bij deze opgave is om met \textit{recursie} te werken: dat wil zeggen, om voor steeds langere skylines te berekenen hoeveel mogelijkheden er zijn. We noteren $S(n, i)$ als het aantal skylines van lengte $n$ waarvan het laatste gebouw hoogte $i$ heeft, en $T(n)$ als het totale aantal skylines van lengte $n$. Dan hebben we de volgende recursieve relaties:

\begin{align*}
S(1, i) & = 0 & \mbox{ voor alle } i \\
S(n, 1) & = S(n - 1, 1) + S(n - 1, 2) & \mbox{ als } n \geq 2 \\
S(n, 5) & = S(n - 1, 5) + S(n - 1, 4) & \mbox{ als } n \geq 2 \\
S(n, i) & = S(n - 1, i - 1) + S(n - 1, i) + S(n - 1, i + 1) & \mbox{ als } n \geq 2, 2 \leq i \leq 4 \\
T(n) & = S(n, 1) + S(n, 2) + S(n, 3) + S(n, 4) + S(n, 5) & \mbox{ voor alle } n \geq 1
\end{align*}

Hiermee kunnen we een tabel maken voor $S$ en $T$.

$n$		$1$	$2$	$3$	$4$	$5$	$6$
$S(n, 5)$		$1$	$2$	$5$	$13$	$35$	$95$
$S(n, 4)$		$1$	$3$	$8$	$22$	$60$	$164$
$S(n, 3)$		$1$	$3$	$9$	$25$	$69$	$189$
$S(n, 2)$		$1$	$3$	$8$	$22$	$60$	$164$
$S(n, 1)$		$1$	$2$	$5$	$13$	$35$	$95$
$T(n)$		$5$	$13$	$35$	$95$	$259$	$707$

We zouden deze tabel kunnen uitbreiden tot we bij de 10 zijn, maar we kunnen ook op zoek gaan naar patronen. Het eerste patroon dat opvalt is dat $S(n, i) = S(n, 6 - i)$. Dit is logisch: als we een skyline hebben waarvan het laatste gebouw hoogte $i$ heeft, dan kunnen we van elk gebouw de hoogte $h$ vervangen door $6 - h$ en dan krijgen we een nieuwe skyline waarvan het laatste gebouw hoogte $6 - i$ heeft. Andersom kan dit ook, dus geldt $S(n, i) = S(n, 6 - i)$.

Een ander patroon dat opvalt is $T(n) = S(n + 2, 1)$. Ook dit kunnen we bewijzen:

\begin{align*}
S(n + 2, 1) & = S(n + 1, 1) + S(n + 1, 2) \\
& = (S(n, 1) + S(n, 2)) + (S(n, 1) + S(n, 2) + S(n, 3)) \\
& = 2S(n, 1) + 2S(n, 2) + S(n, 3) \\
& = S(n, 1) + S(n, 2) + S(n, 3) + S(n, 4) + S(n, 5) \\
& = T(n)
\end{align*}

We kunnen ook met een verhaaltje laten zien dat dit zo is. Neem een willekeurige skyline van lengte $n$, en stel dat we deze op hoogte 1 of 5 willen laten eindigen. Dan zijn hier, ongeacht de hoogte van het laatste gebouw, precies 2 manieren voor. Dus geldt $2T(n) = S(n + 2, 1) + S(n + 2, 5)$, en omdat $S(n + 2, 1) = S(n + 2, 5)$ volgt hieruit dat $T(n) = S(n + 2, 1)$.

Door uit te schrijven vinden we nu dat

\begin{align*}
T(n + 1) & = S(n, 1) + S(n, 2) + S(n, 3) + S(n, 4) + S(n, 5) \\
& = 2S(n, 1) + 3S(n, 2) + 3S(n, 3) + 3S(n, 4) + 2S(n, 5) \\
& = 3T(n) - S(n, 1) - S(n, 5) \\
& = 3T(n) - 2T(n - 2)\end{align*}

Ook dit zouden we met een verhaaltje kunnen bewijzen (probeer dat zelf maar te verzinnen). Met deze formule $T(n + 1) = 3T(n) - 2T(n - 2)$ kunnen we vrij snel $T(10)$ uitrekenen, en vinden we dat er $T(10) = 39 371$ skylines van lengte 10 zijn.

Opgave 487 ^[ooO]

Als $x = 0$ dan is $1 - xy = 1$ en dat is inderdaad het kwadraat van een rationaal getal. Hetzelfde geldt als $y = 0$. Neem nu aam dat $x, y \neq 0$. We kunnen in de vergelijking

$$x^7 + y^7 = 2x^3y^3$$

beide kanten kwadrateren: dan vinden we dat

\begin{align*}
x^{14} + 2x^7y^7 + y^{14} & = 4x^6y^6 \\
x^{14} - 2x^7y^7 + y^{14} & = 4x^6y^6 - 4x^7y^7 \\
(x^7 - y^7)^2 & = 4x^6y^6(1 - xy) \\
\left(\frac{x^7 - y^7}{2x^3y^3}\right)^2 & = 1 - xy
\end{align*}

Aangezien $x, y$ allebei rationaal zijn, volgt hieruit dat $(x^7 - y^7)/2x^3y^3$ ook rationaal is, en dus is de linkerkant het kwadraat van een rationaal getal. En dus is $1 - xy$ ook het kwadraat van een rationaal getal.

Opgave 488 ^[ooO]

Er zijn meerdere manieren om deze lastige opgave aan te pakken, maar het komt erop neer dat je een manier moet vinden om alle mogelijkheden te vinden, waarbij je zeker weet dat je niets overslaat of dubbel telt. We zullen hier \'e\'en mogelijke aanpak laten zien.

Om de percelen (vakjes) aan te duiden gebruiken we de schaaknotatie: de kolommen heten van links naar rechts $A$, $B$, $C$ en $D$, en de rijen heten van beneden naar boven $1$, $2$, $3$ en $4$. Merk op dat als we de middelste 4 vakjes weghalen, dat het blauwe en rode deel dan nog steeds aaneengesloten moet zijn. Anders zouden in de middelste 4 vakjes een pad van blauwe vakjes (om de twee blauwe delen te verbinden) en een pad van rode vakjes elkaar moeten kruisen, wat duidelijk niet kan. Met deze wetenschap kunnen we onderscheid maken tussen de volgende gevallen:

1. De vier middelste vakjes zijn allevier rood. In dit geval zijn er nog $4$ rode vakjes in de rand, die aaneengesloten moeten zijn. Hier zijn $12$ mogelijkheden voor.
2. Drie vakjes in het midden zijn rood. Stel even dat $C3$ het enige blauwe vakje is. Er moeten in totaal $5$ rode vakjes in de rand: echter op $3$ manieren sluiten we vakje $C3$ op, waardoor het blauwe deel niet aaneengesloten is. Dus er zijn in totaal $9$ mogelijkheden. Omdat er $4$ mogelijke plaatsen voor het enige blauwe vakje in het midden zijn, vinden we in totaal $4 \cdot 9 = 36$ mogelijkheden.
3. Twee vakjes in het midden zijn rood.} Als de vakjes $B2$ en $C3$ rood zijn (terwijl $B3$ en $C2$ blauw zijn), dan moeten we een blauw vakje insluiten bij het verbinden van de twee rode vakjes: dit kan dus niet. Hetzelfde argument geldt als $B3$ en $C2$ rood zijn. De twee rode vakjes in het midden liggen dus naast elkaar. Stel even dat $B2$ en $C2$ rood zijn, terwijl $B3$ en $C3$ blauw zijn. Dan zijn er nog 6 rode vakjes op de rand, die aaneengesloten zijn. Deze kunnen we op $11$ manieren plaatsen zodat zowel het blauwe als rode gebied aaneengesloten zijn. Omdat er $4$ manieren zijn om twee aaneengesloten vakjes in het midden rood te maken, vinden we in totaal $4 \cdot 11 = 44$ mogelijkheden.
4. Een vakje in het midden rood. Dit kunnen we op precies dezelfde manier doen als drie vakjes rood: we vinden dus weer $36$ mogelijkheden.
5. Geen vakjes in het midden rood. Dit kan op precies dezelfde manier als het geval dat alle vakjes in het midden rood zijn: hier vinden we dus $12$ mogelijkheden.

In totaal vinden we dus $12 + 36 + 44 + 36 + 12 = 140$ mogelijkheden om de grond te verdelen.