9. Kolosálne Medziľudské Spoločnosti vzorové riešenie

Úlohu budeme riešiť matematickou indukciou vzhľadom na počet matematikov. Použijeme tú formu, pri ktorej predpokladáme, že úlohu vieme vyriešiť pre všetky nižšie počty. Pre \(0\) matematikov tvrdenie triviálne platí. Najmenší počet matematikov, ktorý má význam uvažovať, je \(1\). V prípade že je daný matematik presne v strede, v prvej sekunde si vyberie jedného manažéra, ku ktorému vykročí a následne sa k nemu bude blížiť na polovičnú vzdialenosť, až kým k nemu v konečnom počte krokov nepríde. To sa ale určite aspoň za \(\log_2(500 000)\) krokov stane. Ak nie je presne v strede, priebeh bude analogický až na to, že manažér, ku ktorému sa začne hneď na začiatku približovať, je dopredu určený, keďže je najbližšie. Týmto je prvý krok indukcie dokázaný.

Predpokladajme teraz, že danú úlohu vieme vyriešiť pre \(a<n\) matematikov a poďme sa pozrieť na prípad, kedy je matematikov \(n\). Indukcia je v tomto prípade užitočná preto, že akonáhle eliminujeme aspoň jedného matematika, tvrdenie vieme z indukcie prehlásiť za dokázané.

Najprv uvažujme postupnosť \(1<m\) matematikov. Tí majú medzi sebou \(m-1\) medzier. To je iba \(m-1\) pozícií, kam sa môžu pohnúť, keďže vždy idú do stredu nejakej medzery. Takže ak sa najľavejší matematik rozhodne ísť doprava a najpravejší doľava, tak z Dirichletovho princípu sa aspoň \(2\) matematici stretnú, čím celkový počet matematikov klesne a úlohu nám dorieši indukčný predpoklad.

Takže v žiadnom kroku neexistuje úsek, na ktorého koncoch by sa matematici rozhodli ísť proti sebe. Zoberme prvého matematika zľava, ktorý sa rozhodol vykročiť doprava a nazvime ho Jožko. Ak taký neexistuje, tak Jožkom nazvime manažéra. Dôkaz prebehne rovnako - všetci matematici pred Jožkom šli prvý krok doľava, Jožko a tí za ním doprava. To nám garantuje, že postupnosť vzdialeností medzi matematikmi až po Jožka je neklesajúca. Ak by aspoň raz táto postupnosť klesla, tak vzdialenosť \(k\)-teho od \((k+1)\)-vého matematika je menšia ako \(k\)-teho od \((k-1)\)-vého, a teda \(k\)-ty matematik by musel spraviť krok doprava. Keďže je pred Jožkom, tak ide o spor. Podobne postupnosť vzdialeností matematikov za Jožkom by musela byť nerastúca. Ak by aspoň raz vzrástla, tak by sme mali matematika za Jožkom, ktorý musí spraviť krok doľava, lebo od svojho ľavého suseda má menšiu medzeru ako od pravého. S Jožkom by však vytvorili škripec, kvôli ktorému by sa aspoň dáky matematik medzi nimi stretol s iným a úlohu by nám doriešil indukčný predpoklad. Všimnime si, že nerastúcosť a neklesajúcosť týchto postupností sa po kroku nezmení.

Jožko týmto stratil možnosť ísť doľava (aj keď predtým ju nemusel nutne mať), jeho vzdialenosť od matematika pred ním sa zväčšila (triviálne) a vzdialenosť od matematika za ním sa zmenšila alebo nezmenila. Je to preto, že ak bol od matematika za ním vzdialený o \(d\), matematik za ním bol od svojho pravého suseda vzdialený maximálne o \(d\) (už sme si ukázali, že ide o nerastúcu postupnosť). Jožko sa teda pohol o \(\frac d2\) doprava a matematik za ním o maximálne \(\frac d2\) doprava, a teda ich vzdialenosť sa nezväčšila. Uvedomme si, že sa už nikdy nezväčší. Keďže každý matematik, ktorý je vpravo od Jožka, má pravého matematika bližšie alebo rovnako ďaleko ako ľavého, tak jeho posun doprava je nanajvýš rovnako veľký (polovica nanajvýš rovnakej vzdialenosti) ako posun jeho ľavého kamaráta doprava, takže sa jeho vzdialenosť od ľavého kamaráta nezväčší. Teoreticky by sa tá vzdialenosť mohla zmenšiť natoľko, že by musel spraviť krok doľava, ale to by nám vznikol škripec a úlohu by nám doriešil indukčný predpoklad. Takže matematici v nerastúcich rozostupoch pekne kráčajú k svojmu manažérovi alebo sa vrhajú do pazúrov indukčného predpokladu.

Takže Jožko a všetci za ním pôjdu doprava a tí pred ním úplne rovnako doľava. Ostáva si rozmyslieť, či niekedy dôjdu do cieľa. Najprv je matematikov iba konečný počet, takže existuje ten, ktorý je najbližšie pravému manažérovi. Ten sebavedomo skracuje vzdialenosť medzi sebou a manažérom na polovicu, až kým dôjde do vzdialenosti \(0.5\) metra, čo určite vie, lebo nech začíname s ľubovoľným \(x\), tak vieme nájsť \(n\) dosť veľké, že \(\frac x{2^n}\) bude menej ako \(0.5\). Druhý matematik zľava síce neskracuje vzdialenosť priamo k manažérovi, ale k prvému matematikovi. Ten je však v konečnom čase za métou \(0.5\) m od manažéra. Teda druhý matematik sa k manažérovi začne približovať aspoň tak rýchlo, akoby delil vzdialenosť medzi sebou a \(0.5\) m na polku, preto po nejakom čase bude \(\frac14\) m od \(\frac12\) m, čo je \(0.75\) m od manažéra. Tretí matematik začne poliť svoju vzdialenosť od \(0.75\) m od manažéra, až sa dostane na \(\frac18\) na od \(\frac14\) m od \(\frac12\) m. A tak ďalej. Všimnime si, že všetci sa takýmto spôsobom do toho \(1\) m zmestia :).