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

[fiviol]

Аркадий и Борис (далее - А и Б), играют в морской бой на m-мерном кубе со стороной в n клеток по следующим правилам

Comments

[saarak]

k(2; 10)=19 уж точно достаточно.

А в целом - хорошая задачка.

[fiviol]

Я знаю стратегию с меньшим k.
Самое сложное будет внятно доказать минимальность. Пока не могу себе представить такого доказательства.

[fdo_eq]

для начала неплохо бы найти k(1, n). Я знаю, как решать эту задачу в несколько измененных условиях: Б обязательно переставляет свой корабль в одну из соседних клеток, в этом случае ответ 1.

[fiviol]

У Б нет кораблей, у него бомбы. :)

k(1,1) = 1 и k(1,n) = 2 при n >= 2, это почти очевидно. Понятно, что k = 1 мало, а для k = 2 стратегия Б: бомбить поля с координатами i и i+1 на i-том ходу.

[fdo_eq]

Понятно. Для ситуации, при которой перестановка корабля обязательна, алгоритм поинтересней :-)

[fiviol]

Первые n ходов бомбим клетки последовательно слева направо, если не попали - следующие n ходов бомбим справа налево.

[saarak]

Нет, про 19 я ерунду сказал. То есть тот план, о котором думал, не работает.

Но есть мысль, играющая на неоднозначности фразы "за конечное количество ходов". При к=1 и абсолютно случайном выборе места стрельбы закон больших чисел гарантирует, что Б убьет А с вероятностью 1.

[fiviol]

С вероятностью ровно 1 - все равно за бесконечное число ходов. :)

Чтобы не было неоднозначности: считаем, что у А чудовищно развита интуиция, и он заранее знает, куда будет стрелять Б.

[saarak]

Я ж говорю -тут хитрая диалектика. Каждая отдельная партия все равно продолжается конечное число ходов.

А интуиция против генератора случайных чисел (включаемого ПОСЛЕ хода А) должна быть бессильна.

[anonymous]

В обычном морском бое досаточно 12 мин.

В общем случае, похоже, что (при n>1) k(m, n) = (n^m-1)/(n-1)+1.

hippie

[fiviol]

Да, я тоже дошел до того, что 12 достаточно. Есть ли возможность доказать, что меньше 12 не достаточно?