De opgave Een $\ell$-code is een geheel getal $n \ge 0$ van hoogstens $\ell$ cijfers, zonodig aangevuld met voorloopnullen, zodat het in totaal uit $\ell$ cijfers bestaat. Zo kun je van $310$ een $4$-code maken door het te schrijven als $0310$. Een $\ell$-code noemen we zelf-kwadratisch als de laatste $\ell$ cijfers van het kwadraat van die code precies de oorspronkelijke $\ell$-code vormen. Zo zijn de $1$-codes $5$ en $6$ zelf-kwadratisch, maar is de $3$-code $006$ niet zelf-kwadratisch, want $6^2 = 36 = 036$ eindigt niet op $006$. De $2$-code $76$ is wel zelf-kwadratisch, omdat $76^2 = 5776$ eindigt op $76$. $\color{blue}{A}$ Bewijs dat een $\ell$-code $n$ zelf-kwadratisch is dan en slechts dan als $n(n - 1)$ deelbaar is door $10\ell$. $\color{blue}{B}$ Bewijs dat elke zelf-kwadratische $\ell$-code $n \ge 2$ eindigt op het cijfer $5$ of het cijfer $6$. $\color{blue}{C}$ Bewijs dat elke zelf-kwadratische $\ell$-code $n \ge 2$ op precies één manier is uit te breiden tot een zelf-kwadratische $(\ell + 1)$-code door er een geschikt cijfer voor te plaatsen.

$\ell$-codes? Abstracte begrippen zoals deze kunnen afschrikken, maar rustig de tijd nemen om deze begrippen te snappen (en niet schrikken!) is hoe je aan zo'n opgave moet beginnen.

10-maChten

Ten eerste is het fijn om een $\ell$-code te zien als gewoon een getal met $\ell$ cijfers waarmee je kan optellen, aftrekken, vermenigvuldigen etc., net zoals ieder ander getal. Het enige verschil is dat een $\ell$-code n mag beginnen met nullen, zodat $n$ niet per se minstens $10\ell-1$ hoeft te zijn, maar ook een kleinere waarde mag hebben.

Daarnaast is het idee van zelf-kwadratisch best vaag: wat betekent het concreet als een getal eindigt op bepaalde cijfers? Kijk maar weer naar $76^2 = 5776$. Omdat we hier kijken naar een $2$-code, splitsen we $5776$ in de laatste twee cijfers $76$ en $5700$, waarbij $76$ gelijk is aan het getal waarmee we begonnen. Dat betekent dat $5776 - 76$ deelbaar is door $100 = 10^2$. Dit moet natuurlijk gelden voor iedere zelf-kwadratische $2$-code: het kwadraat van de code min de code zelf moet eindigen op $2$ nullen, oftewel deelbaar zijn door $10^2$, want anders zullen de laatste $2$ cijfers van het kwadraat niet overeenkomen met de $2$-code. Hierboven heb ik het over een $2$-code, maar dit patroon bestaat voor alle waardes van $\ell$, behalve dat we het dan hebben over de laatste $\ell$ cijfers en deelbaarheid door $10^\ell$.

Met een volledig begrip van wat zelf-kwadratisch echt inhoudt is het gevraagde bij onderdeel $\color{blue}{A}$ eigenlijk erg vanzelfsprekend. Er geldt dat $n(n - 1) = n^2 - n$, maar dat is gewoon het verschil tussen het kwadraat van een $\ell$-code en de code zelf, en we hebben zojuist gezien dat dat deelbaar moet zijn door $10\ell$ als de code zelf-kwadratisch is!

Wel opgelet: hier wordt er gevraagd om een dan en slechts dan relatie aan te tonen. We moeten dus ook het omgekeerde bewijzen: als $n(n - 1)$ deelbaar is door $10^\ell$, is $n$ zelfkwadratisch. Gelukkig is het omgekeerde bij deze opgave niet lastiger te bewijzen: als $n^2 - n$ deelbaar is door $10^\ell$, eindigt dat getal op $\ell$ nullen. Als we dus $n$ bij $n^2 - n$ optellen om weer $n^2$ te maken, zullen de laatste cijfers precies overeenkomen met de cijfers van het getal $n$, dat $\ell$ cijfers lang is. Hiermee is $\color{blue}{A}$ opgelost.

Voortbouwen en getallen opdelen

