Zadanie

Newyorkskí stredoškoláci trávia svoj voľný čas streetballom. Nemajú tam totiž KMS. Najlepšie sa hrá takej partii, ktorá sa vie rovnomerne rozdeliť.

Nájdite všetky šestice po sebe idúcich prirodzených čísel, ktoré je možné rozdeliť do dvoch skupín (nie nutne rovnako veľkých) s rovnakým súčinom.

Po chvíľke skúšania a hľadania nadobúdame dojem, že taká šestica neexistuje. Tak sa to pokúsime dokázať. Ak majú mať dve skupiny čísel rovnaký súčin, musia mať oba súčiny v rozklade na prvočísla rovnako veľa toho istého prvočísla. Teda ak v rozklade prvého súčinu máme \(p^k\), potom aj v druhom rozklade musí byť \(p^k\). Preto sa pozrieme na jednotlivé prvočísla.

Najskôr sa pozrieme na prvočísla väčšie ako 6. Ak nejaké prvočíslo \(p > 6\) delí niektoré z čísel \(a,\, a+1,\, \dots,\, a+5\), označme si to číslo \(a+k\), tak delí aj čísla \(a+k-p\) a \(a+k+p\), obe zjavne nepatria medzi \(a,\, a+1,\, \dots,\, a+5\). No a na to, aby sme tú skupinu rozdelili , tak potrebujeme aby \(p\) delilo aj iné číslo ako \(a+k\), aby sme ho mohli dať do druhej skupiny. Keby nedelilo, tak rozklady na prvočísla sa nezhodujú, a teda nemôžu sa súčiny rovnať. To ale znamená, že v prvočíselnom rozklade čísel \(a,\, a+1,\, \dots,\, a+5\) budú len prvočísla 2, 3, 5 a každé musí deliť aspoň dve čísla.

Teraz máme na výber viacero možností, čo s tým. Môžme skúsiť všetky možnosti, ako by mohli prvočísla deliť \(a,\, a+1,\, ...,\, a+5\). Môžme sa taktiež pozerať na zvyšky po delení číslami 2, 3 alebo 5. My sa najprv pozrieme na zvyšky po delení piatimi.

O číslach deliteľných piatimi vieme, že majú byť dve a vieme, že rozdiel dvoch rôznych čísel deliteľných piatimi je aspoň 5. Jediné dve čísla z \(a,\, a+1,\, \dots,\, a+5\), ktoré majú rozdiel 5 sú \(a\) a \(a+5\). Na tento fakt ste prišli viacerí, a to vám mohlo nahintiť deliteľnosť piatimi. Teraz máme čísla \(a+1,\, \dots,\, a+4\). Z nich sú deliteľné dvoma buď \(a+1\) a \(a+3\), alebo \(a+2\) a \(a+4\). Teraz by sme potrebovali, aby tie čísla, čo ostali, boli deliteľné tromi, teda buď \(3 \mid a+2\) a \(3 \mid a+4\), alebo \(3 \mid a+1\) a \(3 \mid a+3\). No ale tieto čísla sú od seba vzdialené o dva, a teda aj keby 3 delilo jedno z nich, nedelí to druhé. Čo znamená, že vždy máme nejaké číslo, ktoré je nedeliteľné ani dvomi, ani tromi, ani piatimi. Môže to byť už len číslo 1 (prvočísla väčšie ako 6 sme už zakázali), ale jediná šestica obsahujúca 1 je 1, 2, 3, 4, 5, 6. A tá zjavne nevyhovuje.

Záver je, že žiadna šestica po sebe idúcich čísel sa nedá rozdeliť do dvoch skupín s rovnakým súčinom.

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ť.