Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/lexord.ps Дата изменения: Fri Oct 22 16:19:15 2004 Дата индексирования: Sat Dec 22 16:04:26 2007 Кодировка: koi8-r

Принцип минимального контрпримера (И.И.Богданов)
Принцип минимального контрпримера. Если утверждение зависит от натураль-
ного параметра n, то либо оно верно для всех n, либо есть наименьшее n, для которого
утверждение неверно.
1. Доказать что F n и F n+1 взаимно просты (здесь F n | числа Фибоначчи).
2. В памяти компьютера записан массив a 1 , a 2 , . . . , a 100000 . Обнаружив пару соседних
элементов в беспорядке, то есть a i > a i+1 , компьютер меняет их местами. Докажите, что со
временем весь массив будет идти в порядке возрастания.
3. Прожектор в пространстве освещает октант с осями, параллельными координатным.
Такие прожектора последовательно помещаются в неосвещенные точки с натуральными ко-
ординатами. Докажите, что удастся разместить лишь конечное число прожекторов.
Определение. Пусть A = (a 1 ; a 2 ; : : : ; am ) и B = (b 1 ; b 2 ; : : : ; b m ) | две числовые строки
длины m. Мы скажем что A < B если или a 1 < b 1 , или a 1 = b 1 , a 2 < b 2 , или a 1 = b 1 , a 2 = b 2 ,
a 3 < b 3 и т.д. N m | множество строк натуральных чисел длины m. Порядок, задаваемый
этим соотношением, называется лексикографическим.
4. а) Если A < B, B < C, то A < C.
б) Cтрого убывающая последовательность строк всегда конечна.
Теорема 5. В каждом подмножестве из N m есть наименьший элемент.
6. Дана последовательность из бесконечного числа нулей и конечного числа единиц.
Если найдется группа вида 01, то ее можно заменить на какую угодно группу вида 10 : : : 0.
Докажите, что можно сделать лишь конечное число таких замен.
7. В колоде несколько карт лежат рубашкой вверх, остальные | рубашками вниз. Время
от времени Петя выбирает пачку из несколько карт подряд, в которой первая и последняя
карты лежат рубашкой вниз, вынимает ее, переворачивает, и вставляет в то же место.
(Пачка может состоять и из одной карты рубашкой вниз). Докажите, что хочет того Петя
или нет, рано или поздно все карты в колоде лягут рубашкой вверх.
8. В памяти компьютера записан массив положительных чисел a 1 , a 2 , . . . , a 100000 . Обнару-
жив пару соседних элементов в беспорядке, то есть a i > a i+1 , компьютер меняет их местами
и а) умножает новый элемент a i+1 на 1000; б) умножает оба элемента на 1000. Докажите,
что со временем весь массив будет идти в порядке возрастания.
9. Множество S  N таково: для каждого числа x > 1, x 2 S есть число y = x(p
1) p 1 =p 2 S, где p | некоторый простой делитель числа x. Докажите, что и 1 лежит в этом
множестве.
10. 1000 монет разложена на 10 куч. Играют двое. Первый своим ходом выбирает 4 кучи
и делит каждую из них на правую и левую. После этого второй меняет между собой две
или несколько левых куч и соединяет правые с левыми обратно (так что снова получается
10 куч). В любой момент вместо своего хода первый может забрать любые три кучи и
прекратить игру. Докажите, что он сможет обеспечить себе не менее 950 монет.
11. Ожерелье из 2003 бусинок раскрашено в несколько цветов. Докажите, что его можно
разрезать в некотором месте так, чтобы никакая цепочка бусинок слева от разреза не была
раскрашена в точности так же, как цепочка бусинок справа от разреза.
12  . Королевство имеет вид прямоугольника m  n, разбитого на единичные клетки
дорогами; города расположены в целых точках. В городах живут гонцы. Каждый год
один из городов, который может это сделать, рассылает по гонцу во все соседние с ними
(если это невозможно ни для какого города, то процесс заканчивается). Известно, что
при некотором выборе последовательности городов, выпускающих гонцов, этот процесс
продолжается бесконечно.
а) Докажите, что, если города, выпускающие гонцов, изначально выбирать по-другому,
то процесс все равно продолжится бесконечно.
б) Найдите минимальное возможное общее число гонцов.
в) Решите ту же задачу для произвольного графа.