Kalender 2005 |
Oplossingen week 1 (3 t/m 9 januari)Maandag 3 januari0-7 → 4-3 → 0-3 → 3-0 → 3-7 →
4-6 → Dinsdag 4 januariNee, want 6 en 9 zijn allebei een veelvoud van drie en 8 niet. Elke keer dat er weer iets is overgeschonken zit er in elk vat een veelvoud van drie. Woensdag 5 januari16-0 → 1-15 → 1-0 → 0-1 → 16-1 → 2-15 → 2-0 → Donderdag 6 januari10-0-0 → 7-0-3 → 7-3-0 → 4-3-3 → 4-6-0 → 1-6-3 → Vrijdag 7 januari12-0-0 → 7-0-5 → 7-5-0 → 2-5-5 → 2-7-3 → Zaterdag 8 januari9-0-0-0 → 4-5-0-0 → 4-3-0-2 → 4-0-3-2 → Zondag 9 januariVoor gegeven a en b bekijken we eerst aan welke voorwaarden c in ieder geval moet voldoen. Het is duidelijk dat c ≤ a+b, want dat is de grootste hoeveelheid die we kunnen afmeten. Verder zien we dat als a en b alletwee een veelvoud van een getal d zijn, dat dan alle hoeveelheden die we kunnen afmeten ook veelvouden van dit getal zijn. We concluderen dat c een veelvoud moet zijn van de grootste gemene deler van a en b. Nu vragen we ons af of deze voorwaarden ook voldoende zijn, dus dat we iedere hoeveelheid c ≤ a+b met ggd(a,b) | c ook daadwerkelijk kunnen maken. Enig experimenteren doet vermoeden dat dit het geval is. Een klein beetje notatie om het onderstaande argument te versimpelen:
Door eventueel te delen door ggd(a,b) kunnen we er voor zorgen dat ggd(a,b)=1, zodat de enige eis op c is dat c ≤ a+b. Verder kunnen we aannemen dat a > b (in het geval a = b = 1 is de bewering duidelijk waar). We kunnen nu de volgende stappen maken: (0,0) → (a,0) → (a−b,0) → ... → (a%b,0) →
(0,a%b) → Nu omdat ggd(a,b) = 1, komen in de rij (1•a)%b, (2•a)%b, ..., (b•a)%b de getallen 0, 1, ..., b−1 allemaal precies 1 keer voor, zodat we alle hoeveelheden van 0 t/m b−1 kunnen maken. Nu kunnen we dus elke hoeveelheid c maken door eerst c%b af te meten en dan een voldoende aantal keer b erbij te doen. |