/* Горизонт */

    Здравствуйте!
Ответы

    Сегодняшний выпуск целиком будет посвящен ответу на задачу Скотта Пурди (Scott Purdy) "Ферзи на роликовых коньках":
    Ферзь может перемещаться на любое количество клеток шахматной доски по вертикали, горизонтали или диагонали. Ферзь же на роликовых коньках (ФРК) должен перемещаться до тех пор, пока не столкнется со стеной, либо преградой (которая занимает ровно одну клетку). Каково минимальное количество преград, которое бы позволило ФРК остановиться у любой клетки. Каково максимальное количество ходов, которое требуется ФРК, чтобы переехать с одной клетки на другую?
    Размер доски - любой, но больше интересуют доски 8х8, 9х9, 10х10 и выше.
    Фёдор Меньшиков заметил некоторые неточности в условии, поэтому необходимо добавить два следующих уточнения:
  1. При данной конфигурации преград ответ истинен, независимо от того, на какой клетке изначально расположен ФРК.
  2. Под максимальным количеством ходов понимается максимальное количество ходов без повторения точек остановки, то есть нельзя бесконечно бегать по одному и тому же маршруту.
    Все нижеследующие решения нашел JP Ikaheimonen, Федор Меньшиков нашел все решения за исключением доски 11х11, также он подсчитал количество вариантов решения.
Доска 5х5 5x5 - 1 ФРК Решение единственное
Доска 6х6 6x6 - 4 ФРК 369 решений вместе с отражениями и поворотами
Доска 7х7 7x7 - 5 ФРК 2069 решений с отражениями и поворотами
Доска 8х8 8x8 - 6 ФРК 3 уникальных решения, с отражениями и поворотами 18
Доска 9х9 9x9 - 9 ФРК Теоретически доказано, что меньше 9 преград недостаточно. Решений с девятью преградами много.
Доска 10х10 10x10 - 12(?) ФРК С 12 преградами решений много, для 11 преград полный перебор не был произведён (кое-что, конечно, было проверено, так что я убедил хотя бы себя использовать 12). Внимание, не доказано (и не получено), что 11 нельзя.
Доска 11х11 11x11 - 13 ФРК

    12x12 и более современный компьютер никак не тянет. Хотя... если перебирать только симметричные... тогда тянет. В любом случае из приведённых симметричных решений что-то вырисовывается (по крайней мере из 5x5 - 11x11, в 12x12 я не нашёл продолжения)- может, кто-то уловит закон и найдёт решение для 12x12. Первоочередной проблемой в таком случае будет определение, действительно ли получившееся решение обладает свойством минимума преград. Судя по всему, неразрешимой. Однако для 12x12 доказано, что меньше 16 преград нельзя - если кому удастся за 16, задача о минимуме не встанет.

Теория

    Для доски размера 3*n+2 число преград не может быть менее n*n.
    Действительно, чтобы можно было остановиться у любой клетки, нужно, чтобы с ней соседствовала или преграда, или край доски. Если не учитывать края, будет доска размером 3*n. Каждая преграда может взять на себя максимум девять клеток - восемь соседей, одна под преграду. Получаем: (3*n)*(3*n)/9=n*n. Очевидно также, что такое размещение единственное, ибо квадраты 3x3 с преградами в центре должны стоять вплотную, не пересекаясь.
    Однако минимум (n*n) не достигается почти всегда (n>1):
недостижимость минимума - каждая клетка имеет соседа: или преграду, или стену. Однако красная клетка недостижима.

    Для доски размера 3*n+3 число преград не менее (n+1)*(n+1).
    Действительно, уберём клетки по границе доски. Размер станет 3*n+1. Разобьём доску на вертикальные столбцы шириной 2,3(n-1 штук),2 клеток.
    Установим в первом (слева) столбце (ширины 2) несколько преград так, чтобы ими был покрыт весь левый ряд клеток. В высоту он составляет 3*n+1. Одна преграда может относиться только к трём клеткам в столбце. Значит, все клетки этого ряда можно покрыть используя не менее чем n+1 преграду. Преграда должна находиться в этом столбце ширины 2, иначе она не сможет "дотянуться" до крайнего ряда.
    Установим в следующем столбце (ширины 3) несколько преград так, чтобы они покрывали все клетки среднего ряда этого столбца. Таких преград тоже не менее n+1, т.к. на этот ряд не влияют преграды соседних столбцов. И так для каждого столбца ширины 3.
    В последнем столбце так же покрываем крайний правый ряд с помощью не менее чем n+1 преград.
    Итого n+1 столбцов с не менее чем n+1 преградами в каждом. Следовательно, требуется не менее чем (n+1)*(n+1) преград.
    Для доски размера 3*n+4 число преград тоже не менее (n+1)*(n+1). Меньше быть не может, т.к. иначе доска меньшего размера 3*n+3 покрывалась бы тем же количеством преград. А (n+1)*(n+1) преград покрывают всю доску, т.к. они же покрывают большую доску размера 3*n+5 = 3*(n+1)+2.

    Теперь об оценке сверху необходимого числа преград.     Рассмотрим бесконечную (достаточно большую) доску с повторяющимся узором преград. Покажем, что из любой точки этого узора можно попасть в любую другую. Для этого достаточно показать, что из 6 можно попасть в каждый из 1, 2, 3, 4, 5 а из них - в 6.
бесконечная доска с 1/7 преград
6-7-1 1-5-6
6-3-8-4-2 2-5-6
6-3 3-5-6
6-3-8-4 4-6
6-3-5 5-6

    Следовательно можно достичь 1/7 преград от общей площади доски, то есть для доски NхN верхняя граница количества преград NхN/7.
Задача о максимуме ходов

8 преград, 55 ходов

Задача о ладьях

    Естественно, роликовые коньки можно надеть и на ладью. Задание будет тем же самым, за исключением того, что ладья не может двигаться по диагонали.
    До встречи!

Ведущий рассылки - Сумароков Стас,
Сайт рассылки - http://golovolomka.hobby.ru