Opgave 5, Finale Nederlandse Wiskunde Olympiade 2020 Sabine heeft een heel grote schelpenverzameling. Ze besluit een deel van haar schelpen aan haar zusje te geven. De eerste dag legt ze al haar schelpen op een lange rij en geeft vervolgens elke schelp die op een kwadraatpositie in de rij ligt (dus de eerste, de vierde, de negende, de zestiende, enzovoorts) aan haar zusje. De tweede dag maakt ze van de overgebleven schelpen weer zo’n lange rij en opnieuw geeft ze elke schelp die op een kwadraatpositie ligt aan haar zusje. Ze herhaalt dit proces elke dag.  Het blijkt dat ze op de 27ste dag voor het eerst minder dan $1000$ schelpen overhoudt en dat het op de 28ste dag voor de tiende keer gebeurt dat het aantal schelpen dat ze overhoudt precies een kwadraat is. Wat zijn de mogelijke aantallen schelpen waarmee Sabine begonnen kan zijn?

 

Dit is een lastige opgave om aan te beginnen. We lijken nog niet veel meer te weten dan dat Sabine erg vaak naar het strand moet zijn gegaan. Wat dan goed kan helpen, is uitproberen wat er gebeurt met kleine schelpenverzamelingen, bijvoorbeeld van $25$ schelpen. Van die verzameling geeft Sabine de schelpen op plek $1$, $4$, $9$, $16$ en $25$ weg en houdt er nog $20$ over. Dat lijkt nog niet echt interessant, maar in de opgave geeft Sabine meerdere keren een deel van haar verzameling weg. Laten we dus verder rekenen: op de tweede dag geeft ze schelpen $1$, $4$, $9$ en $16$ weg en heeft er dan nog $16$, precies genoeg om op de derde dag weer vier schelpen te moeten weggeven. Van de twaalf die ze zo overhoudt, geeft ze er drie weg. Na vier dagen heeft Sabine dus nog negen schelpen over.

Dat is toevallig: $9$ is net als $16$ en $25$ een kwadraat. Sabine lijkt dus elke twee dagen een kwadraat aantal schelpen te hebben. Interessant, want in de opgave is gegeven dat Sabines schelpenverzameling op dag 28 voor de tiende keer uit een kwadraat aantal schelpen bestaat. Het is dus fijn als we weten wanneer het aantal schelpen in de verzameling een kwadraat is. Werkt ons patroon van om-en-om een kwadraat ook voor grotere verzamelingen? Dat lijkt wel zo te zijn: als Sabine begint met $100$ schelpen, dan heeft ze na twee dagen $81$ en na vier dagen nog $64$ schelpen. Zelfs vanaf $900 = 30^2$ schelpen gaat Sabine via $870$ naar $841 = 29^2$ schelpen.

Het patroon bewijzen

Met deze grote getallen hebben we, misschien onterecht, genoeg vertrouwen gekregen om ons patroon te bewijzen. Stel dat Sabine $n^2$ schelpen heeft, met $n$ minstens twee. Hoeveel schelpen geeft ze dan weg? Dat zijn natuurlijk precies de n schelpen op plekken $1 = 1^2, 4 = 2^2, 9 = 3^2, \cdots, (n - 1)^2$ en $n^2$. Ze houdt er dan nog $n^2 - n = n(n - 1)$ over. Dit is duidelijk kleiner dan $n^2$, maar nog wel meer dan $(n - 1)(n - 1) = (n - 1)^2$. Op de tweede dag gaat Sabine dus schelpen $1^2, 2^2, \cdots, (n - 1)^2$ weggeven en houdt er $n^2 - n - (n - 1) = n^2 - 2n + 1$ over. Gelukkig was ons vertrouwen niet voor niets, want dat is inderdaad $(n - 1)^2$. Het aantal schelpen gaat dus van een kwadraat in twee dagen naar het eerstvolgende kleinere kwadraat. Zoals we al hoopten, wordt het nu ineens interessant dat op dag 28 het aantal schelpen een kwadraat is. We kunnen namelijk afleiden wat de eerste dag is waarop Sabine een kwadraat aantal schelpen had. Dit moet wel dag 10 zijn, want als dag $x$ deze eerste 'kwadraatdag' was, dan was de tweede op dag $x + 2$, de derde op dag $x + 4$ en zo doortellend de tiende, wat dag 28 was, op dag $x + 18$.

