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

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

Ответ: Поровну.

 

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

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

Ответ: С4n.

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

 

Пример 4. Докажите, что в числе первые 999 цифр справа после запятой – нули.

Решение. Основная идея: добавим сопряжённую иррациональность и заметим, что сумма + есть число целое, а член достаточно мал.

 

Задачи

 

1. Докажите, что дроби 1000/1993 и 993/1993 имеют одинаковую длину периодов.
2. Докажите, что сумма номеров «счастливых» билетов делится на 13. Билет называют «счастливым», если сумма первых трёх цифр его номера равна сумме трёх последних цифр.
3. По кругу расставлены 8 точек. Двое по очереди соединяют их отрезками. Первый отрезок проводится произвольно, а каждый следующий отрезок начинается из конца предыдущего. Проигрывает тот, кто не может провести новый отрезок (дважды проводить отрезок нельзя). Предположим, что игроки не делают ошибок. Кто из них победит: первый или второй?
4. На окружности даны 1987 точек, одна из них отмечена. Рассмотрим всевозможные выпуклые многоугольники с вершинами в этих точках. Каких многоугольников больше: тех, которые содержат отмеченную точку, или тех, которые её не содержат?
5. Докажите, что число представимо в виде , причём .
6. Существуют ли такие рациональные ai и bi, что ?
7. Докажите, что число представимо в виде , где .
8. Двое бросают монетку: один бросил её 10 раз, другой – 11. Чему равна вероятность того, что у второго монета упала орлом большее число раз, чем у первого?

 

Идея №13

Графы

 

Во многих ситуациях удобно изображать объекты точками, а связи между ними – линиями или стрелками. Такой способ представления называется графом. Например, схема метро – это граф. Точки называют вершинами графа, а линии – рёбрами.

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

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

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

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

3) если в связном графе ровно  две нечётные вершины, то существует правильный обход, причём в одной из них он начинается, а в другой – кончается;

4) в любом графе количество  нечётных вершин чётно.

 

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

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

 

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

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

Ответ: 784913526.

 

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

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

 

Задачи

 

1. Расположите на плоскости 6 точек и соедините их непересекающимися линиями так, чтобы из каждой точки выходили четыре линии.
2. В трёх вершинах правильного пятиугольника расположили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться того, чтобы одна из фишек вернулась на своё место, а две другие поменялись местами?
3. В марсианском метро 100 станций. От любой станции до любой другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая станция найдётся.
4. Докажите, что в плоском графе найдётся вершина, из которой выходит не более 5 рёбер. 
   Следствия: 
   а) Вершины плоского графа можно раскрасить в 6 цветов так, чтобы вершины, соединённые ребром, имели разный цвет. 
   б) Конечная плоская карта допускает раскраску в 6 цветов такую, что соседние страны будут окрашены в разные цвета.
5. Клетчатая плоскость раскрашена десятью красками так, что соседние (т.е. имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Каково минимальное возможное число пар соседних красок? (Две краски называются соседними, если ими покрашены какие-то две соседние клетки).
6. В тридевятом царстве каждые два города соединены дорогой с односторонним движением. Докажите, что существует город, из которого в любой другой можно проехать не более чем по двум дорогам.
7. В городе на каждом перекрёстке сходится чётное число улиц. Известно, что с любой улицы города можно проехать на любую другую. Докажите, что все улицы города можно объехать, побывав на каждой по одному разу.
8. Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятёрок подряд стоящих цифр встречаются все 32 возможных комбинации. Найдите пять последних цифр последовательности.
9. Дан правильный 45-и угольник. Можно ли так расставить в его вершинах цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой занумерованы этими цифрами. 
   Указание. Рассмотреть полный граф, вершины которого суть цифры цифры от 0 до 9. Задача сводится к его обходу.
10. Докажите, что можно расположить по кругу символы 0 и 1 так, чтобы любой возможный набор из n символов, идущих подряд, встретился. 
    Указание. Рассмотреть граф, вершины которого суть слова длины n – 1. Две вершины u и v соединяются стрелкой, если существует слово длины n, у которого u является началом, а v – концом.

 

Идея №14

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

 

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

Упаковка – это размещение нескольких непересекающихся фигур внутри данной фигуры.

 

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

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

 

Пример 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. Каким наименьшим числом прямых разрезов можно наверняка задеть монету?

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

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

Воспользуемся следующим замечательным фактом: если сферу пересечь двумя параллельными плоскостями, то площадь сферы между ними зависит только от расстояния между плоскостями и не зависит от их положения.

Опишем вокруг блина сферу. Через края каждой полосы проведём две перпендикулярные к ней плоскости. Они высекут на сфере кольца одинаковой площади. Осталось покрыть сферу наименьшим числом колец известной площади.

 

 

Задачи

 

1. Квадратный каток надо осветить четырьмя прожекторами, висящими на одной высоте. Каков наименьший радиус освещённых кругов?
2. На плоскости горит лампочка. Можно ли расположить три круга так, чтобы освещённая область была ограниченной?
3. Коридор полностью покрыт несколькими ковровыми дорожками. Докажите, что можно убрать несколько дорожек так, чтобы 
   а) коридор был полностью покрыт, а общая длина оставшихся дорожек была не больше удвоенной длины коридора; 
   б) оставшиеся дорожки не перекрывались и их суммарная длина была не меньше половины длины коридора.
4. Пол в прямоугольной комнате 6 х 3 м2 покрыт квадратными коврами разных размеров, края которых параллельны стенам. Докажите, что можно убрать несколько ковров так, чтобы оставшиеся ковры покрывали более 2 м2.
5. На столе лежат 15 журналов, полностью покрывая его. Докажите, что можно убрать 7 журналов так, чтобы оставшиеся покрывали не менее 8/15 площади стола.
6. Круглый стол покрыт круглыми салфетками разных размеров. Докажите, что можно выбрать несколько салфеток, которые не пересекаются и закрывают не менее 1/9 площади стола.
7. Среди четырёх выпуклых фигур любые три имеют общую точку. Докажите, что все фигуры имеют общую точку.
8. Плоскость покрыта конечным числом полуплоскостей. Докажите, что из них можно выбрать три (или две) полуплоскости, которые покрывают всю плоскость.
9. Прожектор освещает прямой угол. Четыре прожектора поместили в произвольных точках плоскости. Докажите, что прожекторы можно повернуть так, что они осветят всю плоскость.
10. На шахматной доске расставляют королей так, чтобы они били все клетки. Каково наименьшее число королей?
11. Из листа клетчатой бумаги 29 х 29 клеток вырезали 99 квадратов 2 х 2. Докажите, что из остатка можно вырезать ещё один такой квадрат.
12. Пусть А – наибольшее число попарно непересекающихся кругов диаметра 1, центры которых лежат внутри многоугольника М, В – наименьшее число кругов диаметра 2, которыми можно покрыть многоугольник. Что больше: А или В?
13. На круглом столе радиуса R лежат без наложений n круглых монет радиуса r. Докажите, что 
    .
14. Пусть S – площадь выпуклого многоугольника, P – его периметр, R – радиус максимального вписанного круга. Докажите, что 
    .
15. Окружность покрыта бесконечным число открытых дуг. Докажите, что можно выбрать несколько дуг, которые покрывают окружность и имеют суммарную длину не более 720о?
16. На листе бумаги расположено несколько прямоугольников, стороны которых параллельны осям координат. Каждые два прямоугольника имеют общие точки. Докажите, что существует точка, принадлежащая всем прямоугольникам.