О бедном гусаре замолвите слово

[iad58]

Így szól Medve: Treffünk, édes húgunk,
Ünnepére nem bűn, ha berúgunk!
Teljesüljön minden jókivánság,
Amelyet ma kiáltunk vagy súgunk!

Azaz: Boldog születésnapot!

---

Nemrég jelentek meg ezek a kérdések:

1. Hányféleképpen bejárhatja a huszár a fél sakktáblát (4×8), feltéve, hogy bármilyen mezőről indulhat?
2. Ha úgy színezzük a táblát, hogy a huszár útján ugyanabban a sorban akadjanak a színek, mintha a táblát soronként „olvasnánk”, és minél több színet használunk, mi a színek minimális és maximális száma?

Íme a válaszok:

1. A 4×8 táblán a huszárnak 62176 útja van. (Vagyis 15544 különböző út, tekintetbe véve a tábla szimmetriáját. A másik feladat szempontjából azonban a tükörszimmetria nem számít, csak a forgásszimmetria.)
2. A színek legkisebb száma 1; ennek egy példája volt is már.

   Színek száma Utak száma 1 1904 2 7964 3 14486 4 16050

   Színek száma Utak száma 5 12134 6 6096 7 2386 8 882

   Színek száma Utak száma 9 194 10 62 11 16 12 2

   A színek legnagyobb száma 12; ilyen út csak kettő van:

   1 18 13 28 11 24  7 22 14 31 16 19  4 21 10 25 17  2 29 12 27  8 23  6 30 15 32  3 20  5 26  9

   illetve

   24  7 28 13 30  1 18  3 27 10 25  6 21  4 31 16  8 23 12 29 14 17  2 19 11 26  9 22  5 20 15 32

Comments

Буквы не понял :)

[fiviol.livejournal.com]

А картинка, разумеется, одна и та же (повернутая вокруг центра на 180 градусов и каждый номер n хода заменен на 33-n).
Верно ли я понял? 62176 - количество способов обойти поле конем, тогда 15544 = 62176/4 - это существенно разные способы (не получающиеся друг из друга симметриями доски). Однако из 4 симметричных способов обхода одинаковыми (точнее, симметричными же) раскрасками обладают только центральносимметричные (в то время как при осевой симметрии раскраска, очевидно, изменяется существенно). То есть 62176/2 = 31088 существенно различных раскрасок.
А способов обхода, при котором раскраска содержит всего 1 цвет - 1904/62176, что очень близко к 1/32, как и предполагалось.
Очень интересная задачка и интересные (я бы сказал - красочные) результаты. Спасибо.

Цифры зато понял!

[iad.livejournal.com]

Все именно так.

Только подскажи, почему предполагалось, что число способов обхода, при котором раскраска содержит всего 1 цвет, будет близко к 1/32 общего числа способов обхода? То есть на основании чего можно было это предвидеть?

Re: Цифры зато понял!

[fiviol.livejournal.com]

Я в прошлом твоем посте об этом уже писал:
Каждый обход конем порождает перестановку из 32 элементов: номеру поля ставится в соответствие номер хода. Но все перестановки разбиваются в произведение независимых циклов (в твоей задаче каждый цвет как раз и соответствует независимому циклу). Всех перестановок 32! = 1*2*...*31*32, а тех, которые являются одним независимым циклом 31! = 1*2*...*31. То есть их доля среди всех перестановок ровно 1/32. Вот я и предполагал, что среди перестановок, порождаемых ходом коня, их доля примерно такая же.

Re: Цифры зато понял!

[iad.livejournal.com]

Я хотел спросить, почему тех перестановок, которые являются одним независимым циклом, — 31!; тем временем, однако, я нашел причину.

[treff.livejournal.com]

Köszönöm szépen kedves Medve-bátyám!