Смерть линкора

*

Сложность: 

Какое наименьшее число «выстрелов» надо сделать, чтобы в игре в «морской бой» наверняка хотя бы один раз попасть в линкор, одиноко плавающий по морю? Напомним, что в «морской бой» играют на квадрате 10×10, а «линкором» в этой игре называется «корабль» 1×4.

Решение

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

Каждый «линкор» при любом своём расположении закрывает четыре клетки разного цвета. Логично предположить, что наименьшее число выстрелов, требуемых для того, чтобы наверняка его подбить, равно 24 — числу клеток цвета 3 (клеток остальных цветов больше). Докажем, что в общем случае за меньшее количество выстрелов это сделать не удастся.

Собственно, это следует из того, что на игровом поле одновременно можно разместить 24 линкора:

Если сделать 23 выстрела, то как минимум один линкор останется невредимым. Значит, в общем случае 23-х выстрелов недостаточно, чтобы наверняка подбить одиноко плавающий линкор.




Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.