vraag internationale olympiade

[donald_sciencetalk]

Beste,
Heeft iemand misschien een idee hoe je deze vraag kan oplossen?

Je start met twee verschillende gehele getallen op een blad. Je voert een reeks stappen uit. Elke stap bestaat uit één van de volgende twee handelingen:
- Als a en b verschillende gehele getallen zijn op het blad, dan mogen we a+b op het blad schrijven
(enkel als het er nog niet staat).
- Als a, b en c drie verschillende gehele getallen zijn op het blad, en als een geheel getal x voldoet
aan ax^2 + bx + c = 0, dan mogen we x op het blad schrijven (enkel als het er nog niet staat).

Bepaal alle paren startgetallen (u, v) waarvoor geldt dat elk geheel getal na een eindig aantal stappen
uiteindelijk op het blad geschreven kan worden.

[siep]

Bekijk systematisch alle mogelijkheden voor u en v, gegeven u \neq v:

Situatie 1: u>0, v>0
Handeling 1 genereert alle getallen n\cdot u + m\cdot v (n \ge 1, m \ge 1).
Kies hieruit voor handeling 2 deze drie getallen:
p = u + v
q = 2u + 2v = 2p
r = 3u + 3v = 3p
en stel
px^2 + rx + q = 0
We kunnen dan x_1 = -1 en x_2 = -2 op het blad schrijven.
Via handeling 1 genereren we met deze twee alle negatieve getallen.
Samen met een onbeperkt groot getal dat we met u en v via handeling 1 kunnen bereiken, kunnen we nu dus elk geheel getal bereiken.


Situatie 2: u=0 of v=0
Stel u=0, dan kunnen we via handeling 1 alleen 0 + v = v bereiken, maar die staat al op het blad, dus lopen we vast.
Handeling 2 kunnen we hier niet gebruiken, want we hebben geen 3 verschillende getallen.


Situatie 3a: u<0, v>0 en u=-v
Handeling 1 geeft maximaal \{-v, 0, v \}
Handeling 2 levert (elk van deze 3 vergelijking ook nog met -1 te vermenigvuldigen, maar dat geeft geen extra oplossingen):
0x^2 + vx - v = 0\; \Rightarrow \; x =1
vx^2 + 0x - v = 0\; \Rightarrow \;x = \pm 1
vx^2 - vx + 0 = 0\; \Rightarrow \;x = 0 \vee x = 1
[1] als v = 1 levert dit geen nieuwe waarden op en lopen we vast,
[2] als v \neq 1: gebruik het paar (1, v) als in situatie 1 om alle getallen te genereren

Situatie 3b: u<0, v>0 en u \neq -v
[1] stel u is een negatief veelvoud van v, dan is er een k > 1, zodat u = -kv
Via handeling 1 kunnen door herhaald v op te tellen bij u = -kv op het blad toevoegen:
(-kv+v), (-kv+2v), ..., -2v, -v, 0.
Via handeling 2 krijgen we zowel x=1 (0x^2+vx-v = 0) als x=2 (0x^2+vx-2v = 0),
waarmee we weer in situatie 1 belanden.
[2] stel u is geen negatief veelvoud van v. Tel dan herhaald v bij u op, totdat je net boven nul komt, en noem dat getal w.
Er geldt dan w > 0 EN w \neq v, waardoor je met (v, w) weer alle getallen kan genereren.


Situatie 4: u<0, v<0
Net als in situatie 1 kunnen we hier kiezen:
p = u + v
q = 2u + 2v = 2p
r = 3u + 3v = 3p
waarmee we weer alle negatieve getallen kunnen genereren.
In handeling 2 zijn nu alle parameters a, b en c negatief. Als we
ax^2+bx+c = 0
herschrijven als
x^2+\frac{b}{a}x+\frac{c}{a} = 0
zijn zowel \frac{b}{a} als \frac{c}{a} positief.
Voor de oplossing geldt
(x-x_1)(x-x_2) = x^2 - (x_1+x_2)x +x_1x_2 = 0
Omdat x_1x_2 >0 zijn ze ofwel beide positief, ofwel beide negatief, en
omdat -(x_1+x_2) > 0 blijft er 1 mogelijkheid over: beide oplossingen zijn negatief
In dit geval kunnen we dus nooit een positief getal toevoegen.


Volgens mij is bovenstaande zo compleet, laat s.v.p. even weten als je vragen of opmerkingen hebt.