Opgave 334 [niveau oOO]

Start met het getal 1. Vervolgens kies je of je er 2 bij optelt óf het met 3 vermenigvuldigt. Met het volgende getal heb je weer precies dezelfde keuze: 2 erbij optellen óf met 3 vermenigvuldigen. Zo ga je door, maar: je mag niet twee keer achter elkaar 2 erbij optellen. Dus nadat je er 2 bij hebt opgeteld, moet je met 3 vermenigvuldigen, of stoppen. Kun je op deze manier het getal 2016 verkrijgen?
Oplossing. Het getal ná 1 is hoe dan ook 3. Daarna komt 5 of 9. Je ziet dat dit allemaal oneven getallen zijn, en dat blijft zo: is $x$ oneven, dan is zowel $x$ + 2 als 3$x$ oneven. Omdat 2016 even is, kun je dus nooit op dit getal uitkomen (zelfs zonder de restrictie dat je niet twee keer achter elkaar 2 erbij mag optellen).

 

Opgave 335 [niveau oOO]

Boris en Laila maken een afspraakje om Otto te imponeren. Ze doen het volgende spelletje met 10 kaarten. Deze liggen blind op tafel met de cijfers 1 tot en met 10 op de onderkanten. Otto mag er 3 willekeurig uitkiezen en blind bij zich neerleggen. Boris pakt de andere 7 op en bekijkt ze. Otto mag er dan 3 uit de 7 trekken en blind bij Boris neerleggen. Dan zegt Boris: ‘De andere 4 kaarten zijn voor jou, Laila’ en geeft ze een voor een aan haar. Ze bekijkt ze en zegt vervolgens tegen Otto welke kaarten hij heeft. Dat zegt ze altijd goed, hoe vaak ze het spelletje ook doen. Otto snapt er eerst niets van, maar dan bedenkt hij wat Boris en Laila hebben afgesproken. Weet jij ook wat Boris en Laila hebben afgesproken?
Oplossing. Omdat Boris de andere 7 kaarten mag zien, weet hij precies welke kaarten Otto heeft. Laila krijgt 4 van deze kaarten; zij weet dus van deze 4 kaarten dat Otto ze niet heeft. Er zijn dus nog 6 onbekende kaarten die Otto zou kunnen hebben. Otto heeft 3 ervan, dus voor Laila zijn er (6 · 5 · 4)/(3 · 2 · 1) = 20 mogelijkheden voor de kaarten van Otto. Maar aangezien Boris wel weet welke kaarten Otto heeft, kan hij in de volgorde waarin hij de 4 kaarten aan Laila geeft (hij geeft de kaarten immers één voor één) aan Laila doorgeven welke kaarten Otto heeft. Hiervoor heeft Otto 4! = 24 mogelijkheden, meer dan 20.
Met deze kennis kunnen Boris en Laila als volgt een afspraak maken. Aan iedere keuze van 3 elementen uit een rij van 6 kennen ze een nummer toe, van 1 tot en met 20. Vervolgens kiezen ze 20 verschillende permutaties van de getallen 1, 2, 3, 4, en kennen ze aan ieder daarvan ook een nummer 1, 2, ..., 20 toe. Dit kan, aangezien er 4! = 24 ≥ 20 permutaties van 1, 2, 3, 4 zijn. Nadat bij Boris door Otto 3 uit de 7 kaarten zijn getrokken, sorteert Boris de 6 kaarten die Otto heeft getrokken, en bepaalt de positie van de 3 die het eerste getrokken waren in deze rij. Dit correspondeert met een keuze van 3 uit 6, en hij bepaalt het nummer dat hij hiermee met Laila had afgesproken. Vervolgens neemt Otto de permutatie van 1, 2, 3, 4 die hetzelfde nummer heeft. Hij sorteert de kaarten volgens deze permutatie (van laag naar hoog: het getal 1 correspondeert met het laagste getal, het getal 2 met het één na laagste, enzovoort), en geeft ze in die volgorde aan Laila. Voorbeeld: als Otto nog de kaarten 3, 6, 7, 9 heeft en de permutatie is 3, 1, 4, 2, dan geeft Otto de kaarten in volgorde 7, 3, 9, 6 aan Laila. Laila bekijkt de volgorde waarin de kaarten zijn gegeven en bepaalt hieruit de permutatie van 1, 2, 3, 4 die erbij hoort, en hieruit het getal tussen 1 en 20. Ze bepaalt de keuze van 3 uit 6 die hetzelfde nummer heeft. Ze sorteert de zes kaarten die ze niet heeft van laag naar hoog, en neemt vervolgens de kaarten volgens de bepaalde keuze van 3 uit 6. Dat zijn dan de drie kaarten van Otto.

 

