Kezdőlap


Feladat:	1990. évi Nemzetközi Matematika Diákolimpia 22. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Harcos Gergely
Füzet:	1990/november, 341 - 343. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Teljes indukció módszere, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1990/szeptember: 1990. évi Nemzetközi Matematika Diákolimpia 22. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Rögtön észrevehetjük, hogy $B$ -nek mindig csökkentenie kell az utoljára elhangzott számot, $A$ -nak pedig növelnie (legalábbis nem csökkentenie). Az is látszik, hogy $B$ csak akkor nyerhet, ha $A$ előtte prímhatványt mondott. Mivel $A$ mindig egy $[n_{2 k}, n_{2 k}^{2}]$ típusú intervallumból választhat számot, ezért ─ úgy érezzük ─ $B$ -nek elég kevés esetben van esélye a nyerésre, feltéve persze, hogy $A$ valamilyen ésszerű stratégiával játszik.
Célszerű tehát először az a) kérdéssel foglalkoznunk. Ha $n_{0} \leq 1990 < n_{0}^{2}$ , akkor $A$ triviálisan nyer az $n_{1} = 1990$ számmal, ezért $45 \leq n_{0} \leq 1990$ esetén $A$ -nak van nyerési stratégiája.
Az $1990 < n_{0}$ esetben $A$ nem alkalmazhatja ezt a módszert, de ha tud olyan $n_{1}$ számot mondani, amelyre $B$ csak $45 \leq n_{2} \leq 1990$ számmal válaszolhat, akkor ismét $A$ nyer, hiszen ekkor $n_{0}$ szerepét $n_{2}$ veszi át. Legyen például $n_{1} = 47 \cdot 53 = 2491$ ‐ $A$ választhatja ezt a számot $1990 < n_{0} \leq 2491$ esetén ‐, ezzel $n_{2} = 47$ vagy $53$ .
Ezzel beláttuk, hogy $45 \leq n_{0} \leq 2491$ esetén $A$ tud nyerni, hasonlóan fogjuk igazolni $k$ szerinti teljes indukcióval, hogy $45 \leq n_{0} \leq 2^{k - 1} \cdot 2491$ esetén ( $k$ pozitív egész) is $A$ -nak van nyerési stratégiája.
$k = 1$ -re már beláttuk az állítást, tegyük fel ezért, hogy valamilyen $k \geq 1$ -re igaz az állítás, azt kell megmutatnunk, hogy

\begin{matrix} 2^{k - 1} \cdot 2491 < n_{0} \leq 2^{k} \cdot 2491 \end{matrix}

esetén

A

-nak van nyerési stratégiája.
Válassza ehhez

A

n_{1} = 2^{k} \cdot 2491 = 2^{k} \cdot 47 \cdot 53

számot, nyilván

n_{0} \leq n_{1} < n_{0}^{2}

. Ezek után

B

csak egy

n_{2} = n_{1} / p^{α} = (2^{k} \cdot 47 \cdot 53) / p^{α}

alakú egészet választhat, ahol

p^{α}

prímhatvány. Erre

47 < n_{2} \leq \frac{n_{1}}{2} = 2^{k - 1} \cdot 2491

, ami azt jelenti induktív feltevésünk szerint, hogy

A

-nak van nyerési stratégiája, az állítás

(k + 1)

-re is fennáll.
Eddigi eredményeinket összefoglalva kapjuk, hogy a

45 \leq n_{0}

esetben

A

-nak van nyerési stratégiája.
Próbáljuk meg a fennmaradó

n_{0} < 45

eseteket is erre az esetre visszavezetni.

A

-nak olyan

n_{1}

számot kell mondania, amelyre

B

csak egy

45 \leq n_{2}

számot választhat. Tekintsük ehhez az

n_{1} = 3^{2} \cdot 5 \cdot 11 = 495

számot ‐

A

választhatja ezt a

23 \leq n_{0} \leq 44

