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

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

Условие

На некоторых клетках доски 10×10 сидит по блохе. Раз в минуту блохи одновременно прыгают, причём каждая – в соседнюю клетку (по стороне). Блоха прыгает строго в одном из четырёх направлений, параллельных сторонам доски, сохраняет направление, пока это возможно, иначе меняет его на противоположное. Пес Барбос наблюдал за блохами в течение часа и ни разу не видел, чтобы две из них сидели на одной клетке. Какое наибольшее количество блох могло прыгать по доске?


Решение

  Оценка. На одной вертикали может быть не более двух блох, прыгающих по вертикали (иначе блохи, находящиеся в клетках одного цвета, встретятся). То же верно для горизонталей. Итого на 20 горизонталях и вертикалях – не более 40 блох.
  Пример. Ясно, что блохи с клеток разных цветов не смогут встретиться. Поэтому достаточно указать только 20 "белых" блох (расположение "чёрных" блох можно получить, например, симметрией относительно средней линии).
  На левом рисунке нарисована одна "вертикальная" блоха В и все запрещённые положения "горизонтальных" блох (те, начиная с которых, "горизонтальная" блоха может оказаться с В на одной клетке). Как видим, запрещённые клетки образуют два прямоугольника, построенных на проходящих через В диагоналях. На правом рисунке размещены 10 "вертикальных" блох и все запрещённые ими положения "горизонтальных". Мы видим, что в каждой горизонтали осталась хотя бы одна незапрещённая белая клетка, куда можно посадить "горизонтальную" блоху.


Ответ

40 блох.

Замечания

11 баллов

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

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

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

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