March 26th, 2015

Водолаз

- Приключений маловато, - сказали игроки в функциональный морской бой.

Аркадий и Борис (далее - А и Б), играют в морской бой на m-мерном кубе со стороной в n клеток по следующим правилам.
Игрок А ставит однотрубный корабль в произвольную точку куба, не известную Б.
На своем ходе Б называет любые k клеток, по которым он проводит бомбардировку. Если на одной из этих клеток находится корабль, Б выиграл.
В противном случае ходит А: он либо оставляет свой корабль в той же клетке, либо сдвигает его в любую клетку, имеющую с ней хотя бы одну общую точку. После этого ход снова переходит к Б.
При каком наименьшем k (в зависимости от m и n) Б наверняка сможет выиграть за конечное количество ходов?

Для начала: найти k(2; 10), то есть решить задачу для обычного квадратного поля 10*10.