De opgave Emma verkoopt online kaarsen, en op haar website kun je grote dozen vol kaarsen, of kleine dozen bestellen. Er zitten niet meer dan $20$ kaarsen in een doos. Op een dag krijgt ze een bericht van een klant die precies $25$ kaarsen wil kopen, maar klaagt dat dit niet mogelijk is door een geschikte combinatie van grote en kleine dozen te kopen. Emma reageert dat dit wel mogelijk is voor elk aantal kaarsen dat groter is dan $25$. Hoeveel kaarsen zitten er in een grote doos?

Laten we eens proberen of we deze opgave op kunnen lossen! Noem het aantal kaarsen in de kleine doos k, en het aantal kaarsen in de grote doos $g$. We weten dat het niet mogelijk is om een aantal grote en kleine dozen te kopen om $25$ kaarsen te krijgen, dus er bestaan geen gehele getallen $a \ge 0$ en $b \ge 0$ zodat $ak + bg = 25$. Aan de andere kant bestaan er voor elk getal $s > 25$ wel geschikte $a$ en $b$ zodat $ak + bg = s$.

Een goede manier om zo'n opgave aan te pakken is door wat kleine gevalletjes uit te proberen. We kunnen meteen zien dat $k = 1$ niet kan, omdat je dan met alleen kleine dozen al $25$ kaarsen kunt kopen. Hetzelfde is het geval voor alle delers van $25$, dus het is ook niet mogelijk dat een doos $5$ kaarsen bevat.

Laten we dan eens kijken wat er gebeurt als er $2$ kaarsen in een kleine doos zitten. Door even na te denken, kunnen we zien dat $g$ nu geen even getal mag zijn, omdat we dan nooit oneven getallen boven de $25$ kunnen bereiken. Hieruit kunnen we meteen een belangrijke algemene observatie maken: de getallen $k$ en $g$ mogen geen gemeenschappelijke deler hebben, want anders kunnen we nooit getallen bereiken die geen veelvoud van die gemeenschappelijke deler zijn. Overigens kunnen we hierna zien dat $k = 2$ geen optie is: als $g \le 20$ oneven is, is deze $g$ maar een even aantal verwijderd van $25$, dus in dit geval zou $25$ wel een mogelijke combinatie zijn, en dat mag niet. (De eis dat $g \le 20$ is hierbij essentieel; anders zouden we voor $k = 2$ wel $g = 27$ kunnen nemen; dan is elk aantal vanaf $26$ te maken en $25$ niet.)

Het zou best een tijdje kunnen duren om alle mogelijkheden langs te gaan, dus laten we hier eens op een andere manier naar kijken. Het moet mogelijk zijn om elk getal groter dan $25$ te vormen, zoals $26$. Er zijn meerdere opties: of we gebruiken alleen maar kleine dozen (in welk geval $k$ een deler is van $26$), of we gebruiken één grote doos en verder kleine dozen (wat betekent dat k het getal $26 - g$ deelt), of we gebruiken twee grote dozen, enzovoort. Maar: als g groot genoeg is, namelijk als twee grote dozen meer is dan het aantal dat we willen vormen, dan zijn er maar twee opties: nul of één grote dozen. Nu is het getal $26$ niet zo handig, omdat dit getal zelf ook meerdere delers heeft. Maar toevallig zijn er twee priemgetallen in de buurt, namelijk $29$ en $31$, dus laten we daar eens beter naar kijken. Zonder grote dozen is het namelijk niet mogelijk om de priemgetallen $29$ en $31$ te vormen, aangezien de kleine doos minder dan $20$ kaarsen bevat. En als $g \ge 15$, dan is het ook niet mogelijk om twee grote dozen te gebruiken, want $k$ kon geen $1$ zijn. Daarmee concluderen we dat als $g$ groter is of gelijk aan $15$, dat we dan vinden dat $29 = ak + g$ en $31 = a’k + g$ voor bepaalde getallen $a \ge 0$ en $a' \ge 0$. We kunnen deze twee vergelijkingen van elkaar afhalen en vinden dat $2 = (a’ - a)k$, wat betekent dat $k$ een deler is van $2$. Maar we hadden juist gezien dat $k$ niet gelijk aan $1$ of $2$ kan zijn! Dit betekent dus dat $g$ kleiner moet zijn dan $15$.

Hoe zit het dan met het geval $g = 14$? Nu is het mogelijk om $31$ te krijgen met behulp van twee grote dozen, maar dat betekent wel dat $k$ gelijk moet zijn aan $3$. Bovendien is het met deze twee getallen mogelijk om het priemgetal $29 = 5 \cdot 3 + 14$ te vormen. De vraag is of we hiermee alle getallen boven de $25$ kunnen maken. Dit is inderdaad het geval: alle veelvouden van $3$, dus alle getallen van de vorm $3n$ (en dus in het bijzonder $27, 30, 33, \dots$) kunnen met louter kleine dozen gemaakt worden; alle getallen van de vorm $3n + 2$ vanaf de $14$ (en dus in het bijzonder $26, 29, 32, \dots$) kunnen met één grote doos en verder kleine dozen gemaakt worden, en alle getallen van de vorm $3n + 1$ vanaf de $2 \cdot 14 = 28$ (dus $28, 31, 34, \dots$) kunnen met twee grote dozen en verder kleine dozen gemaakt worden. En omdat we nu precies weten welke getallen er wel gemaakt kunnen worden, zien we ook dat het getal $25$ uitgesloten, precies zoals we wilden. Dus het antwoord op de opgave is dat een grote doos precies $14$ kaarsen bevat.

De vraag is natuurlijk of dit de enige oplossing is. Dit kunnen we wel verwachten als we kijken naar de vraagstelling, maar dat is natuurlijk geen bewijs. Gelukkig voor de deelnemers is dit een opgave van de JWO en is alleen een eindantwoord voldoende; maar het is natuurlijk wel interessant om hiernaar te kijken. Om de gevallen $k = 4$ en $k = 6$ af te schieten, kunnen we weer slim de priemgetallen $29$ en $31$ gebruiken: omdat deze getallen priem zijn en een grote doos maximaal $20$ kaarsen bevat, weten we dat er om deze getallen te krijgen minstens één kleine doos nodig is. Aan de andere kant is het (volgens het gegeven) niet mogelijk om $29 - 4 = 25$ en $31 - 6 = 25$ te krijgen. Dus deze gevallen vallen af. Het kost iets meer moeite om alle gevallen $k = 7, 8, 9, 10, 11, 12$ langs te gaan, maar bij al deze getallen zijn er twee getallen boven de $25$ te vinden die een verschillend aantal kaarsen in de grote doos nodig hebben. Ik nodig je vooral uit om dit zelf te proberen en te zien waarom dit niet kan!

Nu is het natuurlijk ook nog interessant om naar het algemene geval te kijken. Stel, we hebben een doos met $k$ kaarsen en een andere doos met $g$ kaarsen, waarbij $k$ en $g$ geen gemeenschappelijke deler hebben. Vanaf welk getal kunnen we dan alle mogelijke combinaties krijgen? Het antwoord hierop wordt gegeven door een stelling die ook wel de Chicken McNugget stelling wordt genoemd: als je bakjes hebt met $k$ kipnuggets, en een ander type bakje met telkens $g$ kipnuggets, dan is het mogelijk om elk aantal vanaf $(k - 1) \cdot (g - 1)$ te vormen door meerdere bakjes te combineren. Het is echter niet mogelijk om het getal $(k - 1) \cdot (g - 1) - 1 = kg - k - g$ te krijgen. En dat zien we hier ook: met $k = 3$ en $g = 14$ krijgen we dat elk getal vanaf $(3 - 1) \cdot (14 - 1) = 26$ te behalen is, terwijl dat niet het geval is voor $25$ zelf. Merk op dat omgekeerd de vergelijking $(k - 1) \cdot (g - 1) = 26 = 2 \cdot 13$ maar twee oplossingen met $k < g$ heeft: deze oplossing $k = 3$ en $g = 14$ en daarnaast nog de eerder genoemde oplossing $k = 2$ en $g = 27 > 20$.

Het idee hierachter is als volgt. We kijken naar de reeksen getallen $kn, kn + g, kn + 2g, kn + 3g, \dots, kn + (k - 1)g$ voor gehele getallen $n \ge 0$. In de opgave hadden we de reeksen $3n, 3n + 14$ en $3n + 28$, wat we ook kunnen opschrijven als $3n, 3n + 2$ en $3n + 1$ als $n$ groot genoeg is. In het algemene geval kan er op een vergelijkbare manier worden bewezen dat elk mogelijk getal vanaf $(k - 1) \cdot (g - 1)$ kan worden gemaakt. Dan is er nog de vraag waarom het getal daar eentje onder, namelijk $kg - k - g$, niet kan worden gemaakt; stel dat dit wel het geval is en we $kg - k - g = ak + bg$ kunnen schrijven voor gehele getallen $a \ge 0$ en $b \ge 0$, dan krijgen we $(g - a - 1) k = (b + 1)g$. We weten dat $k$ en $g$ geen gemeenschappelijke delers hebben, dus $g$ is een deler van $g - a - 1$. Maar omdat de rechterkant $(b + 1)g$ positief is, weten we ook dat $g - a - 1$ positief is en kleiner dan $g$, dus dit is niet mogelijk.