Opgave 336 [niveau ooO]

De twee koppels positieve gehele getallen $(2, 2)$ en $(2, 2)$ hebben de eigenschap dat de som van het eerste koppel gelijk is aan het product van het tweede koppel en het product van het eerste koppel gelijk is aan de som van het tweede koppel. Dit is natuurlijk een flauw voorbeeld. Zijn er nog andere geheeltallige koppels $(a, b)$ en $(c, d)$ met deze eigenschap?
Zo ja, hoeveel?
Oplossing. Het was voldoende om uit te gaan van koppels positieve gehele getallen $(a, b)$ en $(c, d)$. Voor dit geval is het aantal oplossingen $9$. Dat laten we hier zien; hieronder staat een bewijs dat er méér koppels zijn als $a, b, c, d$ ook negatief mogen zijn.
Het gevraagde is te formuleren als het stelsel $ab = c + d$ en $a + b = cd$. Neem eerst aan dat $a, b, c, d$ allemaal positief zijn. Dan is het duidelijk dat $a, b, c, d$ niet heel groot kunnen worden. We bewijzen dit als volgt.
Stel $a, b, c, d ≥ 2$. Dan is $(a – 1)(b – 1) ≥ 1$, en dan geeft haakjes uitwerken $ab ≥ a + b$, met gelijkheid dan en slechts dan als $a = b = 2$. Stel nu dat $(a, b)$ en $(c, d)$ de gevraagde eigenschap hebben. Dan is $ab · cd = (c + d) · (a + b) ≤ cd · ab$, met gelijkheid dan en slechts dan als $a = b = 2$ en $c = d = 2$: dit was het flauwe voorbeeld dat al in de opgave was gegeven.
Voor iedere andere oplossing is dus ten minste één van de getallen gelijk aan $1$. Stel dat in elk geval $a = 1$. Dan volgt $b = c + d$ en $1 + b = cd$. Substitutie van $b = c + d$ in de tweede vergelijking geeft $1 + c + d = cd$, ofwel $(c – 1)(d – 1) = 2$. Omdat we hadden aangenomen dat alle getallen positief zijn, volgt hieruit $c – 1 = 1$ en $d – 1 = 2$ (of andersom) en dus $c = 2$ en $d = 3$. Hieruit volgt $b = c + d = 5$. We krijgen dus als paren $(1, 5)$ en $(2, 3)$. Controle geeft dat deze twee tweetallen inderdaad voldoen.
We hadden hier aangenomen $a = 1$ en $c = 2$. Indien we deze restrictie laten vallen, kunnen we nog meer oplossingen maken. We kunnen de volgorde van de tweetallen, de volgorde van $a$ en $b$, en de volgorde van $c$ en $d$ verwisselen: we krijgen uit deze ene oplossing zo in totaal $8$ oplossingen. Op deze manier krijgen we in totaal $8 + 1 = 9$ oplossingen.

Opgave 337 [niveau ooO]

Aan weerszijden van een wandelpad is water. Dit is tevens het leefgebied van een bepaalde kikkersoort. Alle kikkers doen in het voorjaar een poging om aan de andere kant van het pad te komen. Ze springen uit het water op het pad. In principe kunnen ze in twee vervolgsprongen aan de andere zijde van het pad weer in het water springen, maar bij elke sprong kiest elke kikker of de kikker vooruit springt (met kans $p$) of achteruit springt (met kans $1 – p$). Als een kikker eenmaal in het water springt, onderneemt hij geen nieuwe poging. Nu blijkt precies de helft van de kikkers de andere kant van het pad te bereiken. Bepaal $p$.
Oplossing. Noem de kans die een kikker heeft om vanaf de eerste plek op het pad de overkant te halen $P_1$, en de kans die een kikker heeft om vanaf de tweede plek op het pad de overkant te halen $P_2$. Een kikker op de eerste plek heeft kans $1 – p$ om terug in het water te springen, waarna hij stopt, en kans $p$ om naar de tweede plek te gaan. Er geldt dus $P_1 = p · P_2$. Een kikker op de tweede plek heeft kans $1 – p$ om terug te springen naar de eerste plek, en kans $p$ om bij het andere water te komen. Daarom geldt $P_2 = p + (1 – p) · P_1$. We vinden nu dat $P_1 =
p · P_2 = p^2 + p(1 – p) · P_1$, oftewel $(1 – p(1 – p))P_1 = p^2$, dus $P_1 = p^2/(1 – p(1 – p))$. Gegeven is dat deze kans gelijk is aan ${1 \over 2}$ . Uitwerken geeft $p^2 = {1 \over 2} – {1 \over 2} p + {1 \over 2} p^2$. Het oplossen van deze tweedegraadsvergelijking geeft $p = {1 \over 2} (\sqrt5 – 1)$.

 

