Методы решения задач

Содержание

Поиск родственных задач
Причесывание задачи
Докозательство от противного

Четность
Обратный ход
Подсчет двумя способами
Соответствие
Графы
Инварианты
Правило крайнего
Принцип Дирихле
Математическая индукция
Делимость и остатки
Алгоритм Евклида
Покрытия и упаковки
Разрезания и замощения
Раскраски
Игры
Процессы и операции

Поиск родственных задач

Если задача трудна, то попытайтесь найти и решить более простую «родственную» задачу. Это часто дает ключ к решению исходной. Помогают следующие соображения:

рассмотреть частный (более простой) случай, а затем обобщить идею решения;
разбить задачу на подзадачи (например, необходимость и достаточность);
обобщить задачу (например, заменить конкретное число переменной);
свести задачу к более простой (см. тему «Причесывание задач»).

Пример 1. В угловой клетке таблицы 5 х 5 стоит плюс, а в остальных клетках стоят минусы. Разрешается в любой строке или любом столбце поменять все знаки на противо- положные. Можно ли за несколько таких операций сделать все знаки плюсами?

Решение. Возьмем квадрат поменьше, 2 х 2 (один плюс и три минуса). Можно ли сделать все знаки плюсами? Нельзя. Воспользуемся этим результатом (подумайте как): выделим в квадрате 5 х 5 квадратик 2 х 2, содержащий один плюс. Про него уже известно, что сделать все знаки плюсами нельзя. Значит, в квадрате 5 х 5 и подавно.

Пример 2. Постройте общую внешнюю касательную к двум окружностям.

Решение. Если одна из окружностей будет точкой, то задача станет легче (вспомните, как из точки провести касательную). Пусть А₁ и r₁ — центр и радиус меньшей окружности, А₂ и r₂ — центр и радиус большей окружности. Рассмотрим прямую, проходящую через А₁ и параллельную общей касательной. Эта прямая удалена от А₂ на расстояние r₂-r₁. Построим окружность с центром А₂ и радиусом r₂-r₁. Из точки А₁ проведем касательную к новой окружности. Пусть С — точка касания. На прямой A₂C лежит искомая точка касания.

Задачи

1. Легко распилить кубик 3×3×3 на 27 кубиков шестью распилами. Можно ли уменьшить число распилов, если разрешается перекладывать части перед тем как их пилить?

2. Докажите, что в выпуклом n-угольнике сумма внутренних углов равна 180°(n – 2).

3. Докажите, что n(n+1)(n+2) делится на 6 при любом целом n.

4. Решите уравнение (х² + x − 3)² + 2x² + 2x - 5 = 0.

5. (для тех, кто знаком с понятием инверсии). Постройте окружность, касательную к трем данным.

Причесывание задач (или «можно считать, что...»)

Известно, что человек некультурный ест как придется, а культурный сначала приготовит пищу. Так и некультурный математик решает задачу как придется, а культурный «приготовит» задачу, т.е. преобразует ее к удобному для решения виду.

Приготовление задачи может состоять в переформулировке условия на более удобном языке (например, на языке графов), отщеплении простых случаев, сведении общего случая к частному. Такие преобразования сопровождаются фразами «в силу симметрии», «явно не хуже», «для определенности», «не нарушая общности», «можно считать, что...».

Пример 1. Каждый ученик класса ходил хотя бы в один из двух походов. В каждом походе мальчиков было не больше 2/5. Докажите, что во всем классе мальчиков не больше 4/7.

Решение. «Лобовое» решение состоит в рассмотрении количеств мальчиков, ходивших только в первый поход, ходивших только во второй поход, ходивших в оба похода, то же для девочек, составлении и решении системы уравнений и неравенств. Этого делать не хочется, поэтому будем избавляться от лишних параметров, сводя задачу к ее частному случаю. Мы проделаем это в несколько шагов. После каждого шага упрощения становится очевидным следующий шаг. Будем увеличивать число мальчиков в классе, не изменяя числа девочек и не нарушая условия задачи.

1 шаг. «Впишем» всех девочек в число участников обоих походов. От этого доля мальчиков в классе не изменится, а в походах — уменьшится. Итак, можно считать, что все девочки ходили в оба похода.
2 шаг. Если мальчик ходил в первый поход, то освободим его от посещения второго. Доля мальчиков в походе уменьшится. Итак, можно считать, что каждый мальчик ходил только в один поход.
3 шаг. Если в одном походе было меньше мальчиков, чем в другом, то добавим в класс мальчиков. Доля мальчиков в походах останется не больше 2/5, а доля мальчиков в классе увеличится. Можно считать, что мальчиков было в походах поровну.
4 шаг. Задача стала тривиальной: в обоих походах были все девочки и ровно половина мальчиков. Обозначим число Девочек 3х, тогда мальчиков в походах было не больше 2х, а во всем классе — не больше 4х. Максимальное число мальчиков в классе 4х, а это ровно 4/7 класса.

Пример 2. Из бумажного треугольника вырезали параллелограмм. Докажите, что его площадь не превосходит половины площади треугольника.

Решение. Трудность состоит в том, что положение параллелограмма внутри треугольника произвольное. Будем преобразовывать параллелограмм, не уменьшая его пло щадь.

1 шаг. «Удлиним» параллелограмм так, чтобы одна его вершина попала на сторону треугольника.
2 шаг. «Удлиним» параллелограмм в другом направлении так, чтобы еще одна его вершина попала на контур треугольника.
3 шаг. Перекроим параллелограмм, не меняя его площадь, так, чтобы его сторона попала на сторону треугольника.
4 шаг. «Удлиним» параллелограмм так, чтобы четвертая вершина попала на контур треугольника.
5 шаг. Перекроим параллелограмм, не меняя его площадь, так, чтобы один его угол совпал с углом треугольника.
6 шаг. Теперь задача решается легко. Например, покроем параллелограмм дополняющими его треугольниками (рис. 1).

Треугольник ABC и вписанный параллелограм ADEF. Построим треугольник HEF, равный трегольнику FEC, на сторонах параллелограмма. Треугольники AGF и DBE равны (все углы равны при секущих и стороны AF=DE). Тогда S(ABC)=S(ADEF) + S₁ + S₂ = S(ADEF) + S₁ + S₄ + S₃ = 2*S(ADEF) + S₄ ≤ 2*S(ADEF). Обращается в равенстов, когда треугольник S₄ вырождается. В частности, когда ABC прямоугольной или равнобедренный.

Пример 3. В 9 ячейках записаны числа: в первой — единица, в остальных — нули. За одну операцию можно выбрать две ячейки и заменить каждое число в них полусуммой этих чисел. Какое наименьшее число можно получить в первой ячейке?

Решение. Нетрудно получить число $\frac{1}{2^{8}}$ , усредняя число в первой ячейке со всеми остальными по очереди. Труднее доказать, что меньше получить нельзя. Изменим условие задачи. Пусть после каждой операции все ненулевые числа становятся равными наименьшему из них. Эта новая операция дает результат в каждой ячейке не больше, чем исходная операция. Теперь все ясно: новая операция либо ничего не меняет, либо уничтожает один нуль и уменьшает все числа в два раза. Поскольку новая операция не позволяет получить число меньшее $\frac{1}{2^{8}}$ , то исходная операция — тем более.

Задачи

1. В кладовой лежат 300 сапог: 100 хромовых, 100 кирзовых и 100 яловых, причем левых и правых поровну — по 150.
Докажите, что из имеющихся сапог можно составить по крайней мере 50 пар.

2. На плоскости нарисовано несколько точек. Двое по очереди соединяют их отрезками. Отрезки могут выходить из одной точки, но не должны пересекаться. Кто не может сделать ход, проигрывает.
Докажите, что при любых ходах игроков победителем будет один и тот же, а кто именно — определяется лишь начальной позицией.

3. Дан выпуклый многоугольник площади 9. Его пересекают десять параллельных прямых на расстоянии 1 друг от друга.
Докажите, что сумма длин отрезков, высеченных многоугольником на этих прямых, не более десяти.

4. В N-мерном кубе покрашено более половины вершин. Ребро называется покрашенным, если покрашены обе ограничивающие его вершины.
Докажите, что покрашено не менее N ребер.

5. Дан многогранник с n вершинами и точка А внутри него. Пусть $\vec{e_{i}}$ — единичный вектор, направленный из точки А к і-й вершине многогранника.
Докажите, что $| \sum \vec{e_{i}} | < n - 2$ .

6. Алфавит некоторого языка состоит из n букв. Известно, что ни одно слово не является началом другого. a_k — число слов языка, состоящих из k букв.
Докажите, что $\sum_{k = 1}^{\infty} \frac{a^{k}}{n^{k}} \leq 1$ .
Указание. Попробуйте заменить слова максимальной длины на меньшие слова.

Доказательство от противного

Рассуждают примерно так: «Допустим, исходное утверждение неверно. Если из этого получим противоречие, то исходное утверждение верно».

Пример 1. Существует ли самое большое число?

Решение. Допустим, что существует. Тогда прибавим к этому числу единицу и получим число еще большее. Противоречие. Значит, наше предположение неверно и такого числа не существует.

Пример 2. Пять мальчиков нашли 9 грибов. Докажите, что хотя бы двое из них нашли грибов поровну.

Решение. Допустим, что мальчики нашли разное количество грибов. Расставим их по возрастанию числа найденных грибов. Первый собрал не меньше 0, второй — не меньше 1, третий — не меньше 2, четвертый — не меньше 3, пятый — не меньше 4. Всего — не меньше 10. Противоречие.

Пример 3. Докажите, что не существует треугольной пирамиды, у которой к каждому ребру примыкает тупой угол на одной из граней.

Решение. Допустим, что такая пирамида существует. Поскольку в треугольнике против тупого угла лежит самая длинная сторона, то для каждого ребра найдется более длинное ребро. Это невозможно, так как количество ребер у пирамиды конечно. Противоречие.
Замечание. Вместе с рассуждением от противного мы использовали «Правило крайнего».

