Het Euclidisch algoritme levert direct: H = 11c -
4x en L = 8c - 3x met c
een willekeurig geheel getal.
Voorbeeld: we willen 26 verdiepingen omhoog, dan is dus x =
26
We moeten een c kiezen zodat H en L beiden positief zijn.
c = 10 geeft bijv. H = 6 en L = 2 en inderdaad levert
6 keer omhoog en 2 keer omlaag de gewenste 26 verdiepingen
stijging op (6 • 8 - 2 • 11 = 26).
Krijgen we geen problemen met het dak?
Nou nee. Stel dat we H niet kunnen uitvoeren omdat we hoger
dan verdieping 58 zitten.
Dan voeren we toch gewoon eerst een paar keer L uit? We moeten
zeker nog L-bewegingen maken anders komen we netto niet op een
bestaande verdieping uit.
De volgorde van H en L is willekeurig, dus zo gauw we te hoog
dreigen te komen doen we een paar L-bewegingen en zodra we te laag
dreigen te komen doen we eerst een paar H-bewegingen.
Is er geen eenvoudiger manier?
Tuurlijk. 8H - 11L = 1 levert (c = 1) H = 7
en L = 5
Daar hebben we een manier om één verdieping hoger te komen. Door
die steeds maar weer toe te passen kunnen we overal komen.
Op dezelfde manier levert 8H - 11L = -1 met c = 0 de
oplossing H = 4 en L = 3
Daar is een manier om één verdieping lager te komen.
|