Zoradenie kartičiek
Zdravím dostal som nasledovnú úlohu.
Máme 10 kartičiek, na každej z nich je napísané celé číslo od 0 do 4 tak, že každé číslo je napísané dva krát. Možno ich zoradiť do ratu tak, aby medzi dvoma výskytmi čísla K bolo presne K kartičiek?
Dá sa to aj po pridaní dvoch kartičiek s číslom 5?
Našiel som riešenie pre 4 ale pre 5 sa mi nedarí nájsť.
Dá sa nejak dokázať že to je/ nie je možné?
Dik :)
Andy P.
14. 11. 2020 13:02
1 odpověď
Tohle je docela těžká úloha, zní mi spíš jako něco z olympiády.
Třeba pro 10 kartiček bys měl najít hned 4 řešení najednou, ale najít všech 10 řešení už tak lehké není. Dokázat pro 12 kartiček, že rozestavení není možné, to se dá, ale neřekl bych, že to středoškolák dokáže pochopit.
Poměrně jednoduchá varianta důkazu je převést kombinatorickou úlohu na početní. Převedeš si každou dvojici karet do dvojkové soustavy, např. 3xxx3 má hodnotu 10001. Posouvání čísla doleva se dá také vyjádřit ve dvojkové soustavě pomocí násobení 2^k. A pokud existuje korektní řešení po 12 kartiček, pak součet dvojic ve dvojkové soustavě musí dávat 111111111111 = 2^12 - 1
Z toho se odvodí rovnice, kde 2 * (součet pozic) + 21 = 66. Jenže po úpravě platí (součet pozic) = 45 / 2 a to je nesmysl. Každá pozice musí být celé číslo, tím pádem 12 kartiček nemůžeš uspořádat podle daných pravidel.
Sice je to jen středoškolská matematika, ale způsob řešení převedením na jiný problém už je vyšší dívčí.
