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

Проект МЦНМО
при участии
школы 57
Задача 78576
Темы:    [ Процессы и операции ]
[ Доказательство от противного ]
[ Периодичность и непериодичность ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

На лист клетчатой бумаги размером n×n клеток кладутся чёрные и белые кубики, причём каждый кубик занимает ровно одну клетку. Первый слой кубиков положили произвольно, а затем вспомнили, что каждый чёрный кубик должен граничить с чётным числом белых, а каждый белый — с нечётным числом чёрных. Кубики во второй слой положили так, чтобы для всех кубиков первого слоя выполнялось это условие. Если для всех кубиков второго слоя это условие уже выполняется, то больше кубиков не кладут, если же нет, то кладут третий слой так, чтобы чтобы для всех кубиков второго слоя выполнялось это условие, и так далее. Существует ли такое расположение кубиков первого слоя, что этот процесс никогда не кончится?


Решение

Подложим под первый слой ещё один – нулевой – совпадающий с первым. Это не повлияет на требуемую чётность, а значит, и на дальнейший процесс. Предположим, что этот процесс бесконечен. Количество возможных пар слоев конечно, следовательно, найдутся такие i и j  (i < j),  что i-й слой совпадает с j-м, а (i+1)-й – с (j+1)-м. Очевидно, каждый слой однозначно восстанавливается по двум следующим, поэтому (i–1)-й слой совпадает с (j–1)-м, (i–2)-й – с (j–2)-м и т. д. В частности, первый слой совпадает с (ji+1)-м, а нулевой – с (ji)-м. Значит, (ji+1)-й слой совпадает с (ji)-м, и класть его было не нужно. Противоречие.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 28
Год 1965
вариант
1
Класс 9
Тур 2
задача
Номер 4
олимпиада
Название Московская математическая олимпиада
год
Номер 28
Год 1965
вариант
1
Класс 10
Тур 2
задача
Номер 2

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

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