Opgave 465 ^[oOO]

We schrijven een getal bestaande uit de twee cijfers $a, b$ als $\overline{ab}$. Nu is $\overline{ab} = 10a + b$. Merk op dat moet gelden $b > a$, want anders is de rij dalend en komen we dus nooit op $\overline{ab}$ uit. De rekenkundige rij die in de opgave wordt gedefinieerd heeft startgetal $a$ en stapgrootte $b - a$, en dus komen we na $k$ stappen uit op het getal $a + k(b - a)$. Als we in deze rij het getal $\overline{ab}$ tegenkomen, moet er dus een $k$ zijn zodat $a + k(b - a) = \overline{ab}$, oftewel 

$$(k - 1)(b - a) = 10a$$

Dus $b - a$ is een deler van $10a$. We kunnen nu eenvoudig alle mogelijkheden voor $b - a$ nagaan. Omdat $a \geq 1$ (want een getal begint nooit met een 0) en $b \leq 9$ geldt dus $1 \leq b - a \leq 8$: we gaan al deze mogelijkheden na.  

• Als $b - a = 1, 2$ of $5$ dan is $b - a$ altijd een deler van $10a$. Voor $b - a = 1$ geeft dit 8 verschillende oplossingen (12, 23, 34, 45, 56, 67, 78, 89), voor $b - a = 2$ in totaal 7 (13, 24, 35, 46, 57, 68, 79) en voor $b - a = 5$ in totaal 4 ($16$, $27$, $38$, $49$)
• Als $b - a = 3$ dan is $3$ een deler van $10a$, dus als $3$ een deler is van $a$. Omdat $b \leq 9$ is $a \leq 6$. Dus $a = 3$ of $a = 6$. Dit geeft de twee oplossingen $36$ en $69$
• Als $b - a = 4$ dan is $4$ een deler van $10a$ dus $2$ een deler van $a$. Omdat $b \leq 9$ is $a \leq 5$, dus we vinden $a = 2$ of $a = 4$, dit geeft de twee oplossingen $26$ en $48$
• Als $a - b = 6$ is $6$ een deler van $10a$ dus $3$ een deler van $a$. Omdat $b \leq 9$ is $a \leq 3$. De enige mogelijkheid is $a = 3$ en dit geeft de oplossing $39$
• Als $a - b = 7$ of $8$ vinden we geen oplossingen meer

In totaal hebben we dus $8 + 7 + 4 + 2 + 2 + 1 = 24$ oplossingen. 

Opgave 466 ^[oOO]

We bewijzen dat de bij alle cellen kan bereiken. Dit doen we door te bewijzen dat hij vanuit de cel waar hij zit alle cellen om hem heen kan bereiken. 

• De cel direct boven hem (die hij zou bereiken door het commando $A$) kan hij bereiken door de stukjes $A = ABA + ABA + BCBC + CCA$
• De cel rechtsonder hem (die hij zou bereiken door het commando $B$) kan hij bereiken door de stukjes $B = ABA + BCBC$
• De cel linksonder hem (die hij zou bereiken door het commando $C$) kan hij bereiken door de stukjes $C = ABA + BCBC + CCA$
• De cel rechtsboven hem kan hij bereiken door $A + B$
• De cel direct onder hem kan hij bereiken door $B + C$
• De cel linksboven hem kan hij bereiken door $C + A$

Op deze manier kan de bij dus alle cellen naast hem bereiken. Als de bij nu naar een willekeurige cel moet, hoeft de koningin dus alleen maar een route te plannen met stapjes van $1$ cel, en dan steeds bij iedere stap van $1$ de bijbehorende lijst van stukjes te geven. 

Dit geeft trouwens waarschijnlijk niet de snelste route voor de bij, maar op deze manier is de koningin er wel zeker van dat het lukt. 

Opgave 467 ^[ooO]

We bewijzen eerst een lemma. Stel dat we twee breuken $q/r$ en $s/t$ hebben met $q/r + s/t$ geheel, ${\rm ggd}(q, r) = {\rm ggd}(s, t) = 1$ en $r, t > 0$, dan moet gelden $r = t$.

Bewijs: stel $q/r + s/t = p$ met $p$ geheel. Dan is $$qt + rs = prt$$ 

We zien nu dat $r(pt - s) = qt$, dus $r \mid qt$. Omdat ${\rm ggd}(q, r) = 1$ is dus $r \mid t$. Omdat $r, t > 0$ volgt hieruit dat $r \leq t$. Op dezelfde manier is $t(pr - q) = rs$, dus $t \mid rs$. Omdat ${\rm ggd}(s, t) = 1$ is dus $t \mid r$, en dus $t \leq r$. Dus $t = r$. 

We gaan nu met de opgave aan de slag. Stel $x = a/b$ en $y = c/d$, $x^2 + y = m$ en $y^2 + x = n$. Nu zijn $m, n$ geheel. Verder veronderstellen we dat ${\rm ggd}(a, b) = {\rm ggd}(c, d) = 1$. Ook stellen we dat $b, d > 0$: weliswaar mogen $x$ en $y$ negatief zijn, maar een minteken kunnen we net zo goed in de teller zetten. Dan geldt nu 
$$x^2 + y = \frac{a^2}{b^2} + \frac{c}{d}, \quad y^2 + x = \frac{c^2}{d^2} + \frac{a}{b}$$ 

Met ons lemma is nu $b^2 = d$ en $d^2 = b$. Hieruit volgt dat $d^4 = d$, dus $d^3 = 1$. Dus $d = 1$, en ook $b = 1$. Hieruit volgt dat $x = a$ en $y = c$, dus $x$ en $y$ zijn inderdaad geheel. 

Indien $x$ en $y$ reëel zijn, hoeft dit niet meer te kloppen. We kunnen bijvoorbeeld nemen 
$$x = y = \frac{-1 + \sqrt{5}}{2}$$
Dan is $x^2 + y = 1$ en $x + y^2 = 1$, maar $x$ en $y$ zijn niet geheel.

Even tussen haakjes, als je een tegenvoorbeeld instuurt hoef je niet uit te leggen hoe je het gevonden hebt. En als je het wel wilt uitleggen, zet je uitleg dan na het voorbeeld. Wij hadden dit voorbeeld gevonden door gewoon $x = y$ te proberen. Dan wil je een getal $x$ vinden zodat $m = x^2 + x$ geheel is, maar $x$ niet. Het getal $m = 1$ blijkt dan te werken: de bijbehorende $x$ (te berekenen met de ABC-formule) is niet geheel. 

Opgave 468 ^[ooO]

We noemen de vier steden $a, b, c, d$ waarbij de steden $b$ en $c$ de diagonale verbinding hebben. We claimen nu dat $a = 2k, b = k, c = k, d = k - 1$ een winst van $1$ goudstuk geeft voor alle $k \geq 2$. 

Met deze types steden is de totale opbrengst gelijk aan 
$$a^2 + b^2 + c^2 + d^2 = (2k)^2 + k^2 + k^2 + (k-1)^2 = 7k^2 - 2k + 1$$
en de totale onderhoudskosten zijn
$$ab + bc + ac + bd + cd = 2k^2 + k^2 + 2k^2 + k(k-1) + k(k-1) = 7k^2 - 2k$$
En dus is de totale winst gelijk aan $7k^2 - 2k + 1 - (7k^2 - 2k) = 1$ goudstuk. 

We hadden trouwens een foutje gemaakt in de bonusopgave, want een winst van $2$ is wel degelijk mogelijk. Dit kan bijvoorbeeld als $a = 1, b = 2, c = 4, d = 1$. Een aantal inzenders hadden dit correct opgemerkt. De opgave had moeten zijn dat we ook nog een weg van stad $a$ naar stad $d$ aanleggen: dan is een winst van $2$ wel onmogelijk. Kan je bedenken waarom?