WisFaq!

Modulo rekenen

Hallo Wisfaq,

Zouden jullie me kunnen helpen met het volgende probeem. De probleemstelling is als volgt:

4 mannen en een aap hebben een stapel noten verzameld. Gedurende de nacht staat een van de mannen op (terwijl de anderen slapen) en verdeelt de noten in 4 gelijke stapels. Er blijft 1 noot over die hij aan de aap geeft. Vervolgens verbergt hij een van de stapels en maakt van de rest van de noten weer een grote stapel. Ook de andere 3 mannen herhaalden deze procedure en telkens werd er 1 noot aan de aap gegeven. De volgende morgen deelden de mannen de overgebleven noten in 4 gelijke delen en wederom bleef er 1 noot over voor de aap. Laat zien dat het aantal noten n in de oorspronkelijke stapel voldeed aan 81nº781 mod 1024. Wat is de kleinst mogelijke waarde voor het aantal noten? (Hint: laat k het aantal noten voorstellen dat elke man in de morgen krijgt).

Het probleem is dat ik door de hoeveelheid tekst geen idee heb waar ik moet beginnen (de hint helpt me ook niet echt op weg).

Michal de Vries
25-2-2007

Antwoord

Dag Michal,

Laten we met de hint beginnen: elke man krijgt k noten in de morgen. Ze zijn met vier, en er schiet nog één noot over, dus er zijn in de ochtend nog 4k+1 noten over. Laten we dan kijken naar wat de laatste opstaander heeft gedaan: die zag een hoop noten (zeg r), daarvan gaf hij één noot aan de aap en van de overschot (r-1 dus) verborg hij een kwart, dus hij liet 3/4 liggen. Dus de stapel die er in de ochtend lag, was 3/4 (r-1), en dat was dus k+1.

3/4 (r-1) = 4k+1 dus r = 4/3 (4k+1) + 1 = 16k/3 + 7/3

Dan kijk je naar de voorlaatste opstaander: die zag een hoop liggen (zeg s), hij nam er één af voor de aap (dus er schoten er nog s-1 over), hij stopte een kwart hiervan weg, er schoot dus nog 3/4 (s-1) over, en dat was wat hij liet liggen voor de volgende, en dat hadden we r genoemd en al uitgerekend in functie van k. Druk dan nu s uit in functie van k. Doe nog eens hetzelfde voor de tweede en de eerste opstaander. Zo vind je uiteindelijk het oorspronkelijke aantal noten in functie van k, waarbij k een natuurlijk getal is. Daaruit zou je zo een modulorelatie moeten kunnen afleiden, probeer maar eens...

Groeten,
Christophe.

Christophe
25-2-2007