Minder dan 1000 schelpen

Kunnen we misschien nu ook het andere gegeven gebruiken? Dat zegt dat Sabine op dag 27 voor het eerst minder dan $1000$ schelpen had (de vloer van haar kamer
komt inmiddels weer in zicht). Stel dat Sabine op dag 10, de eerste 'kwadraatdag', $a^2$ schelpen had. Dan zien we negen keer twee dagen later dat ze op dag 28 in totaal $(a - 9)^2$ schelpen had. Op dag 27 en dus ook dag 28 had Sabine minder dan $1000$ schelpen, dus we vinden $(a - 9)^2 < 1000$. Aan de andere kant had ze op dag 26, toen ze nog $(a - 8)^2$ schelpen had, juist nog minstens $1000$ schelpen. Met wat gereken vinden we $a = 40$, dan geldt namelijk $(a - 8)^2 = 32^2 = 1024$ en $(a - 9)^2 = 31^2 = 961$. Op dag 27 heeft Sabine nu inderdaad een verzameling van nog 'maar' $1024 - 32 = 992$ schelpen over.

Inmiddels weten we al een stuk meer over de opgave: op dag 10 had Sabine precies $40^2 = 1600$ schelpen in haar verzameling. Helaas hebben we nu niet zoveel meer  aan ons kwadratenpatroon: op alle eerdere dagen is het aantal schelpen geen kwadraat. Er zit dus niets anders op dan nog wat meer patroontjes te gaan vinden. Om ons veel rekenwerk te besparen gaan we van de indrukwekkende aantallen schelpen van Sabine weer terug naar onze vertrouwde $25$. Wat gebeurt er als Sabine een paar schelpen tekort komt voor een kwadraat? Als Sabine $24$ schelpen heeft, dan geeft ze er vier weg. Dan heeft ze, net als vanaf $25$ schelpen, nog $20$ schelpen. Na de tweede dag heeft ze dan dus ook $16$ schelpen en zit ze in ons kwadraat-patroontje. Begint ze met $23 = 5^2 - 2$, dan heeft ze na twee dagen $15$, een kwadraat min één. Vanaf een kwadraat min $x$ lijken we dus in twee dagen naar een kwadraat min $x - 1$ te gaan. Werkt dat voor alle $x$? Nee, met wat uitproberen vinden we al snel dat het patroontje niet meer klopt bij bijvoorbeeld $4^2 - 5, 5^2 - 6$ en $6^2 - 7$. Dit komt doordat Sabine in deze gevallen in twee dagen een schelp minder moet weggeven: vanaf $6^2 - 6$ belandt ze bijvoorbeeld via $5^2$ op $5^2 - 5$. Anderzijds krijgt ze vanaf $6^2 - 7$ eerst $5^2 - 1$, waarna ze dus nog maar $4$ schelpen weggeeft en er ook $5^2 - 5$ overhoudt, in plaats van de $5^2 - 6$ die we hadden verwacht. Voor $x$ hoogstens even groot als het getal waarvan we het kwadraat nemen lijkt het patroon gelukkig steeds wel te werken. Misschien kunnen we nu het patroon bewijzen dat $n^2 - x$ in twee dagen naar $(n - 1)^2 - (x - 1)$ gaat? 

