Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3809862
А
Аноним
12 часов назад · публичный вопрос
А
Аноним

Задача 1 Гарри и Рон играют в морской бой на поле 9 × 9 по необычным правилам. У Гарри только один корабль 1 × 5, а у Рона кораблей нет и стреляет только он.

Запрос пользователя

Реши

Ответ нейросети
12 часов назад

Ответ: 16 выстрелов.

Пронумеруем строки и столбцы от 1 до 9. Рон может простреливать всю среднюю строку и весь средний столбец, кроме их пересечения — центральной клетки. Это \[ 8+8=16 \] клеток.

Почему этого хватает:

  • если корабль стоит горизонтально не в средней строке, то в любой пятёрке подряд идущих клеток из девяти обязательно есть 5-й столбец, а он прострелен;
  • если корабль стоит горизонтально в средней строке, то в этой строке прострелены все клетки, кроме центральной, поэтому корабль длины 5 не сможет целиком спрятаться в непростреленной клетке;
  • для вертикального корабля рассуждение такое же.

Почему 15 выстрелов недостаточно.
Пусть удалось обойтись 15 выстрелами. Если их меньше, добавим недостающие — гарантия попадания не ухудшится.

В каждой строке должен быть хотя бы один выстрел, иначе корабль можно поставить в эту строку. Если в строке ровно один выстрел, он обязан находиться в среднем столбце: только эта клетка входит во все возможные пятёрки подряд идущих клеток строки.

Пусть \(k\) — число выстрелов в средней строке. В остальных 8 строках всего \(15-k\) выстрелов. После одного обязательного выстрела в каждой из них остаётся \[ (15-k)-8=7-k \] «лишних» выстрелов. Значит, строк с ровно одним выстрелом среди этих восьми не меньше \[ 8-(7-k)=k+1. \] Все эти выстрелы лежат в среднем столбце, поэтому в среднем столбце хотя бы \(k+1\) выстрелов.

Аналогично, если в среднем столбце \(l\) выстрелов, то в средней строке должно быть хотя бы \(l+1\) выстрелов. Получаем: \[ k\ge l+1,\qquad l\ge k+1, \] то есть \(k\ge k+2\) — противоречие. Значит, 15 выстрелов не хватит.

\[ \boxed{16} \]