Шахматная головоломка

vitamin8808

На бесконечной шахматной доске-плоскости играют два игрока. У первого есть только король, который может ходить как в обычных шахматах на любую из соседних 8-ми клеток. А у второго(будем называть его Дьявол ) вообще нет фигур, но каждым ходом он может из доски выжеч одно поле(если на нём не стоит король). Ходить по выжженым клеткам королю не разрешается. Вопрос — может ли Дьявол полностью лишить короля ходов за конечное число ходов(запатовать по шахматному) или же есть стратегия, по которой король всегда может убежать ?

soldatiki

Думаю, у короля есть выход.
Надо выбрать произвольное направление, например, вверх, и двигаться каждый раз по диагонали вверх и вправо или вверх и влево. Тогда король выходит за пределы любой полуплоскости, ограниченной горизонтальной прямой. Если дьявол начнет строить сверху горизонтальную стенку, надо идти, скажем, вправо и делать все то же самое. Построить две стенки (сверху и справа) дьявол, очевидно не успеет. Фишка в том, чтобы не делать много "обратных ходов" к первоначальному месту. Одна из координат должна монотонно возрастать.

plugotarenko

дело в том, что дьяволу не нужно строить плотную стенку, Главное, успеть закупорить, если король идет на прорыв. поэтому можно успеть построить узлы стенки и достраивать по мере попыток короля прорваться.
Ни мое, ни твое рассуждение --- ни есть доказательство, но я бы поставил скорее на Дьявола.

vitamin8808


дело в том, что дьяволу не нужно строить плотную стенку, Главное, успеть закупорить, если король идет на прорыв. поэтому можно успеть построить узлы стенки и достраивать по мере попыток короля прорваться.
Ни мое, ни твое рассуждение --- ни есть доказательство, но я бы поставил скорее на Дьявола.

всё верно. Помешанным на строгости рассуждений(таким как я ) остаётся только строго доказать. Правда я не находил конкретные размеры квадрата, в который можно запихать короля, просто доказал что для достаточно большого n из квадрата nxn не вырваться. Как раз из-за того, что надо идти на прорыв. Он блокируется, а на другой прорыв идти уже поздно. Ситуация для короля только ухудшается.

slsf

Следует начать с того, что задачу Вы поставили совершенно некорректно.
Вы не указали конечно ли число ходов, если же оно не конечно, то вообще никакой головоломки нет, хотя решение и противоречит интуиции.
А вот Ваше решение хотелось бы увидеть, если оно строгое.

mtk79

Я думаю, по-любому королек вырвется

vitamin8808

Следует начать с того, что задачу Вы поставили совершенно некорректно
какой ужас. я так понимаю, вообще никакую нельзя нормально сформулировать. Предыдущую задал, сказал, вроде, что информацией нельзя обмениваться, так ещё спросили, а кванты времени можно считать(ага, и супер струнами пользоваться....). Блин, задачки для школьников, не мутите воду на ровном месте.

slsf

Сэр, Вы уходите от ответа, позвольте заметить. Хотелось бы видеть Ваше строгое школьное решение.
Если можно.

stm2515023

