AIVD Kerstpuzzel #44 Editie 2024

quote:

Op zondag 12 januari 2025 17:42 schreef WitteIris het volgende:

[..]
Wellicht is het een idee om dat dit jaar hier eens uitgebreider na te bespreken? Ik denk dat het voor veel mensen inzichtelijk zou zijn hoe andere mensen vragen oplossen. Dat is iets wat je niet uit de uitwerkingen kunt halen; meestal geven ze enkel aan wat het antwoord is.

Voorstel: zullen we dat hier bespreken een week na de deadline? Dan kan iedereen nog even verder puzzelen met de hints die dan uitkomen, maar ik denk dat niet veel mensen nog verder puzzelen na die week, dus dat lijkt me een goed moment om hier lekker na te bespreken.

Bij sommige opgaves moet je maar net per ongeluk het juiste idee proberen, dus daar valt weinig aan uit te leggen. Maar ik kan hier wel af en toe van een aantal opgaves van deze en voorgaande kerstpuzzels een wat uitgebreidere uitleg geven hoe ik aan het antwoord ben gekomen.

Hoewel ik over het algemeen een potlood-en-papierpuzzelaar ben (22 heb ik met schaar en plakstift gedaan, om maar wat te noemen), vind ik het ook handig om sommige dingen met Python te automatiseren. Geavanceerd zoeken op Wikipedia kan bij een enkele opgave (meestal ook niet meer dan een enkele) tot een oplossing leiden. Je kan een dump van de Nederlandse wikipedia downloaden: https://dumps.wikimedia.o(...)ges-articles.xml.bz2 en met de volgende code doorlopen:


Bij opgave 25, als je eenmaal het idee loslaat dat het per se een stad moet zijn, kun je de aanname doen dat de bijnaam van hetgeen je zoekt ergens op de pagina van datgene staat (dus PAGINATITEL + WOORDEN IN BIJNAAM). Het is redelijk om aan te nemen dat het een combinatie van hooguit 3 woorden is die ergens in de eerste 500 woorden op de pagina staan (deze criteria kun je altijd wat verruimen in ruil voor een langere zoektijd). Als je de volgende code draait, staan er binnen een half uur of zo al een aantal antwoorden op je scherm:
En zo zijn er elk jaar wel een of twee opgaves waarbij dit soort zoekwerk kan helpen om het juiste antwoord te vinden.

[ Bericht 0% gewijzigd door thabit op 24-01-2025 17:35:10 ]

Hier volgt een uitleg van opgave 2022-18 (ik probeer even een random LaTeX-renderer die ik online heb gevonden, dus misschien ziet dit er helemaal ruk uit):

Gegeven zijn afschattingen:




Hoe moet 1507 x 1799 worden afgeschat?

Oplossing. Die bovenste trekt meteen de aandacht, want binnen de wortel staat een rij, hoogstwaarschijnlijk van priemgetallen, maar de wortel van een rij is wiskundig niet gedefinieerd. We moeten dus uitzoeken wat daarmee bedoeld wordt. Wat de wortel van een rij ook moge betekenen, als je het kwadrateert, dan zal de rij van priemgetallen er wel uit komen. Dus we kunnen eens kijken wat er gebeurt als we de 'afschatting' kwadrateren, vooral omdat er nog een wortel in de opgave staat lijkt dit wel handig om te doen: 167957152528323² = 28209605085422357111317192329.
Als je goed naar dit getal kijkt, dan zie je dat het eindigt op een aantal priemgetallen: 2357111317192329. Dat kan natuurlijk geen toeval zijn. Eens kijken of het met √π ook werkt: 884461443978422144813971621626560378² = 782272045884395574087950507512127653141592653589793238462643383279502884, en verrek, als je goed zoekt, zie je ergens wel 31415 zitten, en de cijfers daarna komen ook met decimalen van π overeen. De decimale punt moet je blijkbaar wegdenken.

Maar wat moeten we nu met e? Daar staat geen wortel in, en logaritmes lijken ook niks op te leveren. Misschien alsnog kwadrateren maar even proberen?
e² ≈ 7.38905609893065 en 88416² = 7817389056.
Dus daar zien we ook dat 7389056 het begin van het linkerdeel en het eind van het rechterdeel is. En ook bij die gekke breuk die daar staat werkt het (de vreemde notatie zal wel een themahint zijn die ik niet begrijp ).

Oké, nu weten we dus dat bij een 'benadering' x ≈ y, het begin van x² in decimale cijfers overeenkomt met het eind van y². Maar dan zijn we er nog niet, want er zijn doorgaans meerdere getallen y te bedenken die voldoen, dus welke moet het zijn?

Om dit te kunnen beantwoorden, moet je ten eerste weten hoe je herkent of een rij cijfers het eind van een kwadraat kan zijn (vanaf nu noemen we zo'n rij cijfers een kwadraatstaart), en ten tweede hoe je bij een kwadraatstaart getallen kunt vinden waarvan het kwadraat die staart heeft. Hiervoor gaan we modulo-rekenen: een getal/rij van n cijfers is een kwadraatstaart als het een kwadraat modulo 10ⁿ is. Het algemeen herkennen van kwadraten en trekken van wortels modulo m is een vrij uitvoerig onderwerp waar je meerdere topics over kan volposten, maar ik zal mijn uitleg kindergeschikt houden en beperken tot m=10ⁿ, het geval dat voor deze opgave van belang is.

Een getal is een kwadraat modulo 10ⁿ precies dan als het een kwadraat modulo 2ⁿ én een kwadraat modulo 5ⁿ is. Een getal is een kwadraat modulo 2ⁿ als het modulo 2ⁿ geschreven kan worden als 2^2m(8k+1). En je bent een kwadraat modulo 5ⁿ als je modulo 5ⁿ geschreven kan worden als 5^2m(5k±1). Dit geeft een volledige beschrijving van kwadraatstaarten, die je ook makkelijk kunt implementeren op de computer.

Een paar speciale gevallen zijn wel interessant om hier te noemen:
Een kwadraat moet op 0, 1, 4, 5, 6, of 9 eindigen.
Als een kwadraat op een 5 eindigt, moet het op 25 eindigen.
Als een kwadraat op een 0 eindigt, moet het op 00 eindigen.
Als het laatste cijfer van een rij niet deelbaar door 2 of 5 is, dan hoef je alleen maar naar de laatste 3 cijfers te kijken om te weten of het een kwadraatstaart is. Die laatste 3 cijfers moeten in dat geval een getal vormen dat 1 modulo 8, en 1 of 4 modulo 5 is.

Laten we eens kijken hoe dat zit met die priemgetallen:
2 is geen kwadraatstaart, want 2 modulo 5.
23 is geen kwadraatstaart, want 3 modulo 5.
235 is geen kwadraatstaart, want eindigt op 5 maar niet op 25.
2357 is 2 modulo 5, dus geen kwadraatstaart.
235711 is 7 modulo 8, dus geen kwadraatstaart.
23571113 is 3 modulo 5, dus geen kwadraatstaart.
2357111317 is 2 modulo 5, dus geen kwadraatstaart.
235711131719 is 7 modulo 8, dus geen kwadraatstaart.
23571113171923 is 3 modulo 5, dus geen kwadraatstaart.
2357111317192329 is 4 modulo 5 en 1 modulo 8, dus WEL een kwadraatstaart.
Aha, dat was ook de staart die we in de benadering zagen! Dus de EERSTE gelegenheid om een kwadraatstaart te hebben, is degene in de benadering in dit geval. Bij nadere inspectie blijkt dat ook in de andere gegeven benaderingen zo te zijn.

Goed, dat was het herkennen van kwadraatstaarten. Nu moeten we nog een bijbehorend getal vinden waarvan het kwadraat een gegeven staart heeft. Ofwel: we gaan worteltrekken modulo 10ⁿ. Modulair worteltrekken werkt net wat anders dan worteltrekken in ℝ. In ℝ zijn we gewend dat een kwadratische vergelijking hooguit 2 oplossingen heeft. Modulo priemgetallen is dat ook nog steeds het geval (al heeft het worteltrekken daar wel wat voeten in de aarde). Modulo samengestelde getallen kunnen er echter veel meer oplossingen zijn. De vergelijking x²=0 heeft in ℝ en modulo priemgetallen alleen x=0 als oplossing, maar modulo 100 zijn er 10 oplossingen: 0, 10, 20, 30, 40, 50, 60, 70, 80, 90. De vergelijking x²=1 heeft in ℝ alleen x=1 en x=-1 als oplossing. Modulo 1000 zijn er echter 8 oplossingen: 1, 249, 251, 499, 501, 749, 751, 999.

Er zullen voor een kwadraat modulo 10ⁿ dus in het algemeen meerdere wortels modulo 10ⁿ gevonden kunnen worden, maar hoe vinden we ze? Gelukkig is 10 een klein getal, dus we kunnen er met een botte bijl doorheen hakken (met een samurai-zwaard kan ook, maar dan blijft de uitleg niet meer kindergeschikt). We zoeken eerst alle wortels modulo 10; dit kan gewoon door alle cijfers 0 t/m 9 uit te proberen. We gaan dan per wortel kijken welke cijfers we ervoor kunnen plakken om een wortel modulo 100 te krijgen; ook dit kan gewoon door alle cijfers 0 t/m 9 uit te proberen. Daarna doen we hetzelfde om van wortels modulo 100 naar wortels modulo 1000 te gaan, etc, tot we de wortels modulo 10ⁿ te pakken hebben. Dit kun je allemaal makkelijk programmeren.

Laten we wederom het voorbeeld met de priemgetallen erbij pakken: de kwadraatstaart is 2357111317192329. Dat ding is 9 modulo 10, en de wortels modulo 10 in dit geval zijn dus 3 en 7. Als we nu naar modulo 100 gaan, moeten we dus kijken welke cijfers we voor 3 resp. 7 kunnen plakken om een wortel van 29 modulo 100 te krijgen. Daar blijken 4 mogelijkheden te zijn: 23, 73, 27, 77. Wortels van 329 modulo 1000 blijken er 8 van te zijn: 323, 823, 73, 573, 427, 927, 177, 677.
2329 modulo 10000 heeft ook 8 wortels: 3323, 8323, 4573, 9573, 427, 5427, 1677, 6677.
En zo kun je doorgaan tot je de wortels van 2357111317192329 modulo 10¹⁶ vindt: 167957152528323, 5167957152528323, 4502979125184573, 9502979125184573, 497020874815427, 5497020874815427, 4832042847471677, 9832042847471677.
De 'benadering' in de opgave zit hierbij en blijkt de kleinste van de wortels te zijn.

Deze procedure kun je ook op de andere voorbeelden toepassen, en telkens blijkt de 'benadering' het kleinste getal te zijn dat werkt. Dit had je misschien ook wel kunnen gokken, maar dat voelt toch wat onbevredigend. Voor de oplossing van de opgave moeten we dus 1507 x 1799 kwadrateren: daar komt 7350025254649 uit. Hierin is 7350025 de eerste kwadraatstaart. Er zijn 40 wortels modulo 10⁷, en 235005 is daarvan de kleinste.

[ Bericht 0% gewijzigd door thabit op 01-02-2025 11:40:08 ]