Úloha 1.u4: Krychle (4 b)

Zadáno v čísle 23.1.

Řešeno v čísle 23.3.

Zadání

Můžeme na hrany krychle umístit čísla $1, 2, \ldots {}, 12$ (každé právě jednou) tak, aby byl součet čísel na hranách vycházejících z každého vrcholu stejný? Změnila by se odpověď, pokud bychom místo jednoho z čísel museli umístit číslo 13?

Řešení

Nejdříve dokážeme, že čísla jedna až dvanáct na krychli umístit nelze. Pro spor předpokládejme, že to lze. Nechť krychle má vrcholy $A$, $B$, …, $H$ a pro vrchol $v$ si součet na hranách vycházejících z $v$ označíme jako $S_ v$.

Nyní se podívejme na součet $S = S_ A + S_ B + \dots {} + S_ H$. Z pohledu vrcholů dostaneme, že $S = 8s$, jelikož součet na hranách vycházejících z každého vrcholu je stejný (to je ono $s$) a máme osm vrcholů. Z pohledu hran ale dostaneme $S = 2\cdot (1 + 2 + \dots {} + 12)$, jelikož každá hrana do $S$ přispěje v právě dvou vrcholech a na hranách jsou přesně čísla 1, 2, …, 12.

Dáme-li oba vztahy dohromady, zjistíme, že musí platit

\[ 2\cdot (1 + 2 + \dots {} + 12) = 8s,\label{eq:cube} \tag {$\ast $} \]

kde $s$ je onen součet na hranách vycházejících z libovolného vrcholu. Pokud vztah () upravíme, dostaneme:

\[ 78 = 4s, \]

což znamená, že $s = 19,5$. To je ale nemožné, jelikož čísla na hranách jsou celá, a tedy nemohou dát neceločíselný součet. Čísla jedna až dvanáct proto není možné na krychli umístit.

Teď se podívejme, jak může nahrazení nějakého čísla číslem 13 celou situaci změnit. Nahraďme tedy nějaké číslo $x\in \{ 1, \dots {}, 12\} $ třinácti. Nyní můžeme použít stejnou úvahu jako pro čísla jedna až dvanáct, jen s tím rozdílem, že ve vztahu () bude levá strana větší o $2\cdot (13 - x)$. Dostaneme tedy

\[ 91 - x = 4s. \]

Součet $91 - x$ musí být dělitelný čtyřmi, jinak opět dostaneme, že $s$ není celé. Jediná možná $x$ jsou proto čísla 3, 7 a 11, pro která je $s$ rovno 22, 21, resp. 20.

V tuto chvíli udělali mnozí z vás chybu a prohlásili, že jelikož je pro tato $x$ hodnota $s$ celé číslo, lze na krychli čísla jedna až dvanáct, kde číslo $x$ nahradíme třinácti, umístit. To je ale chybná úvaha! To, že je $s$ celé číslo, ještě nestačí. Kdybychom například na hrany krychle umisťovali jedenáct čísel čtyři a jedno číslo 44, pak by bylo $s = 22$, ale stejného součtu ve všech vrcholech nikdy nedosáhneme. Jde totiž jen o nutnou podmínku – pokud čísla na krychli lze umístit, pak je $s$ celočíselné, neboli pokud není $s$ celočíselné, pak čísla na krychli umístit nelze. Ale nemusí platit, že pokud je $s$ celočíselné, pak čísla na krychli umístit lze – to by byla i postačující podmínka. Rozdíl mezi nutnou a postačující podmínkou je dobře vidět na následujícím příkladu: Máme číslo $x$ a zajímá nás, kdy je dělitelné čtyřmi. Postačující podmínkou je, že je $x$ dělitelné osmi – je-li $x$ dělitelné osmi, pak je určitě i dělitelné čtyřmi. Existují ale čísla, která jsou dělitelná čtyřmi, ale ne osmi. Nutnou podmínkou je, že $x$ je dělitelné dvěma – pokud je $x$ dělitelné čtyřmi, pak musí být dělitelné i dvěma, tedy pokud není dělitelné dvěma, pak ani není dělitelné čtyřmi. Ale jistě existují čísla, která jsou dělitelná dvěma, ale ne čtyřmi.

 

Chceme-li tedy tvrdit, že pro $x = 3, 7, 11$ lze čísla na krychli umístit, musíme to ještě nějak dokázat. Nejsnazší způsob je prostě nějaké takové rozmístění najít. Možností, jak to udělat, je mnoho. Můžeme si například všimnout, že možných trojic čísel, které dají součet $s$, je poměrně málo („velká“ čísla jako 13 či 12 nemohou být ve stejné trojici, atd.) a každá taková trojice odpovídá rozmístění čísel na hranách vycházejících z jednoho vrcholu. Snadno dokážeme vybrat některé trojice, které musíme v rozmístění použít (například využijeme to, že ve správném rozmístění se každé číslo vyskytne v právě dvou trojicích). Z těch poté dopočítáme, jak má vypadat celé rozmístění. Nebo si můžeme napsat program, který takové rozmístění najde za nás (pokud existuje). Ani není třeba to dělat chytře, neboť všech možných rozmístění čísel na hrany krychle (včetně těch, které nemají stejný součet ve vrcholech) je necelých 500 miliónů.

Nakonec – příklady rozmístění čísel na krychli splňujících naše podmínky jsou na Obrázku 1.

     
Obrázek 1: Příklady rozmístění čísel na krychli při nahrazení čísla 3, 7, 11 (zleva).

$\mathcal{O}(N)$dra