Aanvulling bij Oplossing 336

Bij opgave 336 vonden we 9 oplossingen, waarbij $a, b, c, d$ positieve, gehele getallen zijn. Staan we echter negatieve getallen toe, dan kunnen we meer oplossingen vinden, want dan hoeven de ongelijkheden die in de oplossing voorkwamen niet meer te gelden. We kunnen oneindig veel oplossingen genereren door de paren tweetallen $(0, –c^2), (c, –c)$ en $(–1, –d + 1), (–1, d)$, met $c, d$ willekeurige gehele getallen. Dit zijn de enige extra oplossingen die negatieve getallen geven (op het omwisselen van getallen en paren na). Dat zullen we bewijzen.
We beginnen weer met het afschieten van de grote gevallen. Indien $|a|, |b|, |c|, |d| ≥ 2$, dan is
$$|ab| = |a| · |b| ≥ |a| + |b| ≥ |a + b|.$$
Hieruit volgt
$$|abcd| = |ab||cd| = |c + d||a + b| ≤ |cd||ab| = |abcd|.$$
We gaan eerst het gelijkheidsgeval analyseren. Er geldt gelijkheid in $|ab| ≥ |a| + |b|$ als ten eerste $|a| = |b| = 2$ en ten tweede $a$ en $b$ hetzelfde teken hebben, dus als $a = b = 2$ of $a = b = –2$. Uit deze tweede conditie volgt dat we een tweetal $c, d$ zoeken met $c + d = ab = 4$ en $cd = a + b = –4$. Hieruit volgt dat $c$ en $d$ allebei oplossingen zijn van de vergelijking
$$0 = (x – c)(x – d) = x^2 – (c + d)x + cd = x^2 – 4x – 4.$$
Deze vergelijking heeft echter als oplossingen $x = 2 ± 2\sqrt2$, die geen van beide geheeltallig zijn, dus $c$ en $d$ kunnen nooit oplossingen van deze vergelijking zijn. Hieruit volgt dat $a = b = –2$ onmogelijk is, dus $a = b = 2$. Dan zijn $c$ en $d$ allebei oplossingen van
$$0 = (x – c)(x – d) = x^2 – (c + d)x + cd = x^2 – 4x + 4 = (x – 2)^2,$$ waaruit volgt $c = d = 2$. Dus zelfs als we negatieve getallen toestaan, is er alleen een triviale oplossing als $|a|, |b|, |c|, |d| ≥ 2$. We nemen daarom aan dat dat niet zo is: stel (zonder verlies van algemeenheid) dat $|a| < 2$. Dan is $a = 0, a = 1$ of $a = –1$.
Als $a = 0$, krijgen we als stelsel $0b = c + d$ en $b = cd$, dus $d = –c$ en $b = –c^2$. Dit geeft dus als oplossing $(0, –c^2), (c, –c)$, die voldoet voor alle gehele $c$.
Als $a = 1$, krijgen we $b = c + d$ en $b + 1 = cd$, en dit geeft (net als eerst) dat $(c – 1)(d – 1) = 2$. Het geval $c – 1 = 1, d – 1 = 2$ hebben we al bekeken. Nu is het echter mogelijk dat $2$ het product is van negatieve factoren. Is $c – 1 = –1, d – 1 = –2$, dan krijgen we $c = 0, d = –1, b = –1$, ofwel $(1, –1), (0, –1)$. Als we goed kijken, is dit de oplossing van het type dat we al hadden, met $c = 1$ en de twee paren omgewisseld. Dit levert dus geen nieuwe oplossingen op.
Als $a = –1$, krijgen we als stelsel $–b = c + d, b – 1 = cd$. Substitutie geeft $cd = –(c + d) – 1$, ofwel $cd + c + d + 1 = 0$, ofwel $(c + 1)(d + 1) = 0$. Dus ons stelsel heeft een oplossing als $c = –1$ of $d = –1$. Stel $c = –1$. Dan hebben we $d$ willekeurig, en $b = –d + 1$. Dit geeft dus $(–1, –d + 1), (–1, d)$ als oplossing. En daarmee hebben we alle oplossingen (op permutaties na) bepaald.