In de wiskunde worden nieuwe stellingen en formules gevonden en bewezen op basis van voorgaande resultaten. Bij $\color{blue}{B}$ moeten we precies dat gaan doen. Neem een  willekeurige zelf-kwadratische $\ell$-code $n$. Het is meteen duidelijk dat $n$ eindigt op $0$, $1$, $5$ of $6$, omdat alleen dan geldt dat $n^2$ eindigt op hetzelfde cijfer. We moeten bewijzen dat het moet eindigen op $5$ of $6$. Uit A weten we dat $n(n - 1)$ deelbaar is door $10^\ell$. Voor mij was dit gelijk interessant omdat $n$ en $n - 1$ zogenaamd copriem zijn: ze hebben geen niet-triviale delers met elkaar gemeen. Want als $n$ deelbaar is door een getal $d > 1$, dan is $n - 1$ dat niet, en vice versa.

We weten dus dat $n(n - 1)$ deelbaar is door $10^\ell$ en dat de factoren $n$ en $n - 1$ geen priemdelers gemeenschappelijk hebben. Met deze kennis wordt de volgende vraag interessant: is het mogelijk dat $n$ of $n - 1$ deelbaar is door $10$? Als de ene factor dat is, kan de andere namelijk niet deelbaar zijn door $10$. Laten we bekijken wat er gebeurt als $n$ dat is. Dan is $n$ gelijk ook deelbaar door $10^\ell$, want $n - 1$ is dan niet deelbaar door $10$ terwijl $n(n - 1)$ wel $\ell$ factoren $10$ moet bevatten. Hieruit volgt dat $n$ uit $\ell$ nullen bestaat, dus gelijk is aan $0$ terwijl $n \ge 2$. In de wiskunde noemen we deze situatie een tegenspraak: twee uitspraken die niet tegelijkertijd waar kunnen zijn. Hiermee hebben we bewezen dat $n$ niet deelbaar is door $10$. Hetzelfde verhaal gaat op voor $n - 1$: als het getal deelbaar was door $10$, zou het bestaan uit $\ell$ nullen en zou $n = (n - 1) + 1$ gelijk zijn aan $1$, terwijl $n \ge 2$. Alweer leidt dit tot een tegenspraak.

We kunnen dus de conclusie trekken dat $n$ en $n - 1$ beide niet deelbaar zijn door $10$. Maar toch moet hun product deelbaar zijn door $10$, wat gelijk is aan $2 \cdot 5$. Deze getallen kunnen niet meer opgedeeld worden in kleinere getallen, dus $n$ moet deelbaar zijn door $5$ en $n - 1$ door $2$, of juist andersom.

Stel dat $n$ deelbaar is door $5$. Dan is het niet deelbaar door $2$, dus het is oneven. Je hebt waarschijnlijk ooit opgemerkt dat alle veelvouden van $5$ eindigen op $5$ of $0$, maar aangezien $n$ oneven is, eindigt $n$ hier op $5$. Stel nu dat juist $n - 1$ deelbaar is door $5$ en dus niet door $2$. Dan eindigt $n - 1$ op $5$, dus $n = (n - 1) + 1$ eindigt op $6$. Hiermee is $\color{blue}{B}$ gelijk opgelost.

Onbekenden namen geven

Onderdeel $\color{blue}{C}$ kan, net zoals $\color{blue}{B}$, opgelost worden door voort te bouwen op $\color{blue}{A}$. Alleen is hier minder duidelijk hoe de gegevens gebruikt kunnen worden. We gebruiken dan een andere truc: we verzinnen gewoon een nieuwe zelf-kwadratische code met lengte $\ell+1$ die bestaat uit een onbekend cijfer $c$ en een zelf-kwadratische $\ell$-code $n$ daarachter. Deze $(\ell+1)$-code noemen we $m$; dit is precies de uitbreiding van $n$ waarnaar gevraagd wordt. We moeten nu bewijzen dat er precies één manier is om $m$ te bouwen, dus dat er een $c$ is die voldoet. Bekijk eerst de vorm van onze $(\ell+1)$-code: die bevat sowieso $n$, de originele $\ell$-code, en $c$ is dan het voorste cijfer, dus op plaats $\ell+1$. Dat komt overeen met de waarde $10^\ell \cdot c$. Dus $m = 10^\ell \cdot c + n$. Hoe kunnen we nu bewijzen dat er precies één $c$ is die voldoet? Een effectieve strategie is om te kijken naar de voorwaarde(n) waaraan die verzonnen dingen moeten voldoen om informatie over die dingen te verkrijgen. Bij deze opgave moet $m$ voldoen aan de voorwaarde bewezen in $\color{blue}{A}$: $m(m - 1)$ moet deelbaar zijn door $10^{\ell+1}$.