esetben, mert ekkor

n_{0} \leq n_{1} \leq n_{0}^{2}

‐, ezzel

n_{2}

-re

\begin{matrix} n_{2} \geq min (3^{2} \cdot 5, 3^{2} \cdot 11,5 \cdot 11) = 3^{2} \cdot 5 = 45, \end{matrix}

vagyis az előzőek alapján

A

-nak van nyerési stratégiája.
Hátra van az

n_{0} \leq 22

eset vizsgálata;

A

-nak most már elegendő olyan

n_{1}

számot mondania, amelyre

n_{2} \geq 23

. Legyen ehhez

n_{1} = 2 \cdot 3 \cdot 5 \cdot 7 = 210

, ezzel

n_{2} \geq 2 \cdot 3 \cdot 5 = 30

. Mivel a

15 \leq n_{0} \leq 22

esetben

n_{0} \leq n_{1} \leq n_{0}^{2}

is teljesül, ezért ilyenkor is

A

-nak van nyerési stratégiája.
Tovább ,,lépegetünk'' lefelé ‐ mindig ugyanazzal a redukáló szándékkal:

11 \leq n_{0} \leq 14

esetén

A

száma legyen

n_{1} = 3 \cdot 5 \cdot 7 = 105

; nyilván

n_{0} \leq n_{1} \leq n_{0}^{2}

, és

n_{2} \geq 3 \cdot 5 = 15

, vagyis innen

A

nyerni tud ‐ az eddig bizonyítottak miatt.
Végül legyen

n_{1} = 2^{2} \cdot 3 \cdot 5 = 60

8 \leq n_{0} \leq 10

; ekkor

n_{0} \leq n_{1} \leq n_{0}^{2}

és

n_{2} \geq min (2^{2} \cdot 3, 2^{2} \cdot 5, 3 \cdot 5) = 2^{2} \cdot 3 = 12

, ami azt jelenti, hogy ekkor is

A

-nak van nyerési stratégiája.
Ezzel beláttuk, hogy

8 \leq n_{0}

esetén

A

-nak van nyerési stratégiája.
Ezzel a módszerrel nem tudjuk tovább csökkenteni

n_{0}

olyan lehetséges értékeit, amelyekből kiindulva

A

el tudja érni a győzelmet. Azt tapasztaljuk ugyanis, hogy

n_{0} < 8

esetén

A

nem tud olyan

n_{1}

számot mondani, amelyre

B

csak egy

n_{2} \geq 8

-cal válaszolhatna. Ez a tény azt sejteti velünk, hogy

n_{0} < 8

esetén

B

legalább egy döntetlent ki tud kényszeríteni. (Valójában az előbbi észrevétel igazolja is sejtésünket, hiszen ha

B

nem nyer, akkor

B

még mindig ki tud kényszeríteni egy végtelen

\begin{matrix} n_{0} < 8, n_{1} < 64, n_{2} < 8, n_{3} < 64, n_{4} < 8, n_{5} < 64, ... \end{matrix}

számsorozatot, ami azt jelenti, hogy

A

sem nyerhet, mert nem nevezheti meg az

1990

-et. A későbbiekben azonban úgyis pontosabban megvizsgáljuk a döntetlen lehetőségeit, ezért egyelőre a sejtés elegendő számunkra.)
Foglalkozzunk most a

b)

kérdéssel.
Ha

n_{0} = 2

, akkor

n_{0} \leq n_{1} \leq n_{0}^{2}

miatt

A

csak prímhatványt választhat

(n_{1} = 2,3,4)

, vagyis

B

mondhatja az

n_{2} = 1

számot, amivel megnyeri a játékot.
Ha

n_{0} = 3

, akkor

n_{1} = 3

4

5

6

7

8

9

. Ha

n_{1}

prímhatvány, akkor

n_{2} = 1

-gyel

B

nyer, egyébként

n_{1} = 6 = 2 \cdot 3

. Ekkor

B

választhatja az

n_{2} = 2

számot, és ekkor ‐ mint az előbb igazoltuk ‐

B

-nek van nyerési stratégiája. (

n_{0}

szerepét

n_{2}

veszi át).
Ha

n_{0} = 4

, akkor

B

az előbbiekhez hasonlóan el tudja érni a győzelmet, amennyiben

n_{1}

prímhatvány, vagy

n_{1} \leq 3^{2}

. Különben pedig

n_{1} = 10

12

14

15

; és ezeket az eseteket rendre visszavezethetjük az előzőekre az

n_{2} = 2

3

2

3

választással, ugyanis

n_{2} \leq 3

esetén

B

-nek van nyerési stratégiája.
Végül

n_{0} = 5

esetén

n_{0} \leq n_{1} \leq n_{0}^{2}

miatt

n_{1}

prímhatvány, vagy

n_{1} \leq 4^{2}

(amire már láttuk, hogy

B

-nek van nyerési stratégiája), vagy pedig

n_{1} = 18

20

21

22

24,

és ezeket az

n_{2} = 2

2^{2}

3

2

3

választással rendre visszavezethetjük a már megvizsgált

n_{0} \leq 4

esetre (

n_{0}

szerepét

n_{2}

veszi át).
Összességében tehát kimondhatjuk, hogy

2 \leq n_{0} \leq 5

esetén

B

-nek van nyerési stratégiája.
Meg kell még vizsgálnunk az

n_{0} = 6,7

esetet. Mivel a

B

-nek győzelmet jelentő

n_{0}

kezdőértékek lehetséges értékeit nem tudjuk a szokásos módszerünkkel tovább növelni, ezért igen valószínűnek látszik, hogy

n_{0} = 6,7

esetén egyik játékos sem tudja kikényszeríteni a győzelmet. Ehhez csak azt kell igazolnunk, hogy mind

A

, mind

B

tud úgy játszani, hogy a másik ne nyerhessen.
Legyen tehát

n_{0} = 6

vagy

7

, és

A

válassza az

n_{1} = 30 = 2 \cdot 3 \cdot 5

számot, amelyre nyilván

n_{0} < n_{1} < n_{0}^{2}

B

ezután csak

n_{2} = 2 \cdot 5 = 10

-et, vagy

n_{2} = 3 \cdot 5 = 15

-öt, vagy

n_{2} = 2 \cdot 3 = 6

-ot választhat.
Az

n_{2} = 10,15

esetben ‐ mint már láttuk ‐

A

-nak van nyerési stratégiája, az

n_{2} = 6

eset pedig

A

szempontjából ekvivalens az

n_{0} = 6

kezdéssel (tehát újra jöhet

n_{0} = 30

, stb.) így beláttuk, hogy ha

A

ügyesen játszik, akkor

B

nem nyerhet.
Ugyanez áll viszont

B

-re is. Ha ugyanis

n_{0} = 6

vagy

7

, akkor

6 \leq n_{1} \leq 49

, és ha végignézzük a

6

7

...

49

számokat, azt találjuk, hogy

B

mindig tud olyan

n_{2}

számot mondani, amelyre

n_{2} \leq 6

. Ha

n_{2} \leq 5

, akkor a fentiek miatt nyerési stratégiája van

B

-nek (esetleg

n_{2} = 1

), ha pedig

n_{2} = 6

, akkor ugyanolyan helyzetet kapunk, mint amilyennel kezdtük a játékot (amikor

n_{0} = 6

7

).
Ezzel a feladatot megoldottuk, eredményeinket a következőképpen foglalhatjuk össze:
a)

A

-nak van nyerési stratégiája, ha

8 \leq n_{0}

,
b)

B

-nek van nyerési stratégiája, ha

2 \leq n_{0} \leq 5

, végül
c) egyik játékos sem tudja kikényszeríteni a győzelmet, ha

n_{0} = 6,7