Задачи

1. По кругу расставлены 100 чисел. Известно, что каждое число равно среднему арифметическому двух соседних.
Докажите, что все числа равны.

2. На плоскости отмечено несколько точек. Известно, что любые четыре из них являются вершинами выпуклого четырехугольника.
Докажите, что все отмеченные точки являются вершинами выпуклого многоугольника.

3. Докажите, что если (m-1)!+1 делится на m, то число m — простое.

4. Существует ли выпуклый многоугольник, у которого больше трех острых углов.

5. Докажите, что не существует многогранника, у которого число граней нечетно и каждая грань имеет нечетное число вершин.

Четность

Многие задачи легко решаются, если заметить, что некоторая величина имеет определенную четность. Из этого следует, что ситуации, в которых эта величина имеет другую четность, невозможны. Иногда эту величину (функцию) надо сконструировать, например, рассмотреть четность суммы или произведения, разбить объекты на пары, заметить чередование состояний, раскрасить объекты в 2 цвета. Четность в играх это возможность сохранить четность некоторой величины при своем ходе (см. темы «Инварианты», «Делимость», «Игры»).

Пример 1. Кузнечик прыгал вдоль прямой и вернулся в исходную точку (длина прыжка 1 м). Докажите, что он сделал четное число прыжков.

Решение. Поскольку кузнечик вернулся в исходную точку, количество прыжков вправо равно количеству прыжков влево, поэтому общее количество прыжков четно.

Пример 2. Существует ли замкнутая 7-звенная ломаная, которая пересекает каждое свое звено ровно 1 раз?

Решение. Допустим, что существует. Тогда пересекающиеся звенья образуют пары. Следовательно, количество звеньев должно быть четным. Противоречие.

Пример 3. У марсиан бывает произвольное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось. Докажите, что число марсиан, у которых нечетное число рук, четно.

Решение. Назовем марсиан с четным числом рук четными, а с нечетным нечетными. Поскольку руки образуют пары, то общее число рук четно. Общее число рук у четных марсиан четно, поэтому общее число рук у нечетных марсиан тоже четно. Следовательно, число нечетных марсиан четно.

Задачи

1. Можно ли разменять 25 рублей десятью купюрами достоинством 1, 3 и 5 рублей ?

2. Девять шестеренок зацеплены по кругу: первая со второй, вторая с третьей и т.д., девятая с первой. Могут ли они вращаться? А если шестеренок n?

3. 100 фишек поставлены в ряд. Разрешается менять местами любые две фишки, стоящие через одну. Можно ли таким способом переста- вить фишки в обратном порядке?

4. Даны 6 чисел: 1, 2, 3, 4, 5, 6. Разрешается к любым двум из них прибавлять 1. Можно ли все числа сделать равными?

5. Все кости домино выложили в цепочку по правилам игры. На одном конце оказалась пятерка. Что может оказаться на другом конце?

6. Может ли прямая, не проходящая через вершины 11-угольника, пересекать все его стороны?

7. На столе стоят 7 перевернутых стаканов. Разрешается одновременно переворачивать любые два стакана. Можно ли добиться того, чтобы все стаканы стояли правильно?

8. В языке дикарей хотийцев всего два звука: «ы» и «у». Два слова означают одно и то же, если одно получается из другого при помощи некоторого числа следующих операций: пропуска идущих подряд звуков «ыу» или «ууыы» и добавления в любом месте звуков «уы». Означают ли одно и то же слова «уыу» и «ыуы»?

9. На доске написаны числа 1, 2, …, 101. Разрешается стереть любые два числа и написать их разность. Повторив эту операцию 100 раз, мы получим одно число. Докажите, что это число не может быть нулем.

10. Улитка ползет по плоскости с постоянной скоростью и каждые 15 минут поворачивает на 90°. Докажите, что она может вернуться в исходную точку только через целое число часов.

11. В трех вершинах квадрата сидели кузнечики. Они стали играть в чехарду: один из кузнечиков прыгает в точку, симметричную относительно другого. Сможет ли хоть один кузнечик попасть в четвертую вершину квадрата?

Обратный ход

Если в задаче задана некоторая операция, и эта операция обратима, то можно сделать «обратный ход» от конечного результата к исходным данным. (Например, надо вынести шкаф из комнаты. Пройдет ли он через дверь? Пройдет, потому что через дверь его внесли.) Анализ с конца используется в играх при поиске выигрышных и проигрышных ситуаций.

Пример 1. На озере расцвела одна лилия. Каждый день число цветков удваивалось, и на 20-й день все озеро покрылось цветами. На который день покрылась цветами половина озера?

Решение. Начнем с конца. Пусть сегодня половина озера покрылась цветами. Через сколько дней покроется все озеро? Завтра! И это будет 20-й день.
Ответ: за 19 дней.

Пример 2. Три мальчика делили 120 фантиков. Сначала Петя дал Ване и Толе столько фантиков, сколько у них было. Затем Ваня дал Толе и Пете столько, сколько у них стало. И наконец Толя дал Пете и Ване столько, сколько у них к этому моменту имелось. В результате всем досталось поровну. Сколько фантиков было у каждого в начале?

Решение. Мы знаем, что в конце у всех оказалось по 40 фантиков, а перед этим у Пети и Вани было вдвое меньше. Значит, у Пети и Вани было по 20, a y Толи — 80. А перед этим у Пети и Толи было вдвое меньше, т.е. у Пети было 10, у Толи — 40, у Вани — 70. И наконец возьмем половину фантиков у Вани и Толи и вернем Пете. Ответ: у Пети было 65 фантиков, у Вани — 20, a y Toли — 35.

Пример 3. В квадрате ABCD на стороне АВ внутри квадрата построили равнобедренный треугольник АВЕ с углами при основании АВ равными 15°.
Докажите, что треугольник CDE правильный.

Решение. Решим обратную задачу: докажем, что если треугольник CDE₁ правильный, то у треугольника АВЕ₁ углы при основании АВ равны 15°.

Поскольку ∠ADE₁ = 30° и DE₁ = AD, то ∠E₁AD = ∠AE₁D = 75°. Значит, ∠E₁АВ = 15°. Аналогично ∠E₁BA = 15°.

Итак, мы доказали, что вершина E₁ правильного треугольника CDE₁ попадает как раз в ту точку E₁, которая дана в условии задачи. Значит, треугольник CDE правильный.

Задачи

1. Однажды царь наградил крестьянина яблоком из своего сада. Пошел крестьянин к саду и видит: весь сад огорожен тройным забором, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошел крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несешь, и еще одно». То же ему сказали второй и третий сторож. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

2. Трем братьям дали 24 бублика так, что каждый получил на три бублика меньше, чем ему лет. Меньший брат был сообразительный и предложил поменять часть бубликов: «Я, - сказал он, - оставлю половину бубликов, а другую разделю между вами поровну; после этого средний брат также оставит половину бубликов, а другую разделит поровну между мной и старшим братом. В конце старший брат поделит также». Так они и сделали. Оказалось, что все получили поровну. Сколько лет каждому брату?

3. Учитель раздавал школьникам открытки. Первому он дал одну открытку и одну десятую оставшихся. Второму он дал две открытки и одну десятую оставшихся и т.д. Девятому он дал девять открыток и одну десятую оставшихся. Оказалось, что все получили поровну и все открытки были розданы. Сколько всего было открыток?

Подсчет двумя способами

При составлении уравнений выражают некоторую величину двумя способами (например, путь или время). Иногда некоторую величину оценивают двумя способами, тогда по- лучают или неравенство, или величины разной четности. Эта идея тесно связана с идеей инварианта. Она бывает источником противоречия (см. тему «Доказательство от противного»).

Пример 1. Можно ли расставить числа в квадратной таблице 5х5 так, чтобы сумма чисел в каждой строке была положительной, а в каждом столбце отрицательной?

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

Пример 2. В классе 27 человек. Каждый мальчик дружит с четырьмя девочками, а каждая девочка с пятью мальчиками. Сколько в классе мальчиков и сколько девочек?

Пример 3. Найдите сумму геометрической прогрессии S=1+3+9+...+ 3ⁿ-1.

Решение. Заметим, что следующую сумму можно получить двумя способами: либо добавить 3ⁿ, либо умножить все слагаемые на 3, а потом прибавить 1. Получаем урав- нение: S + 3ⁿ = 3·S + 1. Отсюда S = (3ⁿ-1)/2.

Пример 4. Докажите, что медианы треугольника пе- ресекаются в одной точке.

Решение. Пусть в треугольнике АВС проведены две медианы: АА1 и СС1, их точка пересечения О. Проведем отрезки ВО и ОВ1. Воспользуемся тем, что медиана делит треугольник на два равновеликих треугольника. Действительно, у этих треугольников равны основания и общая высота. Отметим пары равновеликих треугольников: ОАС1 и ОВС1, ОВА1 и ОСА1, ОАВ1 и ОСВ1. Кроме того треугольники ОАС1 и ОСА1 равновелики, поскольку площадь каждого из них составляет половину площади исходного треугольника АВС. Значит, равновеликими являются треугольники АОС1 и СО А1, поскольку их можно получить из треугольников ОАС1 и ОСА1 выбрасыванием общей части. Отсюда следует, что равны площади четырехугольников АВОВ1 и СВОВ1. С другой стороны, медиана ВВ1 тоже делит АВС на две равновеликие части, поэтому точка О должна лежать на отрезке ВВ1.

Задачи

1. Можно ли соединить 5 городов дорогами так, чтобы каждый город был соединен с тремя другими?

2. В каждой клетке прямоугольной таблицы размером m x k клеток написано число. Сумма чисел в каждой строке и в каждом столбце равна 1. Докажите, что m = k.

3. Существует ли выпуклый 1978-угольник, все углы которого выражаются целым числом градусов,

4. Найдите сумму коэффициентов многочлена (x³ - x+1)¹⁰⁰.

5. Докажите, что не существует многогранника, у которого а) все грани шестиугольники; б) в каждой вершине сходятся 6 граней.

6. Треугольник разрезали на выпуклые четырехугольники. Докажите, что хотя бы у одного четырехугольника есть угол не меньше 120°.

7. В городе отличников от каждой площади отходит ровно 5 улиц. Докажите, что число площадей четно, а число улиц делится на 5 (улицы соединяют площади).

8. В квадрате со стороной единица поместили несколько отрезков, параллельных сторонам квадрата (квадрату принадлежит граница, а отрезкам принадлежат концы). Отрезки могут пересекать друг друга. Сумма их длин равна 18. Докажите, что среди частей, на которые квадрат разбит объединением отрезков, найдется такая, площадь которой не меньше 0.01.

Указание. Оцените двумя способами сумму периметров частей. Чем меньше площадь, тем относительно больший периметр на нее приходится.

Соответствие

Пример 2. Придворный астролог царя Гороха называет время суток хорошим, если на часах с центральной секундной стрелкой при мгновенном обходе циферблата по ходу часов минутная стрелка встречается после часовой и перед секундной. Какого времени в сутках больше: хорошего или плохого?

Решение. Основная идея: если стрелки показывают хорошее время, то их зеркальное отражение показывает плохое, и наоборот.

В полночь стрелки совпадают. Если пустить часы назад, то стрелки, будут показывать какое-то вчерашнее время, а их расположение будет зеркально симметричным расположению стрелок на обычных часах. Итак, каждому хорошему моменту сегодня соответствует плохой момент вчера. Причем интервалу хорошего времени соответствует интервал плохого. Значит, хорошего времени сегодня столько же, сколько было плохого вчера. Поэтому хорошего и плохого времени в сутках поровну.

Пример 3. В выпуклом n-угольнике никакие три диагонали не пересекаются в одной внутренней точке. Сколько точек пересечения у этих диагоналей (не вершин)?

Решение. Каждой внутренней точке пересечения диагоналей соответствует четверка вершин - концов соответствующих диагоналей. Имеется и обратное соответствие: каждой четверке вершин соответствует точка пересечения диагоналей образованного ими четырехугольника. Поэтому число точек пересечения диагоналей равно количеству четверок вершин, т.е. числу сочетаний из n по 4.

Объект может стать более естественным, если у него найдется пара. Например, вместе с иррациональностью x + y $\sqrt{D}$ рассматривают сопряженную иррациональность x - y $\sqrt{D}$ .

Пример 4. Докажите, что в числе ${(6+ \sqrt{37})}^{999}$ первые 999 цифр справа после запятой - нули. Идея решения. Добавим сопряженную иррациональность ${(6- \sqrt{37})}^{999}$ и заметим, что сумма ${(6+ \sqrt{37})}^{999} + {(6- \sqrt{37})}^{999}$ есть число целое, а член ${(6- \sqrt{37})}^{999}$ достаточно мал.

1. Докажите, что дроби $\frac{1000}{1993}$ и $\frac{993}{1993}$ имеют одинаковую длину периодов.

2. Докажите, что сумма номеров счастливых билетов делится на 13. Билет называют счастливым, если сумма первых трех цифр его номера равна сумме трех последних цифр.

3. По кругу расставлены 8 точек. Двое по очереди соединяют их отрезками. Первый отрезок проводится произвольно, а каждый следующий отрезок начинается из конца предыдущего. Проигрывает тот, кто не может провести новый отрезок (дважды проводить отрезок нельзя). Предположим, что игроки не делают ошибок. Кто из них победит: первый или второй?

4. На окружности даны 1987 точек, одна из них отмечена. Рассмотрим всевозможные выпуклые многоугольники с вершинами в этих точках. Каких многоугольников больше: тех, которые содержат отмеченную точку, или тех, которые ее не содержат?

5. Докажите, что число ${(\sqrt{3} - \sqrt{2})}^{999}$ представимо в виде $a \sqrt{3} - b \sqrt{2}$ , причем 3а²- 2b² = 1.

6. Существуют ли такие рациональные а_i; и b_і, что (a₁ + b₁√2)² + (a₂ + ₂√2)^² + ... + (a_n + b_n√2)² = (5+4√2)² ?

7. Докажите, что число (√2 - 1)ⁿ представимо в виде √(m+1) – √m, где m є N.

8. Двое бросают монетку: один бросил ее 10 раз, другой - 11. Чему равна вероятность того, что у второго монета упала орлом большее число раз, чем у первого?

Графы

вершинами графа: Точки
ребра графа: линии
Вершину четной: из нее выходит четное число ребер
Вершину нечетной: противном случае
четным Граф: у него все вершины четные
связным: между любыми вершинами существует путь, состоящий из ребер графа
ориентированным: на каждом ребре указано направление
плоским: он нарисован на плоскости и его ребра не пересекаются (во внутренних точках)

если в графе больше двух нечетных вершин, то его правильный обход (т.е. обход, при котором каждое ребро проходится ровно один раз) невозможен;
для всякого четного связного графа существует правильный обход, который можно начать с любой вершины и который обязательно кончается в той же вершине, с которой начался;
если в связном графе ровно две нечетные вершины, то существует правильный обход, причем в одной из них он начинается, а в другой - кончается;
4) в любом графе количество нечетных вершин четно.

Пример 1. В углах шахматной доски 3х3 стоят 4 коня: 2 белых (в соседних углах) и два черных. Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

Решение. Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно пройти ходом коня. Мы получим граф, содержащий «цикл» из восьми точек и одну изолированную точку (рис. 2). Перемещение коней по доске соответствует дви жению по ребрам этого цикла. Ясно, что при движении по циклу нельзя изменить порядок следования коней.

Пример 2. Выпишите в ряд цифры от 1 до 9 так, чтобы число, составленное из двух соседних цифр, делилось либо на 7, либо на 13.

Решение. Напишем цифры на листе. Соединим стрелками те цифры, которые могут следовать друг за другом (рис. 3). Теперь ясно, что первой идет 7, затем 8 и 4. Поскольку 8 уже использована, то стрелки, идущие в нее, надо убрать. После 4 идет 9, поскольку к девятке другого пути нет. Дальше идет 1 и так далее.
Ответ: 784913526.

Пример 3. В стране Радонежии некоторые города связаны между собой авиалиниями. Из столицы выходит 1985 авиалиний, из города Дальнего одна, а из остальных городов - по 20 линий. Докажите, что из столицы можно добраться до Дальнего.

Решение. Рассмотрим множество городов, до которых можно добраться из столицы. Это граф: его вершины - города, ребра - авиалинии, их соединяющие. Из каждой вершины графа выходит столько ребер, сколько всего авиалиний выходит из соответствующего города. Граф содержит нечетную вершину столицу. Поскольку число нечетных вершин в графе четно, в нем есть еще одна нечетная вершина. Этой вершиной может быть только город Дальний.

Задачи

1. Расположите на плоскости 6 точек и соедините их непересекающимися линиями так, чтобы из каждой точки выходили четыре линии.

2. В трех вершинах правильного пятиугольника расположили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами?

3. В марсианском метро 100 станций. От любой станции до любой другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая станция найдется.

4. Докажите, что в плоском графе найдется вершина, из которой выходит не более 5 ребер. Следствия: а) Вершины плоского графа можно раскрасить в 6 цветов так, чтобы вершины, соединенные ребром, имели разный цвет. 6) Конечная плоская карта допускает раскраску в 6 цветов такую, что соседние страны будут окрашены в разные цвета.

5. Клетчатая плоскость раскрашена десятью красками так, что соседние (т.е. имеющие общую сторону) клетки покрашены в разные цвета, причем все десять красок использованы. Каково минимально возможное число пар соседних красок? (Две краски называются соседними, если ими покрашены какие-то две соседние клетки.)

6. В тридевятом царстве каждые два города соединены дорогой с односторонним движением. Докажите, что существует город, из которого в любой другой можно проехать не более чем по двум дорогам.

7. В городе на каждом перекрестке сходится четное число улиц. Известно, что с любой улицы города можно проехать на любую другую. Докажите, что все улицы города можно объехать, побывав на каждой по одному разу.

8. Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятерок подряд стоящих цифр встречаются все 32 возможные комбинации. Найдите пять последних цифр последовательности.

9. Дан правильный 45-и угольник. Можно ли так расставить в его вершинах цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой занумерованы этими цифрами. Указание. Рассмотреть полный граф, вершины которого суть цифры от 0 до 9. Задача сводится к его обходу.

10. Докажите, что можно расположить по кругу символы 0 и 1 так, чтобы любой возможный набор из п символов, идущих подряд, встретился. Указание. Рассмотреть граф, вершины которого суть слова длины п - 1. Две вершины и и и соединяются стрелкой, если существует слово длины п, у которого и является началом, a v — концом.

Инварианты

Инвариант величина, которая не изменяется в результате некоторых операций (например, разрезание и перестановка частей фигур не меняет суммарной площади). Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться четность или раскраска. В задачах про сумму цифр используются остатки от деления на 3 или 9. Полуинвариант величина, изменяющаяся только в одну сторону (т.е. которая может только увеличиваться или только уменьшаться). Понятие полуинварианта часто используется при доказательствах остановки процессов.

Пример 1. На чудо-яблоне растут бананы и ананасы. За один раз разрешается сорвать с нее два плода. Если сорвать два банана или два ананаса, то вырастет еще один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если известно, сколько бананов и ананасов росло вначале?

Решение. Четность числа бананов не меняется, поэтому, если число бананов было четным, то оставшийся плод - ананас, если число бананов было нечетным, то - банан.

Пример 2. В одной клетке квадратной таблицы 4х4 стоит знак минус, а в остальных стоят плюсы. Разрешается Одновременно менять знак во всех клетках, расположенных в одной строке или в одном столбце. Докажите, что, сколь- ко бы мы ни проводили таких перемен знака, нам не удастся получить таблицу из одних плюсов.