Spelen met algebra

We schrijven $m(m - 1)$ eerst uit:

$$m(m - 1) = (10^\ell \cdot c + n)\left(10^\ell \cdot c + (n - 1)\right) = 10^{2\ell}\cdot c^2 + 10^\ell \cdot c(n - 1) + 10^\ell \cdot cn + n(n - 1).$$

Duidelijk is de eerste term van de tweede regel al deelbaar door $10^{\ell+1}$, het is namelijk zelfs deelbaar door $10^{2\ell}$. Volgens $\color{blue}{A}$ is $n(n - 1)$, net zoals de middelste twee termen, ook deelbaar door $10^\ell$. Nu moeten we alleen nog bewijzen dat er maar één $c$ is waarvoor de som van die laatste drie termen zelfs deelbaar is door $10^{\ell+1}$. Anders geformuleerd moet dat stuk deelbaar zijn door $10$ nadat het gedeeld is door $10^\ell$, zodat het in totaal $\ell + 1$ keer deelbaar is door $10$.

Dit schrijven we weer uit:

$$\frac{10^\ell\cdot c(n-1)+10^\ell\cdot cn+n(n-1)}{10^\ell}=c(n-1)+cn+\frac{n(n-1)}{10^\ell}=c(2n-1)+\frac{n(n-1)}{10^\ell}.$$

Je weet vanwege $\color{blue}{A}$ dat $n(n-1)$ deelbaar is door $10^\ell$, dus de breuk $\frac{n(n – 1)}{10^\ell}$ heeft een gehele uitkomst. Die uitkomst noemen we even $d$ voor de duidelijkheid. Je krijgt dan dat $c(2n-1) + d$ deelbaar door $10$ moet zijn. Nu komt $\color{blue}{B}$ te hulp: $n$ moet eindigen op $5$ of $6$, dus $2n$ eindigt op $0$ of $2$. Daardoor eindigt $2n - 1$ op $9$ of $1$.

Kijk eerst naar het geval wanneer $2n - 1$ eindigt op $1$. Dan eindigt $c(2n - 1)$ op $c$, dus we kunnen $c(2n - 1) + d$ schrijven als $10k + c + d$, waarbij $k$ gelijk is aan $c(2n - 1)$ met het laatste cijfer afgeknipt. Omdat $10k$ al deelbaar is door $10$, moet $c + d$ nog deelbaar zijn door $10$ zodat de hele uitdrukking dat ook is. Er zijn in totaal $10$ opties voor $c$, namelijk $0, 1, 2, \dots , 9$. Deze leveren tien opeenvolgende opties voor $c + d$, namelijk $0 + d, 1 + d, 2 + d, \dots , 9 + d$. En nu komt de doorslaggevende observatie: van tien opeenvolgende getallen is precies één daarvan deelbaar door $10$. Hierdoor is er precies één mogelijkheid voor $c$ waarvoor $c + d$ deelbaar is door $10$, dus precies één $c$ om $n$ uit te breiden tot $m$.

Er blijft nog één geval over. Als $2n - 1$ eindigt op $9$, eindigt $c(2n - 1)$ op het laatste cijfer van $9c$. Dit kunnen we even $x$ noemen. De tafel van $9$ ken je vast nog. Daaruit blijkt dat $x$ ook precies alle cijfers uit $0, 1, 2, \dots , 9$ doorloopt als je $c$ varieert. Hetzelfde argument volgt nu: $c(2n - 1) + d$ is te schrijven als $10k + x + d$ en er is precies één $x$ waarvoor dit deelbaar is door $10$, en ook weer precies één $c$ die deze $x$ oplevert als je het in $9c$ invoert. Hiermee is het bewijs voor $\color{blue}{C}$ afgerond; we hebben in alle gevallen bewezen dat er precies één $c$ is om $n$ uit te breiden tot $m$.

Terugblik

Dat was even flink door puzzelen. Je mag trots zijn op jezelf dat je doorgebeten hebt tot het einde. De moeilijkheid bij abstracte opgaven zoals deze is dat je geen sterke intuïtie hebt over de gegevens. Zoals hier getoond is, helpt het vaak om concreet te zijn over wat er gegeven wordt. Daarmee kan je dan het onbekende verkennen.