Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/01/16.pdf Дата изменения: Fri Dec 23 19:25:00 2005 Дата индексирования: Tue Oct 2 00:11:46 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п

рого находится вдали на линии центров сферических поверхностей? А.Очков

Решения задач М1641, М1646 М1650, Ф1658 Ф1667
М1641. Есть полубесконечная полоска бумаги, разделенная на клеточки с номерами 1, 2, 3, ..., и n камней. На первой клеточке камень лежит всегда. Разрешается положить в клетку камень или убрать камень из клетки, если на предыдущей клетке лежит камень. Как далеко от начала полоски можно положить камень, действуя в соответствии с этим правилом? Докажите, например, что на клетку с номером 2n -1 камень положить можно.

Докажем, что на клетку с номером 2n -1 камень положить можно. Доказательство будет индуктивным. Индукция проводится по числу камней. Случай n = 1 очевиден на первой клетке камень лежит по условию. Пусть можно положить камень на клетку 2n -1 , используя n n камней. Покажем: как добраться до клетки 2 , используя на один камень больше. Все требуемые для этого действия разбиваются на четыре этапа. Этап 1. Без использования дополнительного камня поместим камень на клетку 2n -1 . Этап 2. Дополнительный камень поместим на клетку 2n -1 + 1. Этап 3. Теперь уберем с полоски все камни, кроме самого первого (лежащего на первой клетке) и самого последнего (лежащего на клетке 2n -1 + 1). Это можно сделать, повторяя в обратном порядке действия, совершенные на этапе 1 (разрешенные действия симметричны относительно постановки и снятия камней). Этап 4. Теперь забудем о первых 2n -1 клетках полоски. Повторим все действия этапа 1, считая начальным камень, лежащий на клетке 2n -1 + 1. При этом мы ставим и снимаем камни, освободившиеся на этапе 3. n Последним действием этапа 4 на клетку 2n -1 + 2n -1 = 2 кладется камень, что и требовалось показать. Дальше клетки с номером 2n -1 камень положить нельзя. Доказательство также использует индукцию по числу камней. И в этом случае база индукции очевидна (при n = 1 единственный камень остается на первой клетке по условию). Теперь предположим, что для всех k < n доказываемое утверждение верно, т.е. для того, чтобы положить камень k -1 на клетку с номером большим 2 , нам нужно использовать более k камней. Пусть N максимальный номер клетки, на которую можно положить камень при использовании n камней. Обозначим количество требуемых для этого действий Т, состояние полоски (положения камней, лежащих на ней) после t действий обозначим А(t), наибольший номер клетки, в которой лежит камень после t действий, обозначим N(t) (в этих обозначениях N = N(T)). Из правил, по которым кладутся и снимаются камни, следует, что N(t) 1 N(t + 1) N(t) + 1. Поэтому среди чисел N(t) обязательно встретятся все числа от 1 до N, быть может, не один раз. n-2 Разобьем полоску на две части: клетки от 1 до 2 +1

образуют левую часть, а клетки с номерами, большими n -2 + 1, образуют правую часть. 2 Если N 2 n -2 + 1 (все камни в левой части), то предположение индукции доказано и для n камней. В противном случае найдется такое t0 , что выполнено n -2 n-2 N t0 = 2 + 1 и N(t) > 2 + 1 при t > t 0 . Другими словами, начиная с момента t 0 , в правой части находится хотя бы один камень. Лемма. При t > t 0 в левой части находятся по крайней мере два камня. Доказательство. Камень, стоящий на первой клетке, находится в левой части всегда. Предположим, что в некоторый момент t в левой части не осталось никаких камней за исключением первого. Для t0 t t обозначим через B t - t такое состояние полоски, которое отличается от состояния A(t) тем, что сняты все камни из правой части (а в левой части A(t) совпадает с B t - t ). В состоянии B(0) есть ровно один камень на первой клетке. Переход от состояния B к состоянию B + 1 совершается разрешенным действием (правила обратимы если можно поставить камень, то его можно следующим действием снять, и наоборот). В состоянии B t - t0 на клетке 2 n - 2 + 1 лежит камень. В любом состоянии B(t), 0 t t t 0 , на полоске лежит не более n 1 камня. Действительно, момент t 0 был выбран так, что в любой момент после него в правой части полоски есть хотя бы один камень. При переходе от A t - t к B(t) теряются все камни, оказавшиеся в правой части. Так что в состоянии B(t) по крайней мере на один камень меньше, чем в состоянии A t - t . Таким образом, состояния B(t) n -2 описывают способ положить камень на 2 + 1 клетку, начиная от одного камня на первой клетке и используя не более n 1 камня. Это противоречит предположению индукции. Полученное противоречие доказывает лемму. Теперь забудем о всей левой части полоски, кроме клетки n -2 2 + 1. Как следует из доказанной леммы, от момента t 0 до Т в правой части полоски используется не более n 2 камней. Обозначим через C(t), t 0 t T, такое состояние полоски, которое получается из A(t) сдвигом n -2 влево на 2 и добавлением камня на первую клетку, если его там нет. Состояния от C t0 до C T описывают способ n -2 положить камень на клетку с номером N 2 , начиная от одного камня на первой клетке и используя не более n 1 камня. n -2 В силу предположения индукции N 2 2 n -2 , n -1 поэтому N 2 . Применение принципа математической индукции завершает доказательство. М.Вялый

?D

?

D

?

D

>C

>C D

?

?

D

?

D

?D

>C

М1646. У нескольких крестьян есть 128 овец. Если у

КВАНT 1999/?1

кого-то из них оказывается не менее половины всех овец, остальные сговариваются и раскулачивают его: каждый берет себе столько овец, сколько у него уже есть. Если у двоих по 64 овцы, то раскулачивают когото одного из них. Произошло 7 раскулачиваний. Докажите, что в результате все овцы собрались у одного крестьянина. На простых примерах проверяется, что ситуация 7 раскулачиваний в принципе возможна.

16