Некоторые олимпиадные идеи

 

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

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

 

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

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

 

 

 

Задачи 

 

1. Решите уравнение в натуральных числах 7x – 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 «крокодил» - это шахматный конь). при каких N «крокодил» может пройти с любой клетки бесконечной шахматной доски на любую другую?

 

Идея №10

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

 

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

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

 

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

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

 

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

Решение. Рассмотрим грань с наибольшим числом сторон. Обозначим эту грань G, число её сторон n. К каждой стороне G примыкает грань многогранника, всего примыкающих граней n. Число сторон в каждой грани заключено между 3 и n – 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. Поэтому любой из рассматриваемых образов фигуры, пересекающий малый квадрат, целиком лежит внутри большого. Левый нижний угол маленького квадрата расположим так, чтобы он принадлежал рассматриваемой фигуре.

Оценим площадь фигур, пересекающих малый квадрат. Таких фигур не меньше l2, т.к. сдвиги на векторы вида (m, n) (0 < m < l, 0 < n < l) переводят левый нижний угол квадрата в точку внутри квадрата, а таких сдвигов всего имеется ([l] + 1)2 > l2. Если предположить, что образы фигуры не пересекаются, то их суммарная площадь должна не превосходить площади большого квадрата. Получаем неравенство: 
Sl2 < (l + 2d)2 
или 
(S – 1)l2 – 4dl – 4d2 < 0. 
В левой части последнего неравенства стоит квадратный трёхчлен относительно l со старшим коэффициентом большим нуля. При достаточно больших l он принимает положительные значения (его график – парабола с ветвями вверх). Значит, можно подобрать такое l, при котором последнее неравенство не будет выполняться. Поэтому предположение, что образы нашей фигуры не пересекаются приводит к противоречию.

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

 

Задачи

 

1. Путешественник отправился из своего родного города А в самый удалённый от него город страны В; затем из В - в самый удалённый от него город С и т.д. Докажите, что если С не совпадает с А, то путешественник никогда не вернётся домой. (Расстояния между городами страны различны).
2. Назовём автобусный билет (с шестизначным номером) счастливым если сумма цифр его номера делится на 7. Могут ли два билета подряд быть счастливыми?
3. В оду из голов 100-голового дракона пришла мысль расположить свои головы так, чтобы каждая находилась между двумя другими. Сможет ли он это сделать? (Головы – это точки на плоскости).
4. На столе лежат одинаковые монеты без наложений. Докажите, что найдётся монета, которая касается не более трёх других.
5. На столе лежат монеты без наложений. Докажите, что найдётся монета, которая касается не более пяти других.
6. На столе лежат монеты без наложений. Докажите, что одну из них можно передвинуть по столу к его краю, не сдвинув других монет.
7. На полях шахматной доски расставлены целые числа, причём никакое число не встречается дважды. Докажите, что есть пара соседних (имеющих общую сторону) клеток, числа в которых отличаются меньше, чем на 5.
8. На окружности стоят 30 чисел, каждое из которых равно модулю разности двух следующих за ним по часовой стрелке. Сумма всех чисел равна 1. Что это за числа и как они стоят на окружности?
9. На прямой расположена колония из конечного числа бактерий. В моменты 1, 2, 3, … некоторые из бактерий могут погибать; новых бактерий не возникает ни в один момент. Погибают те и только те бактерии, от которых ни слева на расстоянии 1, ни справа на расстоянии нет бактерий. Существует ли колония бактерий, которая будет жить вечно?
10. В течение дня в библиотеке побывало 100 читателей. Оказалось, что в тот день из любых трёх читателей двое в библиотеке встретились. Докажите, что сотрудник библиотеки мог сделать важное сообщение в такие два момента времени, чтобы все 100 человек его услышали. (Каждый читатель побывал в библиотеке только один раз)
11. На плоскости отмечено несколько прямых. Известно, что через точку пересечения любых двух отмеченных прямых, проходит по крайней мере ещё одна. Докажите, что все отмеченные прямые проходят через одну точку.
12. Дан параллелограмм с вершинами в целых точках такой, что внутри или на границе больше целых точек нет. Докажите, что его площадь равна единице.
13. (лемма Минковского). Докажите, что центрально-симметричная относительно начала координат выпуклая фигура площади больше 4 содержит ещё хотя бы одну целую точку.

Указание. Произведите гомотетию с коэффициентом ½ и воспользуйтесь результатами примера 7.

 

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

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

 

 

Идея №11

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

 

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

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

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

 

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

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

Будем увеличивать число мальчиков в классе, не изменяя числа девочек и не нарушая условия задачи.

1 шаг. «Впишем» всех девочек в число участников обоих походов. От этого доля мальчиков в классе не изменится, а в походах – уменьшится. Итак, можно считать, что все девочки ходили в оба похода.

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

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

4 шаг. Задача стала тривиальной: в обоих походах были все девочки и ровно половина мальчиков. Обозначим число девочек 3х, тогда мальчиков в походах было не больше 2х, а во всём классе – не больше 4х. Максимальное число мальчиков в классе 4х, а это равно 4/7 класса.

 

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

Решение. Нетрудно получить число 1/28, усредняя число в первой ячейке со всеми остальными по очереди. Труднее доказать, что меньше получить нельзя.

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

Теперь всё ясно: новая операция либо ничего не меняет, либо уничтожает один нуль и уменьшает все числа в два раза. Поскольку новая операция не позволяет получить число меньшее 1/28, то исходная операция – тем более.

 

Задачи

 

1. В кладовой лежат 300 сапог: 100 хромовых, 100 кирзовых и 100 яловых, причём левых и правых поровну – по 150. Докажите, что из имеющихся сапог можно составить по крайней мере 50 пар.
2. На плоскости нарисовано несколько точек. Двое по очереди соединяют их отрезками. Отрезки могут выходить из одной точки, но не должны пересекаться. Кто не может сделать ход, проигрывает. Докажите, что при любых ходах игроков победителем будет один и тот же, а кто именно – определяется лишь начальной позицией.
3. Дан выпуклый многоугольник площади 9. Его пересекают десять параллельных прямых на расстоянии 1 друг от друга. Докажите, что сумма длин отрезков, высеченных многоугольником на этих прямых, не более десяти.
4. В N-мерном кубе покрашено более половины вершин. Ребро называется покрашенным, если покрашены обе ограничивающие его вершины. Докажите, что покрашено не менее N ребёр.

 

Идея №12

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

 

Проще всего понять идею на примерах (см. также тему «Игры»).

 

Пример 1. Найдите сумму чисел 1 + 2 + 3 +…+ 100.

Решение (его придумал маленький Гаусс). Напишем ту же сумму в обратном порядке и сложим числа по столбцам: 
  х =    1 +    2 +   3 + …  + 100 
  х = 100 +  99 +  98 + …  +    1 
2х = 101 + 101 + 101 + … + 101 = 10100

Ответ: 5050.

 

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

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

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