Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 22 из 31

следующие вопросы сколько вершину графа G? сколько ребер у графа какова четность количества горизонтальных ребер у графа G?
1)
Полуинвариант (А. В. Шаповалов
Перед изучением данного раздела полезно изучить предыдущий.
Полуинвариант — это связанная с текущей позицией (расположением, ситуацией) величина, которая при каждом ходе (разрешенной в задаче операции) меняется только в одну сторону, скажем, все время уменьшается. Это гарантирует отсутствие циклов (мы не можем вернуться к уже пройденной позиции) и часто может гарантировать, что ходы закончатся. Типичный пример в большинстве игр уменьшается число возможных ходов до конца игры, что не дает игре продолжаться бесконечно.
В следующих двух задачах важно, что полуинвариант целочисленный и не может быть больше определенного числа. На шахматной доске 100 × 100 королю разрешено ходить вправо,

вверх или вправо-вверх по диагонали. Какое наибольшее число ходов он может сделать?
Типичный полуинвариант — сумма всех чисел. В клетках таблицы 99 × 99 расставлены целые числа. Если в каком-то ряду (строке или столбце) сумма отрицательна, разрешается в этом ряду поменять знаки всех чисел на противоположные. Докажите, что можно сделать в итоге лишь конечное число таких операций.
Если полуинвариант не целочисленный, то его ограниченность еще не гарантирует окончания процесса (например, убывающий положительный полуинвариант мог бы бесконечно долго принимать значения, 1/2, 1/3, 1/4, . . . , 1/n, . . .). В этих случаях прекращение ходов гарантируется конечным числом позиций. По кругу выписано несколько чисел. Если для некоторых четырех идущих подряд чисел a, b, c, d оказывается, что (a − d)(b − c) < 0, то числа b и c можно поменять местами. Докажите, что такую операцию можно проделать лишь конечное число раз.
Очень часто положение, в котором нет разрешенных операций, и является искомым.
1)
См.: Кожевников ПА. Задача Шаповалова оладье Математическое просвещение. Третья серия, вып. 4. С. 211–212; http://www.mccme.ru/free-books/matpros/
i5211212.pdf.zip

Гл. 13. Алгоритмы, конструкции, инварианты. В клетки прямоугольной таблицы вписаны числа. Разрешается одновременно менять знаку всех чисел некоторого столбца или некоторой строки. Докажите, что многократным повторением этой операции можно превратить данную таблицу в такую, у которой суммы чисел в любой строке или любом столбце неотрицательны.
В комбинаторных задачах полуинвариантом часто служит число каких-то комбинаций, например неправильных пар. На Украине все города подняли над ратушами флаги — голубые либо оранжевые. Каждый день жители узнают цвета флагов у соседей в радиусе 100 км. Один из городов, где у большинства соседей флаги другого цвета, меняет свой флаг на этот другой цвет. Докажите, что со временем смены цвета флагов прекратятся.
Некоторые конструкции создаются методом последовательного улучшения. Мы берем несовершенную конструкцию и начинаем ее преобразовывать. Полуинвариант гарантирует завершение процесса и достижение нужного эффекта в конце. В парламенте каждый депутат имеет не более трех врагов. Докажите, что парламент можно так разбить на две палаты, что у каждого депутата в его палате будет не более одного врага. На плоскости дано 100 красных и 100 синих точек, никакие три из которых не лежат на одной прямой. Докажите, что можно провести непересекающихся отрезков с концами разных цветов.
Полуинвариант может быть и нестрогим, те. не меняться при некоторых ходах. Тогда полезно найти еще один полуинвариант, который строго меняется как раз тогда, когда первый остается неизменным. На шахматной доске 100 × 100 королю разрешено ходить вправо,
вверх, вправо-вверх или вправо-вниз по диагонали. Докажите, что он может сделать лишь конечное число ходов.
Если и второй полуинвариант оказывается нестрогим, то приходится рассматривать и третий, и четвертый. В этом случае естественно рассматривать наборы значений полуинвариантов как строки, упорядоченные лексикографически (как слова в словаре сравниваются первые элементы, при равенстве — вторые. итак до первого несовпадения. В колоде часть карт лежит рубашкой вниз. Время от времени
Петя вынимает из колоды пачку из нескольких подряд идущих карт,
в которой верхняя и нижняя карты лежат рубашкой вниз (в частности,
может вынуть просто одну карту рубашкой вниз, переворачивает эту пачку как одно целое и вставляет в тоже место колоды. Докажите, что независимо оттого, как Петя выбирает пачки, в конце концов все карты лягут рубашкой вверх

Полуинвариант
335
В заключение — еще несколько задач на полуинварианты и их комбинации. В строке записано несколько чисел. Каждую секунду робот выбирает какую-либо пару рядом стоящих чисел, в которой левое число больше правого, меняет их местами и при этом умножает оба числа на 2. Докажите, что через некоторое время сделать очередную такую операцию будет невозможно. У Карлсона есть 1000 банок с вареньем. Банки необязательно одинаковые, нов каждой не больше, чем сотая часть всего варенья. На завтрак Карлсон может съесть поровну варенья из любых 100 банок.
Докажите, что Карлсон может действовать так, чтобы за некоторое количество завтраков съесть все варенье. На окружности расставлено несколько положительных чисел,
каждое из которых не больше 1. Докажите, что можно разделить окружность натри дуги так, что суммы чисел на соседних дугах будут отличаться не больше, чем на 1. (Если на дуге нет чисел, то сумма на ней считается равной нулю. За круглым столом сидят десять человек, перед каждым лежат несколько орехов. Всего орехов — сто. По общему сигналу каждый передает часть своих орехов соседу справа половину, если у дающего было четное число, или один орех плюс половину остатка — если нечетное число. Такая операция проделывается второй раз, затем третий, итак далее до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.
Зачетные задачи все, кроме любых трех пунктов.
Указания и решения. Указание. Занумеруйте вертикали слева направо, а горизонтали снизу вверх. Рассмотрите, как приходе короля меняется сумма номеров горизонтали и вертикали. Указание. Сумма ограничена суммой модулей всех элементов. Указание. При выполнении операции сумма квадратов разностей соседних по кругу чисел уменьшается, а число перестановок чисел конечно. Меняем знак только там, где сумма чисел меньше нуля. Тогда сумма чисел во всей таблице будет увеличиваться. Но число расстановок знаков конечно, значит, в какой-то момент операции закончатся. Это и означает, что суммы чисел во всех строках и столбцах положительны. Указание. Число пар соседних городов с флагами разных цветов каждый день уменьшается

Гл. 13. Алгоритмы, конструкции, инварианты. Сначала разобьем депутатов на две палаты произвольным образом. Если какой-то депутат обнаружит в своей палате хотя бы двух врагов, то переведем его в другую палату. От этого суммарное число враждующих внутри палат пар уменьшится. Указание. Проведем отрезки с разноцветными концами как попало. Пару пересекающихся отрезков с разноцветными концами можно заменить на пару непересекающихся отрезков с этими же разноцветными концами, при этом суммарная длина отрезков уменьшится. Рано или поздно этот процесс закончится, так как есть только конечное число способов соединить данные точки отрезками с разноцветными концами. Указание. Первый полуинвариант — как в задаче 1, второй — номер вертикали.
Замечание. Оба полуинварианта можно заменить одним номер горизонтали плюс удвоенный номер вертикали. Положение колоды можно закодировать словом из букв В
(карта рубашкой вверх) или Н (карта рубашкой вниз. Таких слов — конечное число, и при каждой операции получается слово, стоящее в словаре раньше по алфавиту до какого-то места ничего не изменилось,
а затем Н заменилась на В. Значит, рано или поздно операции прекратятся, а это возможно, лишь когда все карты лежат рубашкой вверх.
Разные задачи (ДА. Пермяков. В народной дружине 100 человек. Каждый день на дежурство выходят трое. Докажите, что нельзя так организовать график дежурств, чтобы любые два человека дежурили вместе ровно один раз. На каждой из планет некоторой системы сидит астроном, наблюдающий ближайшую планету. Расстояния между планетами попарно различны. Докажите, что если число планет нечетно, то какую-нибудь планету никто не наблюдает. Какое максимальное число ладей можно выставить на шахматную доску, чтобы каждая ладья била не более двух других Ладья не может бить через другую. В выпуклом угольнике проведены все диагонали. Известно, что никакие три из них не пересекаются водной точке.

а) Во скольких точках пересекутся диагонали?
б) Насколько частей разделится при этом многоугольник. Архитектор хочет расположить 7 высотных зданий так, чтобы,
гуляя по городу, можно было увидеть их шпили в любом циклическом порядке. Удастся ли это ему

Цикличность
337
Зачетные задачи все, кроме любой одной.
Решения
1. Рассмотрим одного человека. Выходя на дежурство, он каждый раз будет дежурить с двумя новыми людьми. Значит, всего он продежурит счетным числом людей, следовательно, он не сможет продежурить вместе со всеми 99 оставшимися людьми. Докажем индукцией по числу планет. Для трех планет утверждение очевидно. Если каждую планету кто-нибудь наблюдает, то каждую планету наблюдает не более одного астронома. Рассмотрим паруса- мых близких планет. Их астрономы смотрят друг на друга и больше их никто не наблюдает. Значит, мы можем применить индукционное предположение к оставшимся планетам. а) Каждая четверка вершин многоугольника однозначно задает пару пересекающихся диагоналей, и при этом каждой паре пересекающихся диагоналей однозначно соответствует четверка вершин. Значит,
всего количество точек пересечения равняется количеству четверок вершин, те. Цикличность (ПА. Кожевников
Идея зацикливания или периодичности так или иначе присутствует во многих задачах. В данном разделе представлены задачи разнообразной тематики (алгебра, геометрия, делимость, комбинаторика, объединенные этой общей идеей класс. Решите систему уравнений x
1
+
√
x
2
=x
2
+
√
x
3
=. . .=x для n = 9.
2. В выпуклом многоугольнике все углы равны. Известно, что внутри него есть точка, из которой все стороны видны под равными углами.
Докажите, что этот многоугольник правильный. В футбольном первенстве участвуют 20 команд. Докажите, что после двух туров можно выбрать 10 команд, среди которых нет двух уже сыгравших. Имеются красные и синие бусинки. Составляется ожерелье из n бусинок. Оно называется хорошим, если в нем нет двух красных бусинок, между которыми ровно k − 1 бусинок. Какое наибольшее количество красных бусинок может быть в хорошем ожерелье, если n = 42,
k = 6?

Гл. 13. Алгоритмы, конструкции, инварианты класс. Решите задачу 1 для n = 10.
6. В пересечении пяти прямых получена пятиконечная звезда. Ее внешний контур состоит из 10 отрезков. Раскрасим эти 10 отрезков поочередно в красный и синий цвета. Может ли оказаться, что любой красный отрезок длиннее любого синего. Бесконечная последовательность цифр 9, 6, 2, 4, . . . строится по правилу каждая следующая цифра равна последней цифре суммы предыдущих четырех. Встретится ли в этой последовательности четверка идущих подряд цифр 2, 0, 0, 7?
8. Решите задачу 4 для произвольного числа n бусинок и любого k 6 [n/2].
9. В некотором городе разрешены только парные обмены квартирами (если две семьи обмениваются квартирами, тов тот же день они не участвуют в других обменах. Докажите, что любой сложный обмен квартирами нескольких семей можно осуществить за два дня. (Предполагается, что и дои после обмена каждая семья живет в отдельной квартире. Пусть m — натуральное число, {f n
} — последовательность Фибоначчи а) Докажите, что последовательность остатков f при делении на m периодична.
б) Докажите, что найдется такой номер n, что f делится на Зачетные задачи Контрольные вопросы. Последовательность a
1
, a
2
, a
3
, . . . состоит из натуральных чисел,
не превосходящих 100. При этом значение каждого члена последовательности однозначно определяет значение следующего члена a Верно ли, что последовательность a
1
, a
2
, a
3
, . . . обязательно периодическая а) Верно б) неверно. Бесконечная в обе стороны последовательность . . . , a
0
, a
1
, a
2
,
a
3
, . . . состоит из натуральных чисел, не превосходящих 100. При этом значение каждого члена последовательности a однозначно определяет значение как следующего члена a n+1
, таки значение предыдущего члена a n−1
. Верно ли, что последовательность a
1
, a
2
, a
3

, . . . обязательно периодическая?
а) Верно б) неверно

Цикличность. В стране расстояния между парами городов различны. Путешественник начинает путь из города N и выбирает каждый раз маршрут в наиболее удаленный город. Возможно ли, чтобы он возвратился в N на третьем шаге?
а) Возможно б) невозможно.
Зачетные задачи Комментарии, указания и решения. Заметим, что x
1
= x
2
= . . . = x n
= 1 — решение. Пусть x
1
> 1. Из равенств последовательно получаем, что x
2
< 1, x
3
> 1, . . . , x
9
> 1, x
1
<
< 1 — противоречие. Аналогично приходим к противоречию, если x
1
< 1.
2. Пусть A
1
A
2
. . . A
n
— многоугольники точка внутри него. Из равенств ∠A
2
A
3
A
4
= . . . = ∠A
n
A
1
A
2
=
π(n − 2)
n
,
∠
A
1
OA
2
= ∠A
2
OA
3
= . . . = ∠A
n
OA
1
=
2π
n следует, что ∠OA
1
A
2
= ∠OA
2
A
3
= . . . = ∠OA
n
A
1
. Треугольники OA
1
A
2
,
OA
2
A
3
, . . . , подобны, поэтому OA
1
/OA
2
= k, OA
2
/OA
3
= k, . . . ,
OA
n
/OA
1
= k. Перемножив равенства, получим k = 1, откуда OA
1
=
= OA
2
= . . . = OA
n
3. Составим граф сыгранных игр. Из каждой вершины выходит два ребра, поэтому граф представляет собой объединение непересекающих- ся циклов. Эти циклы четной длины (цикл нечетной длины не может быть сыгран в два тура. Из каждого цикла достаточно выбрать половину команд, не игравших друг с другом. См. общий случай в задаче 8.
5. Из условия вытекает, что x i
∈ [0; 2]. Из уравнений x i
+ √x i+1
= 2
(i = 1, 2, . . . , n − 1) последовательно выводится, что при x
1 6= 1 расстояние от x до 1 увеличивается с ростом k.
6. Ответ не может. Указание. Для пяти треугольников, содержащих красную и синюю стороны, применим утверждение о том, что против большей стороны лежит больший угол. Ответ встретится.
Четыре цифры определяют следующую и предыдущую цифру в данной последовательности. Поскольку упорядоченных четверок цифр конечное число, в последовательности встретятся две одинаковые группы из четырех идущих подряд цифр. Отсюда вытекает, что последовательность периодична, причем не имеет предпериода. Это означает, что

Гл. 13. Алгоритмы, конструкции, инварианты четверка последовательно идущих цифр 9, 6, 2, 4 встретится не только вначале. Легко видеть, что появлению четверки 9, 6, 2, 4 предшествует четверка 2, 0, 0, 7.
8. Ответ d h
n
2d i
, где d = НОД (n, Соединим пары вершин, между которыми k − 1 бусин. Это граф запретов две красные вершины не могут быть соединены ребром. Пусть d = НОД (n, k). Тогда граф распадается на d циклов длины n/d. В каждом цикле может быть не более половины красных вершин, причем ровно h
n
2d красных вершин покрасить можно. Любой сложный обмен — это объединение независимых циклов.
Остается понять, что обмен по циклу можно провести за два дня.
Указание. Поворот можно представить в виде последовательного применения двух осевых симметрий. Выпишем последовательность остатков чисел Фибоначчи при делении на m: r
1
= 1, r
2
= 1, . . . Упорядоченных пар остатков конечное число, поэтому найдутся такие номера i < j, что r i
= r и r i+1
= r Остатки r и r однозначно определяют последующий и предыдущий остатки, поэтому последовательность остатков периодична с периодом l = j − Из периодичности вытекает, что r l+1
= r l+2
= 1, откуда r l
= Литература Канель-Белов А, Сапир МИ возвращается ветер, или Периодичность в математике // Квант. 1990. № Конечное и счетное (ПА. Кожевников класс. Множество натуральных чисел разбито на бесконечные арифметические прогрессии с разностями d
1
, d
2
, . . а) Докажите, что если число прогрессий конечно, то+ . . . = б) Верно ли утверждение пункта а, если число прогрессий бесконечно. Плоскость освещена прожекторами, каждый из которых освещает угол.
а) Докажите, что если число прожекторов конечно, то сумма углов не меньше 360
◦

Конечное и счетное
341
б) Верно ли утверждение пункта а, если число углов бесконечно

(счетно)?
10–11 класс. Можно ли расставить в клетки бесконечной клетчатой плоскости натуральные числа так, чтобы каждое число встречалось ровно один рази чтобы любые два числа из одной строки или одного столбца были взаимно простыми. Множество натуральных чисел разбито на две части A и B. Известно, что A не содержит трехчленной арифметической прогрессии.
Может ли случиться так, что B не содержит бесконечной арифметической прогрессии. Существует ли такая последовательность M = {a
1
, a
2

, . . .} натуральных чисел, что каждое натуральное число представляется единственным образом в виде разности двух чисел из M ?
6. Можно ли окрасить целочисленные точки плоскости в 2007 цветов так, чтобы все цвета присутствовали, на каждой прямой (содержащей не менее двух целых точек) раскраска была периодической, а раскраска плоскости не была периодической (Раскраска плоскости называется периодической, если найдется ненулевой целочисленный вектор,
при сдвиге на который раскраска переходит в себя. Существует ли такая функция f : Q × Q → Q, не являющаяся многочленом от двух переменных, что для любого a ∈ Q функции f(a, и f (x, a) являются многочленами?
Зачетные задачи Комментарии, указания и решения. а) Пусть a
1
, a
2
, . . . , a n
— первые члены прогрессий. Возьмем N =
= d
1
· d
2
· . . . · d подряд идущих натуральных чисел A + 1, A + 2, . . . ,
A + N , где A > max{a
1
, a
2
, . . . , a n
}. Легко видеть, что среди выбранных чисел в й прогрессии лежит ровно чисел (ровно одно из d подряд идущих. Отсюда N =
N
d
1
+
N
d
2
+ . . . +
N
d n
. Сокращая на N , получаем требуемое.
б) Ответ неверно.
Приведем разбиение на прогрессии, для которого+ . . . =
1 где k — фиксированное натуральное число. Для этого подберем прогрессии с разностями d i
= 2
i+k

Гл. 13. Алгоритмы, конструкции, инварианты
Опишем выбор первых членов прогрессий a i
. Пусть a
1
= 1. Если a
1
, . . . , a уже выбраны, то пусть a n+1
— наименьшее натуральное, не входящее нив одну из прогрессий. (Подумайте почему такое число найдется даже среди первых d чисел) Так как d делится на d
1
, d
2
, . . . , d n
, то прогрессия с номером n + 1 не пересекается с уже определенными (докажите. а) Перенесем параллельно углы-прожекторы так, чтобы все они имели общую вершину O. Пусть сумма углов меньше 360
◦
. Тогда найдется луч с началом вне освещенный перенесенными прожекторами.
Нетрудно доказать, что до параллельного переноса каждый прожектор освещал на этом луче ограниченную часть (отрезок или пустое множество, поэтому часть луча была неосвещенной — противоречие.
б) Ответ неверно.
Опишем покрытие углами величиной α
i
=

1 2
i+k

◦
, так что Рассмотрим круги радиусами 1, 2, . . . с центром вначале координат.
Ясно, что если каждый из этих кругов будет покрыт некоторым углом, то вся плоскость будет покрыта. Круг радиусом i покроем углом с номером i, взяв вершину угла очень далеко от начала координат.
Контрольный вопрос