Kan iemand me helpen met dit vraagstuk?

Joyce, 17 jaar
3 november 2011

Hallo,
Ik ben Joyce en ik zit op 6 gymnasium en ik doe mijn profielwerkstuk over wiskunde. Ik maak opgaves uit het boekje ''Spelen en Delen'' door Frank Thuijsman. Ik zit echter met een vraagstuk waarmee ik en mijn wiskundeleraar niet uit de voeten komen. Ik hoop dat u mij de theorie achter mijn volgende vraag kan uitleggen of misschien zelfs wel kan helpen met het antwoord. (mischien kent u wel iemand die me hier anders mee kan helpen?!)
De opgave luidt alsvolgt:

Stel dat x en y twee positieve gehele getallen zijn, en dat x groter of gelijk is aan y. De som van de twee getallen (x+y), wordt doorgegeven aan Anna, terwijl de som van de kwadraten van de twee getallen (x²+y²), wordt doorgegeven aan Bob. Anna en Bob weten allebei dat Anna het getal x+y kent en Bob het getal x²+y² en ze weten ook van elkaar dat de ander dit weet. Vervolgens gaan Anna en Bob met elkaar praten. Het gesprek loopt als volgt:
1: Bob zegt: ''Ik weet niet welke getallen x en y zijn.''
2: Anna zegt: ''Ik weet niet welke getallen x en y zijn.''
3: Bob zegt:'' Ik weet niet welke getallen x en y zijn.''
4: Anna zegt:''Ik weet niet welke getallen x en y zijn.''
5: Bob zegt: ''Ik weet niet welke welke getallen x en y zijn.''
6: Anna zegt: ''Ik weet niet welke getallen x en y zijn.''
7: Bob zegt: ''Nu weet ik welke getallen x en y zijn!''
Om welke getallen x en y gaat het?
(hint: beperk je eerst tot de getallen x en y die elk kleiner zijn dan 25 zijn en kijk daarna of je kunt aantonen dat deze beperking geen invloed heeft op de uitkomst van het probleem.)

Er staat wel bij vermeld dat deze opgave ook is gepubliceerd in Mathematics Magazine 57, 180-181,1984; T.S Ferguson

Alvast hardstikke bedankt!

Antwoord

Hallo Joyce,

dit is een "raadseltje" met beperkte recursie. Het systeem is dat elke keer Anna of Bob zeggen dat ze het niet weten, alle mogelijkheden die ze tot dan toe exploreerden uitlopen op twee of meerdere mogelijkheden.  elke keer ook verdubbelen de mogelijkheden (hoewel in de praktijk vele mogelijkheden gewoon terugkomen). Wanneer Bob zegt dat hij het nu wel weet, betekent dit dat één van de mogelijkheden uniek wordt, en zodoende kan uitgesloten worden omdat anders Anna dit al zou geweten hebben. Dus we zoeken een situatie waarin Anna meerdere mogelijkheden heeft, maar Bob maar één.

Ik zal proberen de juiste oplossing niet te verklappen, maar na mij uitleg zou je het zelf moeten kunnen vinden. Je mag me altijd mailen om me te laten bevestigen dat je antwoord juist is (of om nog meer uitleg of zo) op hvm@cage.UGent.be

Ik weet niet hoeveel je er al op geredeneerd hebt, dus je zult wel dingen herkennen, maar ik zal toch van in het begin beginnen. 

Bob krijgt dus de som van twee kwadraten, zegge x^2+y^2. Het feit dat hij niet weet wat x en y zijn, wil zeggen dat deze som nog op een andere manier te schrijven is als de som van twee kwadraten. Anna krijgt de som x+y. Het feit dat zij niet weet wat x en y zijn, betekent dat er twee "ontbindingen" van x+y zijn waarvoor de som der kwadraten op meer dan één manier als som van kwadraten te schrijven valt. Het feit dat Bob dan nog niet weet over welke getallen het gaat betekent dat voor minstens twee van de mogelijkheden voor de getallen waarvan de som der kwadraten zijn getal geven de eigenschap geldt dat minstens twee ontbindingen van de som zijn waarvoor de som der kwadraten op meer dan één manier te schrijven is als som van kwadraten. Het feit dat Anna dan nog niet weet over welke getallen het gaat betekent dat deze zopas geformuleerde eigenschap geldt voor minstens twee van de ontbindingen van haar getal. Opnieuw zo voor Bob, en opnieuw zo voor Anna. Maar dan weet Bob het wel. Dus er is maar één paar getallen x,y waarvoor er telkens minstens twee mogelijkheden zijn, en de andere mogelijkheden stoten na drie keer (drie keer Bob of drie keer Anna, zoals je verkiest te tellen) op een unieke ontbinding.

