Zadanie
Po výdatných raňajkách sa všetci presunuli na otvárací ceremoniál. Jednými zo súťažiacich boli aj Izraelčania, ktorých bolo tento rok hojne. Ich delegácia pozostávala z \(25\) členov, pričom každý mal svoj unikátny dres s číslom od \(1\) po \(25\). Keď prišli na ceremoniál, sadli si na ľavý kraj prázdneho radu s \(n\) sedadlami tak, že ich čísla boli usporiadané vzostupne zľava doprava. Potom však zistili, že pri predstavovaní ich budú vyvolávať sprava doľava, a preto sa chceli presadiť tak, aby sedeli tesne vedľa seba, ale zľava doprava zostupne. Aby to nebolo také nudné, rozhodli sa premiestňovať tak, že v každom kroku sa niektorý Izraelčan buď posunie o 1 sedadlo doprava, ak je voľné, alebo prekročí človeka sediaceho tesne napravo a sadne si na nasledujúce sedadlo, ak je voľné. Kým predseda komisie Johnny rozprával o histórií Blagogradu, Majo sa z nudy zamyslel nad tým, či sa to Izraelčanom takto vôbec môže podariť. Nájdite najmenšie \(n\), pre ktoré si Izraelčania vedia v rade s \(n\) sedadlami takto presadnúť.
Najprv si uvedomíme, že \(n\) musí byť najmenej \(49\). Žiaden z Izraelčanov sa nemôže posunúť doľava, teda Izraelčan s číslom \(25\) musí určite zostať na svojom mieste alebo sa posunúť doprava. Ak by zostal na svojom mieste tak budeme potrebovať ďalších \(24\) miest pre ostatných, teda spolu \(49\) miest. Ak by sa sa posunul doprava, tak by sme potrebovali navyše počet miest, o ktoré sa posunul a ešte 24 navrch.
Skúsme sa teda pozrieť či by sa boli schopní preusporiadať, ak by sa \(25.\) Izraelčan nepohol. Jediný pohyb, ktorý vedia podľa pravidiel spraviť, je poslať Izraelčana číslo \(24\) na \(26.\) miesto. Potom im ostávajú dve možnosti:
\(24.\) Izraelčan zostane na \(26.\) mieste
\(24.\) Izraelčan sa posunie doprava na \(27.\) miesto.
Ak by nastala prvá možnosť, tak spolu s \(25.\) Izraelčanom by vytvorili „dvojblok“, ktorý by Izraelčania s menším číslom neboli schopní prekonať. V druhej možnosti by Izraelčania s číslami 1 až 23 museli sedieť napravo od neho, a teda by zaberali ďalších 23 miest – teda v súčte 50. Resp. by sa \(25.\) Izraelčan musel niekedy posunúť doprava.
Teda sme práve ukázali, že miest musí byť viac ako 49.
Skúsme sa teraz pozrieť, či by to náhodou nefungovalo pre 50 miest. Prvý pohyb zostáva rovnaký, teda presunieme \(24.\) Izraelčana na \(26.\) miesto, teraz však presunieme \(24.\) Izraelčana na \(27.\) miesto, aby sme vytvorili prechod pre menšie čísla. A zároveň je \(24.\) Izraelčan už na svojom mieste.
Takto sa postupne popresúvajú všetci párni Izraelčania od najväčšieho po najmenšieho (Izraelčan s číslom \(24-2k\) sa presunie na miesto \(27+2k\) pre \(0\leq k\leq 11\)). Uvedomme si, že od Izraelčana s párnym číslom, ktorým aktuálne chceme pohnúť, sa napravo nachádzajú len doposiaľ nepohnutí Izraelčania s nepárnymi číslami (a teda aj pozíciami) a Izraelčania s párnymi číslami, ktorí sa pohli na pozície s nepárnymi číslami. Čiže všetky pozície s párnymi číslami sú voľné, a preto nami vybraný Izraelčan vie cez ne preskákať až na svoje miesto.
Potom sa presúvajú všetci nepárni Izraelčania od najmenšieho po najväčšieho (Izraelčan s číslom \(2k+1\) sa presunie na miesto \(50-2k\) pre \(0\leq k\leq 12\)). Opäť si môžeme uvedomiť, že Izraelčan sa tam vie popresúvať, lebo všetci Izraelčania od jeho pôvodnej až po jeho finálnu pozíciu sa nachádzajú na nepárnych pozíciach.
Postup je ilustrovaný na obrázku 1.
Vyššie uvedenou konštrukciou postupných presunov Izraelčanov sme ukázali, že pre 50 miest v rade sa vedia Izraelčania popresúvať tak, aby spĺňali podmienky zo zadania. Keďže sme ukázali, že pre menej ako 50 miest v rade sa Izraelčania nevedia popresúvať tak, aby spĺňali podmienky zo zadania, tak 50 je najmenšie možné \(n\), pre ktoré sa Izraelčania vedia popresúvať podľa zadania.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.