Решение не скажу, разобью на подзадачки:
1) докажите, что можно не выпустить короля из какой-то полуплоскости.
2) докажите, что можно не выпустить короля из четверть плоскости.
3)ну и решите исходную задачу.
С полуплоскостью понятно - заметим, что если на прямой уже заблокированы две трети точек (то есть две подряд заблокированы, одна нет и т.д. то если король стоит не в плотную к этой прямой, то он уже ее не пересечет. Дальше доделайте сами.
С углом примерно та же фигня, надо только иметь фору (начать в дали от короля) что бы несколько лишних клеток в углу заблокировать.
Вот в трех-мерном случае кажется все не так просто. Мне даже кажется, что ответ другой.

vitamin8808

я так и решал, по кускам, только сначала доказал, что из угла можно не выпустить. А про 3-мерный случай я, как шахматист, и не подумал

greekdom

Вот в трех-мерном случае кажется все не так просто. Мне даже кажется, что ответ другой.
Маза сразу рассмотреть N мерный случай.

plugotarenko

Похоже, что в трехмерном случае нельзя даже удержать короля в каком-либо полупространстве. Так что в трех и более мерном случае король чувствует себя более чем вольно.

mtk79

С углом примерно та же фигня, надо только иметь фору (начать в дали от короля) что бы несколько лишних клеток в углу заблокировать.
— какая "та же фигня" ? : Вы ссылаетесь на то, что "все понятно". Окружающим же не понятно ничего.
давайте сыграем: Вы называете натуральное N и гарантируете, что король не вырвется из квадрата N*N (доска с самого начала ограничена прямым углом а мы посмотрим Ваше док-во

greekdom

Так что в трех и более мерном случае король чувствует себя более чем вольно.
Следовательно дьяволу нужно дать возможность выжигать прямые и проскости.

STASSS

а вот интересно на каком минимально расстоянии надо квадрат строить чтоб он гарантировано не сбежал

kachokslava

ну, например для 21х21 и если король начинает в углу и первым делает ход, то он убежать не может

mtk79

В исходной задаче (где доска бесконечная) первый ход делает диавол. Поэтому и в редуцированной д.б. нечто подобное.
Откуда взялось сие магическое число?

iri3955

Ага. разиерности - не те...
Там были путь короля и граница области размерности один, а здесь один и два соответственно.

kachokslava

взял и на бумажке проверил, что на 21 гарантировано не убежит.
В исходной задаче всё-таки первым делает ход король.
ща проверил, вроде и на 10 не убежит. нет, убегает...
а вот на 13 уже ловится

a101

Кстати, если я не ошибаюсь, то каждый пятый ход дьявол может курить сигаретку и вообще не ходить (или стрелять в рандомное место). Точно не помню, давно проверял

a101

А, и задача была чуточку другая. Там первый игрок ходил не королем, а ставил крестик на любую клетку, соседнюю с уже поставленными.

gvo83

Закрытые клетки: т. е. недоступные королю. Число закрытых клеток всегда считается конечным.
Опр. Расстояние между двумя клетками А и Б — мин. число ходов, необходимое Королю, что бы, находясь на А, попасть на Б, на чистой доске.
Опр. (для любого натур. n) n-разрядный отрезок — длина кратна n, закрыты первая клетка и все последущие, через n (остальные клетки отрезка могут быть любыми).
Утв. Для любого натур. n и любого n-разрядного отрезка существует алгоритм закрытия клеток (т. н. агоритм заклейки действующий лишь при нахождении Короля на расстоянии <=n от отрезка (мин. расстояние до какой-либо клетки отрезка и не дающий Королю возможности стать на отрезок. Начальное положение Короля должно находиться на расстоянии >n от каждого конца отрезка.
Пример алгоритма заклейки: если "под" Королем на отрезке открытая клетка, закрыть ее; иначе добавить одну клетку на меньшую часть подотрезка из закрытых клеток, находящегося на рассматриваемом отрезке "под" Королем (если части равны, удлинить любую; возможно удлинение за пределы отрезка).
Окружив теперь Короля квадратом со сторонами из 24-разрядных отрезков (длиной 6*24) за 23 хода, и применяя (вблизи внутренней границы квадрата) модификацию алгоритма заклейки — на трапециях с полупрямыми углами, сторонами квадрата в основаниях и высотами 24 - обычную заклейку (на общих боковых гранях - к тому отрезку, к которому она была начата, иначе - к любому из двух соседних но с удлинением не по прямой отрезка, а по периметру квадрата — либо случайное заполнение квадрата (во внутренней области за конечное число приведем Короля к пату.
Размеры квадрата могут быть сильно уменьшены.
Начальная очередность ходов не важна, т. к. первый ход является мнимым, если это ход Короля.

MerKish

Это тривиальная часть известной задачи под названием "Охота на снарка", которая, в частности, в 2001 году была предложена на летней конференции турнира городов. Вот все задачи турнира с решениями.
Общая формулировка такая:
Булочник охотится на Снарка на бесконечной клетчатой плоскости. Снарк за один ход может прыгнуть с клетки (х, у) на любую клетку (х', у' где |х - х'| <= n, |у - у'| <= n. Число n называется скоростью Снарка. Булочник своим ходом может положить булочку на любую пустую клетку. Снарк ненавидит булочки, поэтому он никогда не прыгает на клетку с булочкой. Цель Булочника — запереть Снарка, так чтобы ему некуда было прыгнуть. Цель Снарка противоположна.
Общая постановка вопроса: при каких n снакр может убежать от булочника, а при каких - булочник может его запереть.
Нерешённая проблема:
Хотя бы для какого-нибудь одного n > 1 выясните, кто сможет добиться поставленной цели: Булочник или Снарк.
Над этой задачей ломали голову очень крутые дяденьки международного маштаба, но никто ничего не придумал (по данным на 2001 год).
Для n = 1 решение довольно простое. Можете пройти по сцыле вверху поста и почитать. Там есть ещё несколько интересных рассуждений по поводу этой задачи, но никаких существенных продвижений для случая n > 1 никто не придумал. 8(

soldatiki

Маза сразу рассмотреть N мерный случай.
Да ладно, че там, давайте сразу в банаховом пространстве рассмотрим... Дьявол может выжигать любые конечномерные подпространства или что-то типа того...
Оставить комментарий
Имя или ник:
Комментарий: