10. príklad - Vzorové riešenie

Najskôr popíšeme, ako má AnkaP hrať, aby čo najskôr vyhrala, a potom vysvetlíme, prečo to funguje a prečo je to optimálna stratégia.

1. AnkaP začína hru umiestnením pyramídy. Keďže na rovine ešte nič nie je, je jedno kam ju umiestni.
2. Ľudstvo niekam umiestni svojich n miest.
3. V každom ďalšom ťahu AnkaP umiestni svoju pyramídu tak, aby vytvorila čo najviac tzv. potenciálnych trojuholníkov – každá dvojica pyramíd tvorí úsečku, ku ktorej existujú dva body také, že ak na jeden z nich v nasledujúcom kole AnkaP položí pyramídu, vytvoria rovnostranný trojuholník a AnkaP vyhrá.
4. Ľudstvo teraz musí pokryť všetky potenciálne trojuholníky mestami, inak AnkaP v nasledujúcom kole vyhrá.
5. Ak AnkaP môže vytvoriť rovnostranný trojuholník a vyhrať, urobí to, inak pokračuje krokom 3.

Vieme, že keď AnkaP vyhrá tým, že využije nejaký potenciálny trojuholník vytvorený v predchádzajúcich kolách. Ľudstvo sa však tieto potenciálne trojuholníky bude snažiť zablokovať. Ak teda chce AnkaP vyhrať, musí vyrobiť väčší počet potenciálnych trojuholníkov, než ľudstvo dokáže pokryť.

Vieme, že každá dvojica pyramíd môže vytvoriť najviac dva potenciálne trojuholníky. Najviac teda môžeme zaručiť, aby každá dvojica pyramíd vytvorila dva potenciálne trojuholníky. To spravíme tak, že vždy keď AnkaP položí pyramídu, vytvorí dva potenciálne trojuholníky s každou už položenou pyramídou.

Keď AnkaP pokladá pyramídu, existujú nejaké body, kde ak ju položí, nevytvorí plný počet potenciálnych trojuholníkov – pozrime sa na to, koľko je takýchto bodov:

• Jedna takáto možnosť je položiť pyramídu tak, že nejaký potenciálny trojuholník, ktorý vytvorí, má vrchol v už položenom meste. Každá dvojica pyramídy a mesta tvorí dva takéto body.
• Druhá možnosť je taká, že by pyramída vytvorila dva potenciálne trojuholníky ktoré majú spoločný tretí vrchol. Toto sa stane len, ak AnkaP položí pyramídu do bodu ktorý vytvorí s dvoma už položenými pyramídami rovnoramenný trojuholník s uhlom 120 \degree pri novej pyramíde. Takéto body sú dva pre každú dvojicu už položených pyramíd.

Teda celkovo neoptimálnych bodov je 2 \cdot pyramídy \cdot (pyramídy + mestá). Keďže počet už položených pyramíd aj miest je konečný, ale počet bodov na nekonečnej rovine je nekonečný. Takže vždy bude existovať bod, kam môže AnkaP položiť pyramídu tak, aby vytvorila najväčší možný počet potenciálnych trojuholníkov.

Poďme teraz vyjadriť, koľko ťahov bude AnkeP trvať vyhrať hru pyramídová schéma.

V i-tom ťahu AnkaP položí pyramídu a vytvorí tým dva potenciálne trojuholníky s každou už položenou pyramídou. Bude ich teda 2 \cdot (i-1). Ak ich ľudstvo v nasledujúcom ťahu nedokáže pokryť, tak AnkaP vo svojom ďalšom ťahu vyhrá. To sa stane ak 2 \cdot (i-1) > n. Po úprave rovnice dostaneme postupne:

i-1 > \frac{n}{2}

i > \frac{n}{2} + 1

Vieme však, že AnkaP vyhrá až v nasledujúcom ťahu t = i + 1. Ťah, v ktorom vyhrá, má najmenšie číslo t ktoré vyhovuje nerovnici t > \frac{n}{2} + 2. Toto si rozoberieme na prípady, kedy n je párne alebo nepárne:

Ak n = 2k, teda n je párne: t > \frac{2k}{2} + 2 = k + 2.
Ak n = 2k+1, teda n je nepárne: t > \frac{2k+1}{2} + 2 = k + 2{,}5.

Keďže k je celé číslo, najmenšie t vyhovujúce nerovnici bude v oboch prípadoch k + 3.

Odpoveď: AnkaP vždy vie vyhrať – vyhrá v ťahu s číslom k + 3, kde k = \frac{n}{2} zaokrúhlené nadol.

Komentár

Väčšina z vás použila správny postup, avšak ste odovzdali riešenie k + 2 alebo prípadne k + 1. Toto sa dialo preto, že aj keď ste došli ku správnej nerovnici, treba si všimnúť, že ťah musí byť väčší ako k + 2 a najmenšie prirodzené číslo väčšie ako k + 2 je k + 3.

Toto tiež poukazuje na dôležitosť skúšok správnosti, a kontrolovania si výsledku čo vám vyjde. Ak si za n dosadíme napríklad 0, tak s riešením k + 2 vám vyjde výsledok 2, avšak vieme, že AnkaP určite nemôže trojuholník vytvoriť predtým čo položí tri pyramídy.