Решение. Заменим знак «+» на число 1 и знак «-» на число -1. Заметим, что произведение всех чисел в таблице не меняется при смене знака у всех чисел столбца или строки, так как одновременно меняется знак у четырех чисел. В начальном положении это произведение равно -1, а в таблице из одних плюсов +1, чем и доказана невозможность перехода.

Пример 3. На прямой стоят две фишки: слева красная, справа синяя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд (между фишками или с краю) и удаление пары соседних одноцветных фишек (между которыми нет других фишек). Можно ли с помощью таких операций оставить на прямой ровно две фишки: слева синюю, а справа красную?

Решение. Рассмотрим число разноцветных пар (не только соседних), где левая фишка красная, и заметим, что четность этого показателя не меняется. Но в исходной ситуации наш показатель равен 1, а в желаемой ситуации - нулю. Поэтому перейти к желаемой ситуации невозможно.

Пример 4. На острове Серобуромалин живут хамелеоны: 13 серых, 15 бурых и 17 малиновых. Если 2 хамелеона разных цветов встречаются, то они оба меняют свой цвет на третий. Может ли случиться, что в некоторый момент все хамелеоны на острове станут одного цвета?

Указание. Рассмотрите остатки от деления чисел Б бурых, С серых и М малиновых хамелеонов на 3 и проверьте, что попарные разности у этих остатков не меняются.

Пример 5. Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив остальные на месте.

Идея решения. Рассмотрим «пустое поле» как отдельную фишку. Мы можем только менять «пустую фишку» с соседними. Поскольку пустая фишка должна попасть на исходное поле, число наших операций должно быть четным. Поэтому мы можем получить конфигурации, отличающиеся от начальной только четным числом перестановок.

Пример 6. На 44 деревьях, расположенных по кругу, сидели по веселому чижу. Время от времени какие-то два чижа перелетают на соседнее дерево один по часовой стрелке, а другой против. Могут ли все чижи собраться на одном дереве?

Решение. Пронумеруем деревья по кругу с 1-го по 44-е. Сумма номеров деревьев, на которых сидят чижи либо не меняется, либо уменьшается на 44, либо увеличивается на 44. Тем самым, остаток от деления этой суммы номеров на 44 не меняется. Изначально этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не смогут собраться на одном дереве.

Задачи

1. Можно ли разрезать выпуклый 17-угольник на 14 треугольников?

2. Можно ли круг разрезать на несколько частей и сложить квадрат? (Разрезы это прямые и дуги окружностей.)

3. Болельщик Вася нарисовал расположения игроков на футбольном поле к началу первого и второго таймов. Оказалось, что некоторые игроки поменялись местами, а остальные остались на своих местах. При этом расстояние между любыми двумя игроками не увеличилось. Докажите, что все эти расстояния не изменились.

4. Докажите, что сумма квадратов расстояний от вершин правильного п-угольника до любой прямой, проходящей через его центр есть величина постоянная.

5 (Сизифов труд). На горе 1001 ступенька, на некоторых лежат камни, по одному на ступеньке. Сизиф берет любой камень и переносит его вверх на ближайшую свободную ступеньку (т.е. если ближайшая ступенька свободна, то на нее, а если она занята, то на несколько ступенек вверх до первой свободной). После этого Аид скатывает на одну ступеньку вниз один из камней, у которых предыдущая сту пенька свободна. Камней 500 и первоначально они лежали на нижних 500 ступеньках. Сизиф и Аид действуют по очереди начинает Сизиф. Цель Сизифа положить камень на верхнюю ступеньку. Может ли Аид ему помешать?

6. Столица страны соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединен авиалиниями ровно с 10 городами (если А соединен с В, то В соединен с А). Известно, что из любого города можно попасть в любой другой (может быть, с пересадками). Докажите, что можно закрыть половину авиалиний, идущих из столицы, так что возможность попасть из любого города в любой другой сохранится.

7. Во время перемирия за круглом столом разместились рыцари из двух враждующих станов. Оказалось, что число рыцарей, справа от которых сидит враг, равно числу рыцарей, справа от которых сидит друг. Докажите, что число рыцарей делится на четыре.

Правило крайнего

Особые, крайние объекты часто служат «краеугольным камнем» решения. Так, например, рассматривают наибольшее число, ближайшую точку, угловую точку, вырожден- ную окружность, предельный случай. Поэтому полезно сра- зу рассматривать особые, крайние объекты. В задачах на правило крайнего работает метод минимального контрпримера: допустим, утверждение задачи неверно. Тогда существует минимальный в некотором смысле контрпример. И если окажется, что его можно еще уменьшить, то получится искомое противоречие.

Пример 1. Плоскость разрезана вдоль N прямых общего положения. Докажите, что к каждой прямой примыкает треугольник.

Решение. Выберем прямую и рассмотрим точки пересечения других прямых между собой. Среди этих точек пере- сечения выберем ближайшую к нашей прямой. Две прямые, проходящие через эту точку, пересекают исходную прямую и образуют с ней треугольник. Этот треугольник не могут пересекать другие прямые (докажите).

Пример 2. Докажите, что у многогранника есть две грани с одинаковым числом сторон.

Решение. Рассмотрим грань с наибольшим числом сторон. Обозначим эту грань G, число ее сторон n. К каждой стороне G примыкает грань многогранника, всего примыкающих граней п. Число сторон в каждой грани заключено между 3 и п - 1, всего n - 3 возможности. Поскольку число возможностей меньше числа примыкающих граней, то по принципу Дирихле (см. тему «Принцип Дирихле») одна из возможностей повторится. Таким образом, среди граней, примыкающих к грани G, найдутся две грани с одинаковым числом сторон.

Пример 3. На шахматной доске расставлены числа, каждое из которых равно среднему арифметическому своих соседей. Докажите, что все числа равны.

Решение. Рассмотрим наибольшее из чисел. Оно равно своим соседям. Поскольку любые два числа соединяются цепочкой соседних чисел, все числа равны.

Пример 4. Из точки внутри выпуклого многоугольника опускают перпендикуляры на его стороны или их продолжения. Докажите, что хотя бы один перпендикуляр попадет на сторону. Указание. Рассмотрите ближайшую точку границы.

Пример 5. Докажите, что число 1+1/2+1/3+...+1/n не является целым.

Указание. Рассмотрите максимальную степень двойки, входящую в знаменатель членов суммы.

Правилу крайнего родственно рассмотрение ситуации на бесконечности (в асимптотике).

Пример 6. На плоскости расположено 10 точек и 10 прямых. Докажите, что можно найти такую точку, расстояние от которой до любой прямой будет меньше, чем до любой из точек.

Идея решения. Выберем направление, не перпендику- лярное ни одной из прямых. Будем двигать по этому направлению точку с единичной скоростью. Скорость удаления этой точки относительно любой отмеченной точки стремится к единице, а скорость ее удаления относительно любой отмеченной прямой меньше единицы.

Пример 7. Ограниченная фигура на плоскости имеет площадь S > 1. Докажите, что ее можно сдвинуть на целочисленный вектор так, чтобы исходная фигура и ее образ пересекались.

Решение. Пусть расстояние между любыми двумя точками фигуры не превосходит d. Рассмотрим сдвиги нашей фигуры на всевозможные целочисленные векторы. Нарисуем на плоскости два квадрата с общим центром и сторонами, параллельными координатным осям один со стороной l, а другой - со стороной l + 2d (значение l мы определим позже). Большой квадрат «окаймляет» малый, ширина «каймы» равна d. Поэтому любой из рассматриваемых образов фигуры, пересекающий малый квадрат, целиком лежит внутри большого. Левый нижний угол маленького квадрата расположим так, чтобы он принадлежал рассматриваемой фигуре. Оценим площадь фигур, пересекающих малый квадрат. Таких фигур не меньше 12, т.к. сдвиги на векторы вида (m,n) (0 ≤ m < l, 0 ≤ n < l) переводят левый нижний угол квадрата в точку внутри квадрата, а таких сдвигов всего имеется ([l]+1)^2 > l^2. Если предположить, что образы фигуры не пересекаются, то их суммарная площадь должна не превосходить площади большого квадрата. Получаем неравенство

Sl^2 ≤ (1 + 2d)^2 или (S − 1)l^2 – 4dl — 4^2 ≤ 0.

В левой части последнего неравенства стоит квадратный трехчлен относительно l со старшим коэффициентом большим нуля. При достаточно больших l он принимает положительные значения (его график парабола с ветвями вверх). Значит, можно подобрать такое l, при котором последнее неравенство не будет выполняться. Поэтому предположение, что образы нашей фигуры не пересекаются приводит к противоречию. Так как два образа рассматриваемой фигуры при сдвигах на целочисленные векторы пересекаются, то при сдвиге исходной фигуры на разность этих векторов получим фигуру, пересекающую исходную.

Задачи

1. Путешественник отправился из своего родного города А в самый удаленный от него город страны В; затем из В — в самый удаленный от него город С и т.д. Докажите, что если С не совпадает с А, то путешественник никогда не вернется домой. (Расстояния между городами страны различны).

2. Назовем автобусный билет (с шестизначным номером) счастливым, если сумма цифр его номера делится на 7. Могут ли два билета подряд быть счастливыми?

3. В одну из голов 100-голового дракона пришла мысль расположить свои головы так, чтобы каждая находилась между двумя другими. Сможет ли он это сделать? (Головы - это точки на плоскости.)

4. На столе лежат одинаковые монеты без наложений. Докажите, что найдется монета, которая касается не более трех других.

5. На столе лежат монеты без наложений. Докажите, что найдется монета, которая касается не более пяти других.

6. На столе лежат монеты без наложений. Докажите, что одну из них можно передвинуть по столу к его краю, не сдвинув других монет.

7. На полях шахматной доски расставлены целые числа, причем никакое число не встречается дважды. Докажите, что есть пара соседних (имеющих общую сторону) клеток, числа в которых отличаются не меньше, чем на 5.

8. На окружности стоят 30 чисел, каждое из которых равно модулю разности двух следующих за ним по часовой стрелке. Сумма всех чисел равна 1. Что это за числа и как они стоят на окружности?

9. На прямой расположена колония из конечного числа бактерий. В моменты 1, 2, 3, … некоторые из бактерий могут погибать; новых бактерий не возникает ни в один момент. Погибают те и только те бактерии, от которых ни слева на расстоянии 1, ни справа на расстоянии √2 нет бактерий. Существует ли колония бактерий, которая будет жить вечно?

10. В течение дня в библиотеке побывало 100 читателей. Оказалось, что в тот день из любых трех читателей двое в библиотеке встретились. Докажите, что сотрудник библиотеки мог сделать важное сообщение в такие два момента времени, чтобы все 100 человек его услышали. (Каждый читатель побывал в библиотеке только один раз.)

11. На плоскости отмечено несколько прямых. Известно, что через точку пересечения любых двух отмеченных прямых, проходит по крайней мере еще одна. Докажите, что все отмеченные прямые проходят через одну точку.

12. Дан параллелограмм с вершинами в целых точках такой, что внутри или на границе больше целых точек нет. Докажите, что его площадь равна единице.

13 (лемма Минковского). Докажите, что центрально-симметричная относительно начала координат выпуклая фигура площади больше 4 содержит еще хотя бы одну целую точку.

Указание. Произведите гомотетию с коэффициентом 1/2 и воспользуйтесь результатом примера 7. В следующих задачах применяется метод малых шевелений, который родствен правилу крайнего.

14. Прямая имеет с замкнутой ломаной 1995 общих точек. Докажите, что некоторая прямая, не параллельная ни одному звену ломаной, имеет с ней более 1995 общих точек.

15. На окружности проведено 100 хорд, из которых любые две пере- секаются. Всегда ли можно провести еще одну хорду так, чтобы она пересекала их все?

Принцип Дирихле

В простейшем виде его выражают так: «Если десять кроликов сидят в девяти ящиках, то в некотором ящике сидят не меньше двух кроликов». Общая формулировка: «Если n кроликов сидят в k ящиках, то найдется ящик, в котором сидят не меньше чем n/k кроликов, и найдется ящик, в котором сидят не больше чем n/k кроликов». Пусть вас не смущает дробное число кроликов если получится, что в ящике не меньше 7/3 кроликов, значит, их не меньше трех. Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.

Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше чем n/k * k = n. Противоречие. Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, ни ящики. Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы А можно назвать кроликами, а элементы В ящиками.

Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг» (а если кто-то съел больше среднего, то кто-то съел меньше среднего). Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава роль кроликов, сидящих в ящиках.

Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.

Решение. Всего в году бывает 366 дней. Назовем дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше 400/366 кроликов, т.е. больше одного. Следовательно, не меньше двух.

Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.

Пример 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6х6 из чисел +1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от -6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит составить такой квадрат невозможно.

Пример 3. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.

Решение. Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмем эту точку вместе с противоположной к ней.

Пример 4. На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на всех контрольных?

Решение. Рассмотрим множество наборов из трех оце- нок за соответствующие контрольные. Количество таких наборов равно 43 или 64 (4 возможности за каждую из трех контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.

Задачи

1. В классе 30 учеников. Во время контрольной работы Петя сделал 13 ошибок, а остальные меньше. Докажите, что найдутся три ученика, сделавшие одинаковое число ошибок.

2. На Земле больше 4 миллиардов человек, которые моложе 100 лет. Докажите, что на Земле есть два человека, родившихся в одну и ту же секунду.

3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15°.

4. В ящике лежат носки: 10 черных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка а) одного цвета; б) разных цветов; в) черного цвета?

5. На карьере добыли 36 камней. Их веса соответственно 490 кг, 495 кг, 500 кг, …, 665 кг (арифметическая прогрессия). Можно ли увезти эти камни на семи трехтонных грузовиках?

6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной из них был угадан хоть один номер,

7. Докажите, что среди любых пяти человек есть двое с одинаковым числом знакомых среди этих пяти человек. (Возможно, эти двое ни с кем не знакомы.)

8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.

9. Квадратная таблица (2n + 1)x(2n + 1) заполнена числами от 1 до 2n +1 так, что в каждой строке и в каждом столбце представлены все эти числа. Докажите, что если это расположение симметрично относительно главной диагонали, то на главной диагонали тоже представлены все эти числа.

10. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

11. Комиссия из 60 человек провела 40 заседаний, причем на каждом присутствовало ровно 10 членов комиссии. Докажите, что какие-то два члена комиссии встречались на ее заседаниях по крайней мере Дважды.

12. На столе лежат 50 правильно идущих часов. Докажите, что в некоторый момент сумма расстояний от центра стола до концов минутных стрелок будет больше, чем сумма расстояний от центра стола до центров часов.

13. Каждая из 9 прямых разбивает квадрат на два четырехугольника, площади которых относятся как 2:3. Докажите, что по крайней мере три из этих прямых проходят через одну точку.

Математическая индукция

Метод доказательства утверждений типа: «Для каждого натурального п верно, что… ». Такое утверждение можно рассматривать как цепочку утверждений: «Для n = 1 верно, что «Для n = 2 верно, что. верно, что...» и т.д. Первое утверждение цепочки называется базой (или основанием) индукции. Его обычно легко проверить. Затем доказывается индуктивный переход (или шаг индукции): «Если верно утверждение с номером п, то верно утверждение с номером (n+1)». Индуктивный переход также можно рассматривать как цепочку переходов: «Если верно утверждение 1, то верно утверждение 2», «Если верно утверждение 2, то верно утверждение 3» и т.д. Если верна база индукции и верен индуктивный переход, то все утверждения верны (это принцип математической индукции). Иногда для доказательства очередного утверждения це- почки надо опираться на все предыдущие утверждения. Тогда индуктивный переход звучит так: «Если верны все утверждения с номерами от 1 до п, то верно утверждение с номером (n + 1)». Иногда удобен индуктивный спуск - если утверждение с номером п (n > 1) можно свести к одному или нескольким утверждениям с меньшими номерами и первое утверждение верно, то все утверждения верны.

Пример 1. Докажите, что число состоящее из 243 единиц, делится на 243.

Решение. Заметим, что 243 = 3⁵. Попробуем доказать более общее утверждение, что число, составленное из 3ⁿ единиц, делится на 3ⁿ. Оказывается, это проще. Для n = 1 утверждение верно (111 делится на 3). Заметим, что 111111111 = 111 * 1001001, и вообще число из 3ⁿ единиц разлагается на множители: $\underset{\underset{3n+1}{⏟}}{1...1} = \underset{\underset{3n}{⏟}}{1...1} * 10...010...01$ причем, второй множитель делится на 3 (по признаку делимости на 3). Итак, в последовательности чисел 111, 111111111, «3^n единиц» каждое следующее равно предыдущему, умноженному на число, кратное трем. Поэтому, если 1...1 3^(n-1) делится на 3^(n-1), то 1...1 (3^n) делится на 3". Теперь индукция очевидна.

Замечание. Мы специально не произносили слов «база индукции» и «индуктивный переход», чтобы не отвлекать внимание от более трудных моментов.

Пример 2. На плоскости провели несколько прямых. Докажите, что части на которые рассечена плоскость, можно раскрасить в два цвета так, чтобы соседние части (у которых есть общий отрезок) были покрашены в разные цвета.

Решение. Покажем, как из раскраски разбиения плоскости и прямыми получить раскраску разбиения (n+1)-й прямой. Проведем новую прямую. Она разбивает плоскость на две части. В одной части оставим раскраску без изменений, а в другой сменим на противоположную. Легко видеть, что вдоль новой прямой граничат области противоположных цветов. В других местах это следует из того, что старое разбиение удовлетворяло условиям задачи.

Пример 3. Докажите, что если x + 1/x целое, то x^n + 1/x^n тоже целое.

Решение. Пусть Тn = x^n + 1/x^n. Заметим, что Т0 = 2 и Т1 = x + 1/х целые. Рассмотрим произведение (x+1/x)(x+1/x) = x^2 + 2 + 1/x^2 = T2 + 2. Отсюда Т2 = T1 - 2 — целое. Обобщим идею и рассмотрим произведение TnT1 = (x^n+1/x^n)(x+1/x)=(x^n+1 + 1/x^(n+1)) + (x^n-1 + 1/x^n-1) = Tn+1 + Tn-1. Отсюда получим, что Тn+1 = ТnТ1-Тn-1. Поэтому, если Тn и Тn-1 целые числа, то Tn+1 тоже целое. Теперь по индукции получим, что Тn целое при всех n.

Задачи

1. Докажите, что любое число рублей большее семи можно разменять трешками и пятерками.

2. Несколько прямых делят плоскость на части. Каждая прямая «заштрихована» с одной стороны. Докажите, что все границы одной из частей «заштрихованы» изнутри.

3. Из квадрата 128х128 вырезали одну клетку. Докажите, что эту фигуру можно замостить уголками из трех клеток.

4. Докажите, что простых чисел бесконечно много.

5. Докажите неравенство 2^k > k.

6. Докажите неравенство Коши: х1+...+ xn > sqrt(x1•·Xn)

Идея решения. Используется более сложная схема индукции: сначала по степеням двойки, потом от степени двойки к меньшему числу переменных.

7. Пятеро разбойников добыли мешок золотого песка. Они хотят поделить его так, чтобы каждый был уверен, что он получил не меньше одной пятой золота. Никаких способов измерения у них нет, однако каждый умеет оценивать на глаз величину кучи песка. Мнения разбойников о величине куч могут расходиться. Как им поделить добычу?

Указание. Если бы разбойников было двое, то один поделил бы песок на две равные, по его мнению, кучи, а второй выбрал бы себе кучу.
Первый путь. Найти «самого скромного» разбойника и отдать ему его долю.
Второй путь. Пусть n разбойников уже разделили добычу, и пришел еще один....

8. В городе N домов. Какое наибольшее число заборов можно построить в этом городе, если

