ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116278
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Принцип Дирихле (прочее) ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

Два муравья проползли каждый по своему замкнутому маршруту на доске 7×7. Каждый полз только по сторонам клеток доски и побывал в каждой из 64 вершин клеток ровно один раз. Каково наименьшее возможное число таких сторон, по которым проползали и первый, и второй муравьи?


Решение

Пример, где число "общих" сторон равно 16, приведён на рисунке (один маршрут чёрный, другой – красный).

Оценка. Каждый из муравьев посетил по 64 разные стороны. Всего сторон  7·8·2 = 112.  Следовательно, дважды посещённых сторон хотя бы
64 + 64 – 112 = 16.


Ответ

16 сторон.

Замечания

10 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
Задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .