Какое наименьшее количество выстрелов надо сделать ** доске 9x9 в игре "Морской бой",...

Question

Какое наименьшее количество выстрелов надо сделать на доске 9x9 в игре "Морской бой", чтобы гарантированно подбить четырехпалубный  корабль?​

Comments

Значит, если сделать меньше 20 выстрелов, то один из этих кораблей останется не задет, этот корабль может оказаться данным в условии. Таким образом, необходимо сделать 20 выстрелов (по синим клеткам).  

---

Каждый четырехпалубный корабль занимает по одной клетке каждого цвета. Синих клеток всего 20. Значит, если сделать двадцать выстрелов по всем синим клеткам, то будет задет любой четырехпалубный корабль. Заметим, что из доски 9x9 можно вырезать 20 непересекающихся четырехпалубных кораблей, как показано на рисунке.

---

у красного 21 поле у всех остальных по 20. Нам нужно найти минимальное количество полей, то рассматриваем любой другой цвет, к примеру синий

---

красный, зеленый, желтый и синий

Answer 1

Ответ:

  21 выстрел

Пошаговое объяснение:    

  Для начала разделим поле на части, в которых полностью поместятся четырёхпалубные корабли. Это 8х8(рис.1). Получаем 18 возможных расположений. У нас остались два поля 1х9. Их тоже разделяем на 1х8 и 1х8(рис.2). Получилось ещё по два корабля + осталась клеточка 1х1(угловая). Получаем 20 кораблей + 1 клетка = 21 выстрел.

   Отсчитываем три клетки вниз/влево, ставим точку и стреляем так же по диагонали

  Это работает со всеми типами полей и кораблей, расположенных на нём.

  К примеру возьмем поле 6х6. Также находим мин.кол-во выстрелов для поражения четырехпалубного корабля. Разделяем поле 6х6. Разделим поле на 4х4(рис.3). Получаем 4 корабля. Разделяем на два поля 2х4(рис.4) и получаем ещё 4 корабля. Итого: 8 кораблей + поле 2х2.

  В первом случае, у нас остался квадрат 1х1, прибавляем 1 к нашим кораблям и получаем кол-во выстрелов

  Во втором случае, у нас остался квадрат 2х2, прибавляем 2 к нашим кораблям и получаем кол-во выстрелов.

   Рисунки => дополнение. Решать математическим способом(см.выше)