Door wat te experimenteren met kleine getallen tot 25 vind je snel alle situaties waarin een som van twee getallen slechts eenmaal een dubieuze som van kwadraten oplevert. Bijvoorbeeld, indien som = 15, dan is voor alleen 5+10 een ander koppel dat dezelfde som van kwadraten oplevert, namelijk 2 en 11. Zo een situatie (maar niet deze!) moet dus aan het eind komen. Inderdaad, aan het begin kan niet; stel dat de getallen 5 en 10 zijn. Dan weet Bob het niet, want hij krijgt 125, en ook 2 en 11  voldoen. Maar Anna weet dan wel wat de getallen zijn, want zij kreeg 15, en alleen 5+10 kan twijfel opleveren voor Bob (elke andere combinatie niet, bvb 3+12 zou betekenen dat Bob 153 kreeg, maar dat kan maar op één manier als som van kwadraten te schrijven zijn, en dan zou Bob dus meteen geweten hebben welke getallen het zijn.

Jouw taak is nu dus om zulke situatie op het eind van zes keer twijfel te vinden, en op de juiste manier (dus niet dat Anna het weet, maar Bob). Indien ik nu meer zeg, dan verraad ik het antwoord.

Ik kan wel nog een voorbeeld geven van de eerste paar redeneringen van Bob en Anna. Stel dat de getallen 8 en 11 zijn. Bob krijgt 185, maar dat is 8^2+11^2 en 4^2+13^2. Dus Bob weet het niet. Anna krijgt 19. Door het feit dat Bob zegt dat hij het niet weet, weet zij dat de som van kwadraten niet uniek is. Er zijn nu drie mogelijkheden voor Anna: 8 en 11 (zoals zopas gezegd), maar ook 6+13, want 6^2+13^2=3^2+14^2, en 1+18, want 1+18^2=10^2+15^2. Dus zij weet het ook niet. Doordat zij het ook niet weet, weet Bob dat er in Anna haar som meerdere ontbindingen zitten die twijfel opleveren. Dus, zoals gezegd, dit geldt voor 8 en 11, maar dan gaat Bob na of dit ook zo is voor 4 en 13. Jammer voor hem is dit ook zo voor 4 en 13, want indien Anna 4+13=17 had gekregen, dan zou ze kunnen twijfelen tussen 4,13 en 3,14 (want 3^2+14^2=6^2+13^2) en 8,9 (want 8^2+9^2=1+12^2). Dus Bob weet het weer niet. Daardoor weet Anna dat alle mogelijkheden voor Bob twijfel opleveren, en zij gaat na of dit zo is voor al haar mogelijkheden: voor 8 en 11 is dit inderdaad zo, want dat hebben we net gedaan, maar wat gebeurt er voor 6+13 en 1+18? Maak dezelfde redenering nu zelf en zie dat deze ook allemaal twijfels opleveren. Dus Anna weet het ook niet. Nu terug Bob, recursief opnieuw alle mogelijkheden laten nagaan.... enz.

Ik hoop dat dit een beetje helpt. Zoals gezegd, indien toch niet, of je wilt bevestiging, mail gerust.

Ik moet nog vertellen wat er gebeurt indien je ook getallen groter dan 25 toelaat. Dan moet je bewijzen dat je door drie stappen niet kunt terecht komen in een "unieke" situatie. Met andere woorden, je moet bewijzen dat er geen unieke situaties zijn voor zulke grote getallen. Dit houdt in te bewijzen dat elk getal kan ontbonden worden in minstens twee keer twee termen waarvoor de som der kwadraten ook de som is van twee andere kwadraten. Dit is niet zo gemakkelijk op elementaire manier. Maar indien ik de leraar was, dan zou ik al heeeeel tevreden zijn indien je het raadsel oplost voor alleen kleine getallen.

Veel succes nog!

Hendrik Van Maldeghem, UGent

P.S. Om te oefenen in dit soort redeneringen ziehier twee andere raadsels, jedoch veel eenvoudiger:

er zijn opnieuw twee getallen, x,y (tussen 2 en 70 voor de eenvoud) en Paul krijgt het product, terwijl Sam de som krijgt. De conversatie verloopt als volgt:

Sam: Paul, gij kent mijn som niet
Paul: Ik ken uw som wel!
Sam: Nu ken ik uw product ook!

Of, zelfde gegevens, ander gesprek:

Sam: Paul, gij kent mijn som niet
Paul: Inderdaad, ik ken uw som niet
Sam: Maar ik nu wel uw product!     

 

Reacties op dit antwoord

Er zijn nog geen reacties op deze vraag.

Enkel de vraagsteller en de wetenschapper kunnen reageren op een antwoord.

Zoek andere vragen

© 2008-2020
Ik heb een vraag wordt gecoördineerd door het
Koninklijk Belgisch Instituut voor Natuurwetenschappen