заборы не пересекаются,
каждый забор огораживает хотя бы один дом,
никакие два забора не огораживают одну и ту же совокупность домов?

Делимость и остатки

Допустим, нас интересуют остатки от деления чисел на 10 (последняя цифра). Как найти последнюю цифру произведения двух чисел? Достаточно перемножить последние цифры сомножителей и взять последнюю цифру результата. Аналогичная теорема верна для любого делителя: остаток произведения или суммы двух чисел определяется остатками этих чисел это создает «арифметику остатков». Остаток может выступать в роли инварианта (например, остаток от деления на 9 в задачах про сумму цифр).

Пример 1. Докажите, что существует бесконечно много чисел, которые не представимы в виде суммы двух квадратов.

Решение. Достаточно доказать, что числа, имеющие при делении на 4 остаток 3, не представимы в виде суммы двух квадратов. Из равенств (2k)^2 = 4k^2, (2k + 1)^2= 4k^2 + 4k + 1 следует, что квадрат целого числа при делении на 4 дает остаток 0 или 1. Поэтому сумма двух квадратов не может иметь остаток 3.

Пример 2. Докажите, что число, в десятичной записи которого участвуют три единицы и несколько нулей, не может быть квадратом.

Решение. Если такое число существует, то оно делится на 3, но не делится на 9 (по признакам делимости на 3 и 9). Но если число делится на 3 и является полным квадратом, то оно делится на 9. Противоречие.

Задачи

1. Какие числа можно представить в виде разности двух квадратов целых чисел?

2. Если р простое число, большее трех, то р^2 - 1 делится на 24.

3. При каких n число 2^n - 1 делится на 7?

4. Известно, что сумма нескольких натуральных чисел делится на 6. Докажите, что сумма кубов этих чисел тоже делится на 6.

5. Если в целочисленной арифметической прогрессии встретился квадрат целого числа, то квадратов в ней бесконечно много. Докажите.

Алгоритм Евклида

Алгоритм Евклида позволяет находить наибольший общий делитель чисел, решать линейные уравнения в целых числах. Алгоритм основан на следующем факте: «Если при делении числа а на в получается остаток r, mo НОД(a, b) = НОД(b, r)».

Пусть даны два натуральных числа n1 и n2. Поделим n1 на n2 с остатком. Обозначим остаток n3. Поделим n2 на n3 с остатком и т.д. (каждый раз мы делим предыдущий делитель на полученный остаток) до тех пор, пока остаток не будет равен нулю. Последний ненулевой остаток и будет равен наибольшему общему делителю исходных чисел n1 и n2. Отметим, что этот алгоритм может быть применен также для нахождения наибольшего общего делителя многочленов и других объектов более общей природы.

Пример 1. Разделить угол 19° на 19 равных частей.

Решение. Отложим 19 раз угол 19° по кругу. В результате сместимся на 1°, поскольку 19 · 19° = 361° = 360°+1°. Таким образом мы получили «остаточный» угол в 1°, с помощью которого осуществим деление.

Пример 2. Докажите, что числа 2^m - 1 и 2^n - 1 взаимно простые тогда и только тогда, когда числа п и m взаимно простые.

Решение. Пусть n>m. Обозначим F(n,m) = НОД(2^n - 1, 2^m - 1). Тогда F(n,m) = НОД(2^n - 1- (2^m - 1), 2^m - 1) = НОД((2^(n-m)-1)*2^m, 2^m-1) = НОД(2^(n-m)-1, 2^m-1) = F(n-m, m). Таким образом, пару чисел (n, m) можно заменить на пару (n-m, m). С помощью алгоритма Евклида мы придем к паре (d,0), где d = НОД(m, n). Итак, НОД(2^n - 1, 2^m - 1) = НОД(2^d - 1, 2^0 – 1) = 2^d - 1. В нашем случае d = 1, 2^d - 1 = 1, поэтому числа 2^n - 1 и 2^m - 1 взаимно просты.

Задачи

1. Решите уравнение в натуральных числах 7х - 11y = 1.

2. Даны углы 36° и 25°. Постройте угол 1°.

3. Числа m и n - взаимно просты. Докажите, что уравнение mx + ny = 1 имеет решение в целых числах.

4. Один прибор делает пометки на длинной ленте через каждые m см, другой через каждые n см (m и n взаимно простые). Верно ли, что какая-то синяя пометка окажется на расстоянии не большем 1 см от какой-то красной?

5. Разрешается сдвигать фишку вдоль числовой прямой на ±1 и на ±√2. Докажите, что из любого начального положения ее можно придвинуть к началу координат ближе чем на 0.0001.

6. «Крокодилом» называется фигура, ход которой заключается прыжке на клетку, в которую можно попасть сдвигом на одну клетку по вертикали или горизонтали, а затем на N клеток в перпендикулярном направлении (при N = 2 «крокодил» это шахматный конь ). При каких и «крокодил» может пройти с любой клетки бесконечной шахматной доски на любую другую?

Покрытия и упаковки

Если объединение нескольких фигур содержит данную фигуру Ф, то говорят, что эти фигуры образуют покрытие фигуры Ф. При этом покрывающие фигуры могут пересекаться. Упаковка-это размещение нескольких непересекающихся фигур внутри данной фигуры.

Пример 1. Можно ли покрыть правильный треугольник двумя правильными треугольниками меньшего размеpa?

Решение. Каждый из меньших треугольников может покрыть только одну вершину большего, но вершин три, а треугольников только два.

Пример 2. На поле 10 х 10 для игры в «морской бой» нужно расставить один корабль 1 х 4, два корабля 1 х 3, три корабля 1 х 2 и четыре корабля 1 х 1. Корабли не должны иметь общих точек (даже вершин), но могут прилегать к границам квадрата. Докажите, что если расставлять их в указанном порядке (начиная с больших), то каждому кораблю всегда найдется место (как бы их ни ставили на любое свободное место).

Решение. Корабль 1х4 поставить можно. Докажем, что очередной корабль 1 х 3 поместится. Для этого нарисуем 8 вспомогательных кораблей 1 х 3, параллельных друг другу, с интервалом две клетки. Поставленные корабли могут задеть (пересечь или коснуться) не больше двух отмеченных, поэтому останется незадетый отмеченный корабль, на место которого можно поставить очередной корабль 1 х 3.

Пусть уже расставлены корабли 1х4, два 1х3 и меньше трех 1х2. Докажем, что еще один корабль 1х2 поместится. Для этого отметим 12 вспомогательных кораблей 1х2 параллельных друг другу с интервалом две клетки. Каждый поставленный корабль может задеть не больше двух отмеченных, поэтому останется незадетый отмеченный корабль. Аналогично поместится очередной одноклеточный корабль. Отметим 16 вспомогательных кораблей 1х1 с интервалом две клетки. Поставленные корабли задевают не больше 15 отмеченных.

Пример 3. Внутри круглого блина радиуса R запекли монету радиуса г. Каким наименьшим числом прямых разрезов можно наверняка задеть монету?

Решение. Если разрезы проводить параллельно, то монету можно задеть за R/2г разрезов, если число R/2г - целое, и за [R /2г] + 1 разрезов, если R/2r - нецелое. Трудность состоит в доказательстве того, что меньшим числом разрезов обойтись нельзя.

Рассмотрим множество возможных положений центра монеты. Каждому прямолинейному разрезу соответствует полоса ширины 2r, отвечающая множеству возможных центров монеты, задетой этим разрезом. Таким образом, задача переформулируется следующим образом: найти минимальное число полос ширины 2r, покрывающих круг радиуса R. Воспользуемся следующим замечательным фактом: если сферу пересечь двумя параллельными плоскостями, то площадь сферы между ними зависит только от расстояния между плоскостями и не зависит от их положения. Опишем вокруг блина сферу. Через края каждой полосы проведем две перпендикулярные к ней плоскости. Они высекут на сфере кольца одинаковой площади. Осталось покрыть сферу наименьшим числом колец известной площади.

Задачи

1. Квадратный каток надо осветить четырьмя прожекторами, висящими на одной высоте. Каков наименьший радиус освещенных кругов?

2. На плоскости горит лампочка. Можно ли расположить три круга так, чтобы освещенная область была ограниченной?

3. Коридор полностью покрыт несколькими ковровыми дорожками. Докажите, что можно убрать несколько дорожек так, чтобы а) коридор был полностью покрыт, а общая длина оставшихся дорожек была не больше удвоенной длины коридора; б) оставшиеся дорожки не перекрывались и их суммарная длина была не меньше половины длины коридора.

4. Пол в прямоугольной комнате 6 х 3 кв.м покрыт квадратными коврами разных размеров, края которых параллельны стенам. Докажите, что можно убрать несколько ковров так, чтобы оставшиеся ковры покрывали более 2 кв.м.

5. На столе лежат 15 журналов, полностью покрывая его. Докажите, что можно убрать 7 журналов так, чтобы оставшиеся покрывали не менее 8/15 площади стола.

6. Круглый стол покрыт круглыми салфетками разных размеров. Докажите, что можно выбрать несколько салфеток, которые не пересекаются и закрывают не менее 1/9 площади стола.

7. Среди четырех выпуклых фигур любые три имеют общую точку. Докажите, что все фигуры имеют общую точку.

8. Плоскость покрыта конечным числом полуплоскостей. Докажите, что из них можно выбрать три (или две) полуплоскости, которые покрывают всю плоскость.

9. Прожектор освещает прямой угол. Четыре прожектора поместили в произвольных точках плоскости. Докажите, что прожекторы можно повернуть так, что они осветят всю плоскость.

10. На шахматной доске расставляют королей так, чтобы они били все клетки. Каково наименьшее число королей,

11. Из листа клетчатой бумаги 29 х 29 клеток вырезали 99 квадратов 2 × 2. Докажите, что из остатка можно вырезать еще один такой квадрат.

12. Пусть А наибольшее число попарно непересекающихся кругов диаметра 1, центры которых лежат внутри многоугольника М, B наименьшее число кругов диаметра 2, которыми можно покрыть многоугольник. Что больше: А или В?

13. На круглом столе радиуса R лежат без наложений п круглых монет радиуса г. Докажите, что ½ (R/r-1) ≤ √n ≤ R

14. Пусть S — площадь выпуклого многоугольника, Р — его периметр, R - радиус максимального вписанного круга. Докажите, что S/P ≤ R ≤ 2S/P.

15. Окружность покрыта бесконечным числом открытых дуг. Докажите, что можно выбрать несколько дуг, которые покрывают окружность и имеют суммарную длину не более 720°?

16. На листе бумаги расположено несколько прямоугольников, стороны которых параллельны осям координат. Каждые два прямоугольника имеют общие точки. Докажите, что существует точка, принадлежащая всем прямоугольникам.

Разрезания и замощения

В некоторых задачах фигура разрезается на меньшие части (например, на две одинаковые), или наоборот, из нескольких данных фигур составляется одна большая. Это задачи на разрезание или замощение. Замощение является одновременно покрытием и упаковкой.

Пример 1. За какое наименьшее количество выстрелов можно с гарантией подбить четырехклеточный корабль в игре «морской бой»?

Решение. Произведем выстрелы по полям, отмеченным на рис. 4а. Любое положение корабля 1 х 4 накрывает одно отмеченное поле. Поэтому 24 выстрелов хватит.

Задачи

1. На клетчатой бумаге даны произвольные n клеток. Докажите, что среди них можно выбрать не меньше n/4 клеток, не имеющих общих точек.

2. Квадратная площадь размером 100 х 100 выложена квадратными плитами 1 х 1 четырех цветов: белого, красного, черного и серого так, что никакие две плиты одинакового цвета не соприкасаются друг с другом (т.е. не имеют общей стороны или вершины). Сколько может быть красных плит?

3. Двое по очереди ставят на шахматную доску коня, причем его можно ставить на любую незанятую клетку, которая не бьется ни одним из уже стоящих коней. Тот, кто не может поставить коня, проигрывает. Кто победит при правильной игре? Указание. Разбейте доску на пары клеток, связанные ходом коня.

Раскраски

Говорят, что фигура покрашена в несколько цветов, если каждой точке фигуры приписан определенный цвет. Бывают задачи, где раскраска уже дана, например для шахматной доски, бывают задачи, где раскраску с данными свойствами нужно придумать, и бывают задачи, где раскраска используется как идея решения.

Пример 1. Из шахматной доски вырезали две противоположные угловые клетки. Докажите, что оставшуюся фигуру нельзя разрезать на «домино» из двух клеток

Решение. Каждая фигура «домино» содержит 1 белую и 1 черную клетку. Но в нашей фигуре 32 черных и 30 белых клеток (или наоборот).

Пример 2. Можно ли все клетки доски 9 х 9 обойти конем по одному разу и вернуться в исходную клетку?

Решение. Каждым ходом конь меняет цвет клетки, поэтому, если существует обход, то число черных клеток равно числу белых, что неверно.

Пример 3. Дан куб 6х6х6. Найти максимально возможное число параллелепипедов 4 х 1 х 1 (со сторонами параллельными сторонам куба), которые можно поместить в этот куб без пересечений.

Идея решения. Легко поместить 52 параллелепипеда внутрь куба. Докажем, что нельзя больше. Разобьем куб на 27 кубиков 2 х 2 х 2. Раскрасим их в шахматном порядке. При этом образуется 104 клетки одного цвета (белого) и 112 - другого (черного). Осталось заметить, что каждый параллелепипед содержит две черных и две белых клетки. Ответ: 52.

Задачи

1. В каждой клетке доски 5 х 5 сидел жук. Затем каждый жук переполз на соседнюю (по стороне) клетку. Докажите, что осталась хотя бы одна пустая клетка.

2. Прямоугольник м х п разрезан на уголки из трех клеток. Докажите, что разность между количеством уголков, ориентированных как на рис. 5а), и количеством уголков, ориентированных как на рис. 5б), делится на 3.

3. Прямая раскрашена в 2 цвета. Докажите, что найдутся 3 точки А, В, С одного цвета такие, что АВ = ВС.

4. Раскрасьте прямую в 3 цвета так, чтобы нельзя было найти трех точек А, В, С разного цвета таких, что АВ = ВС.

5. Плоскость раскрашена а) в 2 цвета, б) в 3 цвета. Докажите, что найдутся 2 точки одного цвета, расстояние между которыми равно 1.

6. Раскрасьте плоскость а) в 9, б) в 7 цветов так, чтобы не нашлось двух точек одного цвета на расстоянии 1.

7. Можно ли замостить доску 6 х 6 клеток полосками из трех клеток и одним уголком из трех клеток?

8. Можно ли замостить доску 10 х 10 прямоугольниками 4 х 1?

9. Можно ли доску 5х7 покрыть уголками из трех клеток в несколько слоев? Указание. Расставить числа, чтобы общая сумма была положительна, а сумма в каждом уголке отрицательна.

Игры

Математические игры отличаются от обычных тем, что в них можно заранее определить исход игры. В таких играх предполагается, что игроки не делают ошибок, т.е. играют наилучшим образом. Для доказательства чьей-то победы или ничейного исхода используются следующие основные идеи:

Соответствие. Наличие удачного ответного хода (может обеспечиваться симметрией, разбиением на пары, до- полнением числа).
Решение с конца. Последовательно определяются позиции, выигрышные и проигрышные для начинающего. Очередная позиция являются выигрышной, если из нее можно получить ранее определенную проигрышную позицию, и является проигрышной, если любой ход из нее ведет к попаданию в ранее определенную выигрышную позицию.
Передача хода. Если мы можем воспользоваться стратегией противника, то наши дела не хуже чем у него. Например, выигрыш (или ничья) обеспечивается, когда можно по своему желанию попасть в некоторую позицию либо заставить противника попасть в нее.

Пример 1. Двое кладут по очереди пятаки на круглый стол. Проигрывает тот, кто не сможет положить очередной пятак. Кто проигрывает?

Решение. Выигрывает первый. Он кладет пятак в центр симметрии стола, после чего на любой ход второго у первого всегда есть симметричный ответ.

Пример 2. В куче 25 камней. Игроки берут по очереди 2,4 и 7 камней. Проигрывает тот, кому некуда ходить. Кто победит?

Решение. Случаи 0, 1 камня проигрышны для начинающего. Поэтому случаи 2, 3, 4, 5, 7, 8 камней для начинающего выигрышны: своим ходом он переводит игру в позицию, проигрышную для противника. Аналогично, 6 и 9 камней проигрышны для начинающего, поскольку из них можно перейти только в позицию, выигрышную для противника. Рассуждая аналогично, легко установить периодичность выигрышных и проигрышных позиций и получить ответ.

Пример 3. Докажите, что в игре «крестики-нолики» на бесконечной доске у ноликов отсутствует выигрышная стратегия.

Решение. Пусть у ноликов есть выигрышная стратегия. Тогда этой стратегией могут с тем же успехом воспользоваться крестики, игнорируя свой начальный знак. (Когда крестикам приходится ходить на поле, где крестик уже стоит, они ходят куда угодно.)

Пример 4. Две компании А и В получили право освещать столицу международной шахматной мысли Нью-Васюки, представляющую собой прямоугольную сетку улиц. Они по очереди ставят на неосвещенный перекресток прожектор, который освещает весь северо-восточный угол города (от нуля до 90°). Премию О.Бендера получит та компания, которой на своем ходе нечего будет освещать. Кто выиграет при правильной игре?

Решение. Самый северо-восточный квартал города будет освещен в любом случае после первого хода. Если у В есть выигрышная стратегия, то у нее есть выигрышный ответ на ход А, состоящий в освещении только северо- восточного квартала. Но этот же ход может сделать А и воспользоваться выигрышной стратегией В! Противоречие.

Задачи

1. Есть куча из n спичек. Разрешается брать от 1 до 10 спичек, выигрывает взявший последнюю спичку. При каких n выигрывает начинающий?

2. В крайних клетках полоски 1х20 стоят белая и черная шашки. двое по очереди передвигают свою шашку на одну или две клетки вперед или назад, если это возможно (перепрыгивать через шашку нельзя). Проигрывает тот, кто не может двинуть свою шашку. Как играть начинающему, чтобы выиграть?

3. Написано 20 чисел от 1 до 20. Двое по очереди ставят перед этими числами знак + или - (знак можно ставить перед любым числом, перед которым он еще не стоит, включая первое). Игра заканчивается после того, как проставлены все 20 знаков, затем вычисляется значение получившегося выражения. Первый хочет добиться, чтобы оно было по абсолютной величине как можно меньше, а второй - как можно больше. Какое наибольшее по абсолютной величине значение может обеспечить в итоге второй игрок?

4. В строчку выписаны 1992 звездочки. Двое игроков по очереди заменяют их на цифры от 0 до 9. Может ли второй игрок добиться того, чтобы окончательное число делилось бы на 1993?

5. Есть две кучи камней, причем в большей 8 камней. Два игрока по очереди берут либо несколько камней из одной кучи, либо по равному количеству камней из обеих куч. Выигрывает тот, кто возьмет последний камень. Кто выиграет при правильной игре?

6. На трех крайних справа полях доски 1 х n стоит по фишке. Двое играют в следующую игру: каждый по очереди берет одну из фишек и передвигает ее на несколько полей влево. Проигрывает тот, кто не может сделать свой ход. Кто выигрывает при правильной игре?

7. В 50 коробках лежат 100 конфет. Девочка и мальчик берут поочередно по конфете. Может ли мальчик добиться того, чтобы последние две конфеты лежали в одной коробке?

8. В одной куче 18 конфет, а в другой — 23. Двое по очереди съедают одну из куч, а другую делят еще на две кучи. Тот, кто не сможет поделить кучу (если там одна конфета), проигрывает. Как должен играть начинающий, чтобы выиграть?

9. На бесконечном листе клетчатой бумаги вое по очереди соединяют узлы соседних клеток по вертикали или горизонтали, один красным отрезком, другой синим. Нельзя обводить один отрезок дважды. Может ли первый игрок создать замкнутый контур красного цвета?

10. Пять ямок расположены в ряд. В каждой лежит по шарику. За ход разрешается переложить все шарики из какой-нибудь ямки в соседнюю справа ямку. Проигрывает тот, кто не может сделать ход (когда все шарики лежат в самой правой ямке). Кто победит, если игроки не делают ошибок?

11. Игра происходит на бесконечной плоскости. Играют двое: один передвигает одну фишку-волка, другой — 50 фишек-овец. После хода волка ходит какая-нибудь из овец, затем после следующего хода волка опять какая-нибудь из овец и т.д. И волк, и овцы передвигаются за один ход в любую сторону не более чем на один метр. Верно ли, что при любой первоначальной позиции волк поймает хотя бы одну овцу?

Процессы и операции

При решении многих олимпиадных задач организуются процессы. Бывают процессы построения нужного объекта, «причесывания задачи», последовательного улучшения некоторой величины и другие. Отметим, что спуск и индукция тоже являются процессами.

Пример 1. В парламенте у каждого не более трех врагов. Докажите, что парламент можно разделить на две палаты так, что у каждого парламентария в своей палате будет не более одного врага.

Решение. Нет никакой надежды сразу указать нужное разбиение парламента, но можно построить это разбиение поэтапно с помощью процесса. Самое простое, что можно придумать, пересаживать парламентариев по одному. Разобьем парламент произвольным образом на две палаты и организуем процесс пересаживания: выберем парламентария, имеющего не менее двух врагов в своей палате, и пересадим его в другую палату. Общее число пар врагов, сидящих в одной палате, при этом уменьшается. Процесс остановится, поскольку число враждующих пар конечно. Остановка процесса означает построение нужного разбиения.

Пример 2. В клетки таблицы m х n вписаны некоторые числа. Разрешается одновременно менять знак у всех чисел одного столбца или одной строки. Докажите, что несколькими такими операциями можно добиться того, чтобы суммы чисел, стоящих в любой строке и в любом столбце, были неотрицательны.

Решение. Организуем процесс: если сумма чисел в какой-то строке (или в каком-то столбце) отрицательна, то поменяем знак у чисел этой строки (столбца). Для доказательства остановки этого процесса найдем некоторую характеристику таблицы, которая монотонно возрастает при каждом шаге. Искомая характеристика сумма всех чисел. На каждом шаге эта сумма увеличивается. Процесс закончится, поскольку количество расстановок знаков при числах конечно.

Пример 3. В некоторой стране из каждого города выходит нечетное число дорог. На центральной площади каждого города поднят черный или белый флаг. Каждое утро в одном из городов, у которого число соседей с флагами другого цвета больше половины, меняют цвет флага. Может ли этот процесс продолжаться бесконечно?

Решение. Пусть Р - это число дорог с концами в городах с различным цветом флагов. Каждое утро это число уменьшается. Поскольку Р - целое неотрицательное число, процесс закончится.

Пример 4. На плоскости дано N точек. Некоторые точки соединены отрезками. Если два отрезка пересекаются, то их можно заменить двумя другими с концами в тех же точках. Может ли этот процесс продолжаться бесконечно. Идея решения. На каждом шаге сокращается суммарная длина всех проведенных отрезков (это следует из неравенства треугольника), и всего существует лишь конечное число расположений отрезков с вершинами в данных точках. Поэтому данный процесс не может продолжаться бесконечно.

Пример 5. На плоскости расположены N точек. Постройте замкнутую ломаную без самопересечений, проходящую через каждую точку.

Указание. Организуйте процесс как в примере 4.

Замечание. Решения, полученные с помощью процессов, часто оформляют с помощью правила крайнего рассматривая экстремальные объекты. Например, решение этой задачи можно оформить и без понятия процесса, рассмотрев кратчайшую замкнутую ломаную, соединяющую данные N точек.

Пример 6. Вокруг города Зурбагана проходит кольцевая дорога. Все улицы начинаются или кончаются только на этой дороге и никакие 2 улицы не имеют 2 различных пересечений. Части, на которые улицы разбивают город, называются микрорайонами. В городе ввели одностороннее движение на всех улицах и кольцевой дороге. Докажите, что хотя бы один микрорайон можно объехать по правилам.

Решение. Выберем любую улицу, она разбивает город на две части. Эта улица вместе с одной из частей кольцевой дороги образует новое кольцо с односторонним движением. Внутри этого кольца все улицы образуют меньший город аналогичный Зурбагану. Снова выделим одну улицу и т.д. Поскольку число улиц уменьшается, то мы придем к городу, состоящему из одного квартала.

Пример 7. На кольцевой дороге стоят бензоколонки. Общее количество бензина в них достаточно, чтобы объехать круг. Докажите, что автомобиль с пустым баком может стартовать от некоторой бензоколонки и, заправляясь по дороге, объехать весь круг. (Бак достаточно большой.) Решение. Попробуем упростить задачу разрешим автомобилю ездить только в одном направлении. Рассмотрим для каждой бензоколонки ее «область доезда» - максимальный путь, который может проехать автомобиль с пустым баком, стартовав от этой бензоколонки и заправляясь по дороге. Ясно, что области доезда для попутных бензоколонок содержатся внутри области доезда исходной, поэтому можно считать, что весь их бензин перелит в исходную бензоколонку. К чему приведет такой процесс переливания? Число бензоколонок будет уменьшаться. Но поскольку суммарная длина областей доезда равна длине круга, то они перекрываются и процесс переливания возможен, пока весь бензин не окажется в одной бензоколонке. С нее-то и можно объехать весь круг. (Это очевидно, поскольку ее область доезда после переливаний не менялась.)

Пример 8. Можно ли построить правильный n-угольник при n > 6, все вершины которого лежат в узлах целочисленной решетки? Решение. Заметим, что если стороны многоугольника перенести параллельно в один узел решетки, то их вторые концы образуют правильный п-угольник с вершинами в узлах решетки, но длина его стороны будет меньше, чем у исходного (докажите).

Для решения задачи организуем процесс. Пускай такой n-угольник существует. Тогда построим многоугольник меньшего размера, вершины которого также принадлежат узлам решетки. Повторив эту операцию несколько раз (докажите, что при таком процессе длина стороны n-угольника стремится к нулю), получим n-угольник, который может поместиться внутри одной клетки, но, с другой стороны, все его вершины лежат в узлах решетки. Из этого противоречия вытекает невозможность построения исходного n-угольника.

Задачи

1. Есть N прямых общего положения и N точек. Докажите, что их можно занумеровать так, что перпендикуляры, опущенные из этих точек на прямые с теми же номерами, не будут пересекаться.

2. На заседании каждый член парламента дал пощечину ровно одному своему коллеге. Доказать, что парламент можно разбить на три фракции так, что члены одной фракции пощечин друг другу не давали.

3. а) Назовем многоугольник звездным, если внутри него имеется точка, из которой видны все вершины.) Со звездным многоугольником производится следующая операция: две соседние стороны, примыкающие к углу большему 180° заменяются на две новые, образующие с исходными параллелограмм. Докажите, что за конечное число таких операций получится выпуклый многоугольник. б) Докажите, что для каждого невыпуклого многоугольника найдется выпуклый многоугольник с тем же периметром, но большей площади.

4. Запись числа состоит из нулей и единиц. Любой фрагмент числа «10» заменяют на «0001». Докажите, что рано или поздно заменять будет нечего.

5. Докажите, что N точек на плоскости всегда можно покрыть несколькими непересекающимися кругами, сумма диаметров которых меньше N и расстояние между любыми двумя из которых больше 1. (Расстояние между кругами это расстояние между их ближайшими точками.)

6. Шахматную доску 8 х 8 покрыли 32-я прямоугольниками из двух клеток (доминошками). Докажите, что найдутся две доминошки, образующие квадрат 2 х 2.

7. N доминошек уложены в виде прямоугольника. Если две доминошки образуют квадрат, то их можно повернуть на 90°. Докажите, что можно все доминошки сориентировать одинаково.

8. Дан произвольный набор из n целых чисел: a1, a2 ..., аn. Из него получается новый набор: (a1+a2)/2, (a2+a3)/2, (an+a1), из этого набора следующий по тому же правилу и т.д. Докажите, что если все получающиеся числа целые, то первоначальные числа равны между собой.

9. Дан треугольник с разными сторонами. В него вписывают окружность. В точках касания строят новый треугольник. В него снова вписывают окружность и т.д. Докажите, что среди получившихся треугольников нет двух подобных.

10. Докажите, что если последняя цифра числа n не нуль, то существует такое целое k, что в десятичной записи числа kn нет нулей.

11. В классе 32 ученика. Было организовано 33 кружка, причем каждый кружок состоит из трех человек и никакие два кружка не совпадают по составу. Докажите, что найдутся два кружка, которые пересекаются ровно по одному ученику.

12. Дан ориентированный граф. Из каждой его вершины выходит п стрелок, и в каждую его вершину входит и стрелок. Докажите, что можно убрать часть ребер так, чтобы он разбился на циклы.

13. Имеется неограниченное число черных и белых кубиков. Надо построить из них сплошную башню в форме параллелепипеда так, чтобы каждый черный кубик граничил с четным числом белых, а каждый белый с нечетным числом черных. При любом ли заданном нижнем слое кубиков такую башню (конечной высоты) можно построить?

14. Две карты Москвы, одна с более мелким масштабом, наложены друг на друга так, что меньшая карта лежит целиком на большей. Докажите, что их можно проткнуть булавкой так, чтобы на обоих картах была проколота одна и та же точка Москвы.

15. Внутри квадрата со стороной 1 расположены 4 точки. Докажите, что найдутся 2 точки, расстояние между которыми не превосходит 1. Та же задача для куба и 8 точек, для 4-мерного куба и 16 точек.