pro gnomov - okonchanie
Uzhe rasskazany
1. perevod na grafskij jazyk i
2. ocenki; teper'

3. Konstrukcii.


Proshhe vsego spravit'sa so zlobnoj Belosnezhkoj. Nado rasstavit' strelki na vsex rebrax tak, chtoby iz kazhdoj ploxoj vershiny vyxodilo 7, i v kazhduju xoroshuju vxodilo 7: togda verojatnost' udachi budet rovno 1/2. Reshenie edinstvenno, s tochnostju do obrashhenija vsex strelok: strelki idut ot vershin s nechetnym chislom edinic k vershinam s chetnym chislom. Na gnomjem jazyke: esli vidish' nechetnoe chislo chernyx shapochek, krichi "chernaja", inache krichi "belaja".

Konstrukcija dlja samoj pervoj Belosnezhki - samaja krasivaja. Nado razbit' ves' 7-mernyj kub na "ezhiki" - puchki iz 7 strelok, vyxodjashhix iz ploxoj vershiny. Ezhikov budet 128/(7+1)=16, i ix centry obrazujut sovershennyj kod s rasstojaniem 3 - t.e.
rasstojanija mezhdu centrami ne men'she 3 (a to by ezhiki peresekalis'), i kazhdaja vershina - libo centr, libo rjadom s edinstvennym centrom (a to by ne vse pokrylos').
Kody takie est' v ljuboj razmernosti n=2^k-1, naprimer, pri n=7=2^3-1. Estestvenno, chto v drugix razmernostjax takix kodov byt' ne mozhet: ne delitsa 2^n na n+1 :)
A pravilo dlja gnomov? Tozhe terpimoj slozhnosti.
Razdat' kazhdomu nomer (ot 1 do 7), zapisannyj v dvoichnoj sisteme: 001, 010, ..., 111. Gnom schitaet pobitovuju summu vsex nomerov s chernymi shapochkami. Esli summa 0, krichi "chernaja". Esli summa ravna tvoemu nomeru, krichi "belaja". Inache - molchi.
Sobstvenno, eto i est' opredelenie koda Xemminga (the Hamming code), i obobshhaetsa na ljuboe n=2^k-1.

Chto delat' s demokratichnoj Belosnezhkoj?
Rasstavim snachala strelki po kodu Xemminga. Neorientirovannye rebra obrazujut graf stepeni 6 (v kazhdoj vershine - 6 reber). rasstavim na nem strelki, chtob v kazhduju vxodilo 3, i iz kazhdoj vyxodilo 3. Eto vozmozhno sdelat': naprimer, najti ejlerov cikl, i sorientirovat' vse rebra vdol' nego. Chego ja tak i ne smog pridumat' - eto takogo pravila dlja gnomov, chtob bylo pod silu ix mozgam:) Chtob ne prishlos' vyxodit' s ogromennymi bumazhnymi prostynjami i po nim vychityvat' otvet.
Mozhet, kto pridumaet?:)


...
Vot. A Belosnezhka, kak vidite, i vovse ni pri chem. Ponadobilas' ona, slovami Shtirlica, chtoby "zamotivirovat'" chislo 7.