Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2008_2009/8mat_0809/spec/list_19_konechnoe.pdf Дата изменения: Sun Sep 2 20:56:28 2012 Дата индексирования: Tue Feb 5 07:36:41 2013 Кодировка: koi8-r Поисковые слова: внешние планеты

Полуинвариант. Конечное число состояний.
Метод спуска, фигурировавший в одном из прошлых листков, состояд в нахождении полуинварианта | величины, меняющейся в ходе некого процесса в сторону уменьшения, но принимающей натуральные значения. Иногда выделить такую величину бывает достаточно сложно. Порой полезным оказывается взгляд на процесс как на цепочку переходов некоторой системы из одного состояния в следующее. Если понять, что число возможных состояний конечно (а иногда и оценить это конечное число состояний), то станет проще обнаружить полуинвариант и решить задачу. Несколько олимпиадных задач такого рода и составили данный листок. 1) Петя умножает 2009 на правильную дро бь так, что бы результат оказался снова натуральным числом. С результатом он проделывает то же самое, и так далее. Какое наибольшее количество умножений он сможет сделать? 2) В каждой из нескольких стран правит одна из двух партий. Каждый год в одной из стран может поменяться власть. Причём это может произойти только если в большинстве граничащих с ней стран правит другая партия. Докажите, что смены правительств не могут продолжаться бесконечно. 3) На планете Шелезяка бывает три типа погоды: штиль, магнитная буря и метеоритный дождь. Погода каждого дня постоянна и определяется погодой предшествовавшей недели. Однажды всю неделю на Шелезяке лил метеоритный дождь. Докажите, что дождливые недели были и будут.
4) Двоечник Вася умеет приписывать к натуральному числу справа цифру 4 или 0. Ещё он умеет делить чётные числа пополам. Докажите, что из числа 4 он может получить любое натуральное число. 5) В тридесятом королевстве у каждого замка и каждой развилки сходятся три дороги. Рыцарь выехал из своего замка и по очереди поворачивает то направо, то налево. Докажите, что его маршрут зациклится. 6) На плоскости отмечено несколько точек, никакие 3 из которых не лежат на одной прямой. Люба соединила некоторые точки прямолинейными отрезками. Оказалось, что некоторые отрезки пересекаются. Лера взялась соединить точки по-другому, сохранив количество отрезков и сделав их непересекающимися. Именно, Лера, заметив два пересекающихся отрезка AB и C D, стирает их и чертит отрезки AC и B D. До бьётся ли Лера своего? 7) Коля поставил на плоскости 1543 точки так, что никакие три из них не лежат на одной прямой, и поспорил с Мишей, что тот не сможет соединить их все замкнутой несамопересекающейся ломаной. Может ли Миша гарантированно выиграть в этом споре? 8) Веня поставил на плоскости 2009 точек так, что никакие три из них не лежат на одной прямой, и соединил некоторые из них отрезками. Известно, что из любой точки выходит не более 11 отрезков. Докажите, что эти точки можно раскрасить в четыре цвета так, что бы отрезков с одноцветными концами было не более 2009. 9) Круг разбит на n секторов, в некоторых из них сидят пауки о бщим числом n + 1 штук. Каждую минуту какие-нибудь два паука, сидящие в одном секторе, разбегаются в разные стороны в соседние сектора. Докажите, что через некоторое время не менее половины секторов будет занято. 10) В парламенте у каждого депутата не более трёх врагов. Докажите, что парламент можно разделить на две палаты так, что у каждого парламентария в своей палате будет не более одного врага. 11) В столовой стоит длинная очередь из школьников. Хулиган Петя встаёт в конец очереди и даёт впереди стоящему 4 оплеухи и 4 подзатыльника. Школьник, получив m оплеух и n подзатыльников, даёт впереди стоящему m оплеух и n - 1 подзатыльник. Получив же только оплеухи в количестве больше одной, школьник даёт впереди стоящему на одну оплеуху меньше. Если же школьник получил только подзатыльники в количестве k штук, то он разворачивается и даёт сзади стоящему сдачи в виде k + 1 щелбана. Получив только одну оплеуху, школьник тоже даёт сзади стоящему 2 щелбана. Когда школьник получает щелбаны, он даёт впереди стоящему на одну оплеуху меньше, чем дал в прошлый раз, и подзатыльников на 1 меньше, чем получил щелбанов. Если же в прошлый раз он дал одну оплеуху, то вместо этого он даёт сзади стоящему на один щелбан больше, чем получил сам. Получит ли когда-нибудь Петя щелбан? 12) Станок выпускает детали двух типов. На ленте его конвейера выложены в одну линию 75 деталей. Пока конвейер движется, на станке готовится делталь того типа, которого на ленте меньше. Каждую минуту очередная деталь падает с ленты, а подготовленная кладётся в её конец. Через некоторое число минут после включения конвейера может случиться так, что расположение деталей на ленте впервые повторит начальное. Найдите: а) наименьшее такое число; б) все такие числа.

Гимназия 1543, 8 класс, 2008-2009.

Листок O-3, 26 января.

Теория и разминка.

Задачи: