Stel dat de jongens x en y
cent per rondje krijgen en dat zij a en b rondjes lopen.
Dan is hun totale bedrag gelijk aan ax + by
We zoeken naar het grootst mogelijke getal c zodat ax + by
= c géén oplossing heeft.
NUTTIGE STELLING:
|
| Als x en y
relatief priem zijn (= geen gemeenschappelijke
priemdelers hebben), dan is het grootste getal dat
niet te schrijven is als ax
+ by = c gelijk aan xy
- x
- y
|
het bewijs van deze stelling staat
hier.
|
Als x en y wél gemeenschappelijke priemdelers
hebben, dan bestaat er niet zo'n grootste getal.
Immers dan is ax + by deelbaar door dat gemeenschappelijke
priemgetal, dus zijn alleen veelvouden daarvan te fabriceren.
Om het grootste getal te vinden zoeken we dus oplossingen van de
vergelijking xy - x
- y = c
xy - x - y = c Þ xy
- x - y + 1 = c + 1
Þ (x - 1)•(y
- 1) = (c + 1)
Daarom gaan we proberen c + 1 te ontbinden in factoren.
In het geval van beide jongetjes is c = 57657
dus c + 1 = 57658
57658 = 2 • 127 • 227 dus de volgende ontbindingen van 57658
zijn mogelijk:
| (x - 1) |
(y - 1) |
x |
y |
1
2
127
227 |
57658
28829
454
254 |
2
3
128
228 |
57659
28830
455
255 |
De eerste twee vallen af omdat elk jongetje minstens 5 cent kreeg. De
vierde valt af omdat 228 en 255 niet relatief priem zijn (beiden
deelbaar door 3).
Dus de enige oplossing is dat de ene jongen 1,28 per ronde kreeg
en de andere 4,55.
Vraag 2: Hoeveel andere bedragen kunnen
zij óók niet binnenkrijgen?
Dat is te bepalen zonder alle bedragen te
"proberen". Als volgt:
Noem een bedrag "haalbaar" als het te schrijven is als ax
+ by
Dan verandert de functie f(c) = xy
- x - y
- c een haalbaar in een niet-haalbaar bedrag, en een
niet-haalbaar in een haalbaar bedrag. Kortom; deze functie verwisselt de
"haalbaarheid" van een bedrag.
Om dat te bewijzen moeten wem twee stappen bewijzen:
stap 1: als c haalbaar is, dan is f(c)
niet-haalbaar.
stap 2: als c niet-haalbaar is, dan is f(c) haalbaar.
stap 1.
Stel dat c en f(c) beide haalbaar zijn, dan is c
+ f(c) ook haalbaar.
Dan is xy - x
- y = c + f(c) óók
haalbaar, en dat is in tegenspraak met de stelling helemaal bovenaan.
stap 2.
Stel dat c niet-haalbaar is.
Bij het bewijs van de stelling helemaal bovenaan lieten we zien dat er
getallen u en v te vinden zijn zodat c = ux
+ vy (met v < 0 en 0 < u < y)
f(c) = xy - x
- y - c = xy
- x - y
- ux - vy = x(y
- 1 - u) + y(-1
- v)
Maar de coëfficiënten y - 1 - u en -1
- v
zijn beiden groter of gelijk aan nul, dus is f(c)
haalbaar.
De functie f koppelt elk getal uit interval [0, xy
- x - y] aan een ander getal uit dat interval.
Dus de helft van de getallen onder xy - x
- y is
niet haalbaar en de andere helft wel.
Kortom: er zijn precies (xy - x
- y + 1) / 2
= (x - 1)(y
- 1)/2 niet-haalbare
getallen.
De beide jongetjes kunnen dus 1/2
• 127 • 454 = 28829 andere bedragen niet ophalen.
|