Stel dat Sabine op een dag $n^2 - x$ schelpen heeft, met $1 \le x \le n$. Dit zijn er minstens $n^2 - n \ge n^2 - 2n + 1 = (n - 1)^2$, maar minder dan $n^2$. Sabine geeft dus $n - 1$ schelpen weg en houdt er $n^2 - n - x + 1$ over. Dit is vanwege $x \le n$ weer minstens $n^2 - 2n + 1$, Sabine geeft dus ook nu $n - 1$ schelpen weg. In totaal heeft ze er dan nog $n^2 - 2n - x + 2$. Leuk genoeg kunnen we dat ook wel schrijven als $n^2 - 2n + 1 - x + 1 = (n - 1)^2 - (x - 1)$, precies het patroontje dat we wilden bewijzen! Nu is het niet meer zo lastig om een aantal schelpen te vinden dat na tien dagen op $40^2$ schelpen uitkomt: vanaf $41^2 - 1$ schelpen gaan we in twee dagen naar de $40^2 - 0$ schelpen van dag 10. Op dag 8 zouden we dus $41^2 - 1$ schelpen kunnen hebben en om dezelfde reden op dag 6 nog $42^2 - 2$. Zo doortellend volgens het patroon, vinden we dat Sabine aan het begin $45^2 - 5$ schelpen kan hebben gehad.

Alle mogelijke aantallen

Voor wie nu juichend op de bank zit, heeft Sabines reusachtige schelpenverzameling helaas (of gelukkig, net hoe je het bekijkt) nog een verrassing in petto: we moeten niet maar één, maar alle mogelijke beginaantallen voor Sabines schelpenverzameling vinden. Gelukkig is dat met de hulp van onze patroontjes niet heel moeilijk meer.

Stel dat Sabine met meer dan $45^2 - 5$ schelpen begint. Vanaf $45^2 - 4$ hebben we wel na tien dagen $40^2$, maar na acht dagen $41^2 - 0$ schelpen. Dat mag niet: dag 10 was de eerste 'kwadraatdag'. Ook $45^2 - 3$ tot en met $45^2$ komen te vroeg op een kwadraat uit. Maar we geven niet op: $45^2 + 1$ werkt vast. Voor kwadraten plus een beetje  hebben we geen patroon besproken (dat is er trouwens wel, probeer het maar eens te vinden), maar met wat telwerk vinden we dat we na 10 dagen $40^2 + 1$ schelpen  hebben. Dat is juist te veel. Werkt het met nog meer? Nee, zien we: als Sabine op een dag met meer schelpen begint, dan heeft ze er na die dag ook minstens evenveel. Als ze namelijk $c$ extra schelpen heeft, dan zullen daar hoogstens $c$ extra kwadraten bijzitten en geeft ze hoogstens $c$ extra schelpen weg. Als Sabine met meer dan $45^2 + 1$ schelpen begint, zal ze dus na dag 1 minstens evenveel schelpen hebben. Maar nu kunnen we hetzelfde argumentje weer toepassen: ook op dag 2 en, zo doorredenerend, dag 10 heeft ze minstens evenveel schelpen als wanneer ze met $45^2 + 1$ schelpen was begonnen. Ook als Sabine met meer dan $45^2 + 1$ schelpen begint, zal ze er dus op dag 10 te veel hebben. Alle beginaantallen groter dan $45^2 - 5$ vallen daarom af.

Werkt het wel met minder dan $45^2 - 5$ schelpen? Stel dat Sabine met maar $45^2 - 6$ schelpen zou beginnen, dan heeft ze er volgens het patroon na 10 dagen maar $40^2 - 1$; dat is te weinig. Ook nog minder schelpen gaat haar nu niet helpen, want we kunnen ons argument van hierboven gewoon omgekeerd gebruiken: als Sabine op een dag met minder schelpen begint, zal ze na die dag hoogstens evenveel schelpen hebben. Ook alle beginaantallen kleiner dan $45^2 - 5$ vallen dus af, Sabine moet precies $45^2 - 5$ schelpen hebben gehad. Met twee gegevens waar we eerst helemaal niets mee konden, hebben we dus leuk genoeg precies de begingrootte van Sabines enorme schelpenverzameling bepaald! En wie nog niet genoeg verrassingen heeft ontdekt in deze uit de hand gelopen verzameling, moet maar eens uitrekenen
hoeveel die $45^2 - 5$ eigenlijk is...