Предмет: Математика, автор: stefanikris

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

stefanikris: ответ 20

stefanikris: Раскрасим данную доску по диагоналям в 4 цвета, как показано на рисунке.

stefanikris: например начнем с правого верхнего угла

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

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

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

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

Ответы

Автор ответа: Аноним

Ответ:

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 к нашим кораблям и получаем кол-во выстрелов.