Можно ли квадрате $%10\times10$% по правилам «Морского боя» разместить $%2$% корабля $%1\times4$%, $%4$% корабля $%1\times3$%, $%6$% кораблей $%1\times2$% и $%8$% кораблей $%1\times1$%?

задан 5 Янв '15 17:32

1

Я думаю, что нельзя так кораблики разместить.

(5 Янв '15 19:53) katerina
10|600 символов нужно символов осталось
2

Можно на клеточную доску 10х10 нанести сеточку из точек, расположенных в вершинах клеточек и удаленных от границы доски на 1 клеточку, а между собой на две клеточки. Всех таких точек получится 25. Кораблик 1х4 при любом его расположении будет иметь или 2, или 3 таких точки. Кораблик 1х3 будет при любом расположении иметь 2 такие точки. Кораблик 1х2 будет иметь или 1, или 2 таких точки. Кораблик 1х1 будет всегда иметь 1 такую точку. Находим минимальное число точек, которые должны содержать все кораблики, если бы их можно было расставить: $$2 \times 2 + 2 \times 4 + 1 \times 6 + 1 \times 8 = 4+8+6+8=26$$ А всех точек только 25. Не хватает ! А это значит, что нельзя эти кораблики расставить на доске 10х10.

ссылка

отвечен 5 Янв '15 22:38

10|600 символов нужно символов осталось
2

Для каждого корабля $%m\times n$% рассмотрим его "окрестность", то есть прямоугольник $%(m+1)\times(n+1)$%, содержащий внутри себя корабль, стороны которого удалены на расстояние $%1/2$% от сторон "объемлющего" прямоугольника. Такие окрестности содержатся в квадрате со стороной 11 и не перекрываются друг с другом. Сумма площадей равна $%2(2\times5)+4(2\times4)+6(2\times3)+8(2\times2)=120$%, то есть свободным остаётся ещё один квадратик. Задача оказывается равносильна тому, можно ли квадрат со стороной 11 разбить на прямоугольники заданного вида в заданном количестве.

Рассмотрим 22 линии: горизонтали и вертикали из клеток, пересекающие квадрат со стороной 11. Каждая из них в своём пересечении с прямоугольниками должна содержать нечётное число частей, имеющих нечётную длину. Это значит, что хотя бы одна такая часть должна найтись для каждой линии. Общее же количество таких частей, которые могут возникнуть, равно $%2\cdot2+6\cdot2+2=18$%: по два для каждого из прямоугольников $%2\times5$% и $%2\times3$%, и ещё две с учётом клетки $%1\times1$%. Поскольку $%18 < 22$%, разместить корабли оказывается нельзя.

ссылка

отвечен 5 Янв '15 22:46

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×11

задан
5 Янв '15 17:32

показан
1069 раз

обновлен
5 Янв '15 22:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru