1
1

На шахматной доске размером $%n \times n$% сидят муха и два паука. Каждым ходом муха может переползти в клеточку, которая имеет общую вершину с клеточкой, где она находится (она также может остаться на месте). Каждым ходом пауков, каждый паук может переместится в клеточку, которая имеет общую сторону с клеточкой, где он находится (он также может остаться на месте). Если паук и муха окажутся в одной клетке, то пауки выиграют. Имеют ли пауки выигрышную стратегию?

задан 17 Мар '16 21:43

перемечен 19 Мар '16 15:57

Trumba's gravatar image


74118

10|600 символов нужно символов осталось
2

Пауки всегда смогут поймать муху).

Для этого :

  1. поставим их рядом друг с другом на одной горизонтали.

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

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

ссылка

отвечен 19 Мар '16 16:09

а пауки могут одновременно ходить что-ли?

(19 Мар '16 16:36) Trumba

Каждым ходом пауков, каждый паук может .....

(19 Мар '16 17:00) Sergic Primazon

Если ходит один из пауков, то все равно каждый_паук_может...

В общем, я решал не ту задачу, которую решали Вы. Вроде как обе задачи неплохи.

(19 Мар '16 17:04) Trumba

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

(19 Мар '16 17:18) Sergic Primazon
10|600 символов нужно символов осталось
1

Я начну, чтобы задача не потерялась.

А пауки могут находится одновременно в одной клетке? Считаю, что да.

Чтобы "зажать" муху, ее необходимо (но не достаточно), прижать к стенке - она тогда может пойти максимум на 5 клеток, однако пауки могут занять 2 клетки и соседствовать еще с 3-я клетками (например, муха с координатами $%(1;4)$%, пауки - $%(2;3)$% и $%(2;5)$%). Если же муха сможет не попасть к стенке, значит поймать ее будет нельзя - ей будет доступно 8 вариантов хода, а пауки могут контролировать только 6 клеток. Доска - метрическое пространство с манхэттенской метрикой, причем скорость пауков = 1, а скорость мухи = 2, когда она ходит по диагонали, потому при достаточно большом $%n$% муха всегда может просто убежать от пауков, оставаясь при этом на внутренней части доски. (Это явно неполное рассуждение, его надо допиливать, т.к. идейно его д.б. достаточно. Либо другой вариант - муха выбирает одного паука и бегает вплотную возле его плюсика по диагонали, избегая 2-го паука и стен, только он тоже плохо формализован.)

Паучков можно мыслить как плюсики, ширина плюсика - 3, ширина 2-х плюсиков - 6. Если муха попала в края плюсика, то ей надо обязательно оттуда убежать, иначе она проигрывает. Плюсики могут закрыть всю горизонталь при $%n\leqslant 6$%, а если учесть, что пауки ходят попеременно, плюсики могут образовывать множество, разделяющее доску на 3 части только при $%n\leqslant 5$%. При этих $%n$% паукам достаточно встать в самый низ $%2$%-й и $%n-1$%-й вертикали и идти вверх, ожидая, если нужно, после чего они зажмут муху у верхней стенки.

При $%n\geqslant 6$% эта стратегия точно не работает - умная муха может встать у места сочленения плюсиков и пробежать их, как только хотя бы один паук сходит (при этом ей есть куда ходить).

Вроде бы при $%n\geqslant 6$% муха в общем случае не ловится, но пока доказать не получается.

ссылка

отвечен 19 Мар '16 15:27

у меня пауки ходят по одному

(19 Мар '16 16:36) Trumba
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×77
×69
×32
×22

задан
17 Мар '16 21:43

показан
1133 раза

обновлен
19 Мар '16 17:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru