Нестандартные задачи на олимпиадах по математике Учебно (стр. 2 из 5)

3. Можно ли окрасить на клетчатой бумаге 25 клеток так, чтобы у каждой из них было нечётное число окрашенных соседей? (Соседними клетками считаем те, у которых есть общая сторона.)

Решение: Пусть на клетчатой бумаге окрашено несколько клеток и n-число окрашенных клеток, имеющих ровно k окрашенных соседей. Пусть N – число общих сторон окрашенных клеток. Так как каждая из них принадлежит ровно двум окрашенным клеткам, то N=(n₁+2n₂+3n₃+4n₄)/2= (n₁+n₃)/2+n₂+n₃+2n₄. Поскольку N – целое число, то число n₁ + n₃ четно.

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

4. На плоскости дана замкнутая ломаная с конечным числом звеньев. Прямая l пересекает её в 1985 точках. Докажите, что существует прямая, пересекающая эту ломаную более чем в 1985 точках.

Решение: Прямая l задает две полуплоскости; одну из них будем называть верхней, а другую нижней. Пусть n₁ (соответственно n₂) –число вершин ломаной, лежащих на прямой l, для которых оба выходящих из них звена лежат в верхней (соответственно в нижней) полуплоскости, а m-число всех остальных точек пересечения прямой l и ломаной. Совершим обход ломаной, выйдя из некоторой точки, не лежащей на прямой l, и вернувшись в ту же точку. При этом мы переходим из одной полуплоскости в другую, только проходя через любую из m точек пересечения. Так как мы вернемся в ту же точку, из которой начали обход, то m четно. По условию n₁ + n₂ + m = 1985, потому что число

n₁+n₂ нечетное, т.е. n₁ = n₂ .Пусть для определенности n_1> n_2. Проведём тогда в верхней полуплоскости прямую l_1, параллельную l и удаленную от неё на расстояние меньшее, чем любое ненулевое расстояние от l до вершин ломаной (рис.). Число точек пересечения ломаной с прямой l₁ равно 2n₁+m>n₁+n₂+m=1985, т.е. l₁ –искомая прямая.

----------------------------------------------------------------- l₁

l

5. Окружность разбита точками на 3k дуг: по k дуг длиной 1,2 и 3. Докажите, что найдутся две диаметрально противоположные точки деления.

Решение: Предположим, что окружность разбита на дуги указанным образом, причем диаметрально противоположных точек деления нет. Тогда против концов любой дуги длиной 1 не лежат точки разбиения, поэтому против неё лежит дуга длиной 3. Выбросим одну из дуг длиной 1 и противолежащую ей дугу длиной 3. При этом окружность разбивается на две дуги. Если на одной из них лежит m дуг длиной 1 и n дуг длиной 3, то на другой лежит m дуг длиной 3 и n дуг длиной 1. Общее количество дуг длиной 1 и 3, лежащих на этих двух « больших » дугах, равно 2(k-1), поэтому n+m=k-1. Так как, кроме дуг длиной 1 и 3, есть дуги только с четной длиной, то четность длины каждой из двух рассматриваемых дуг совпадает с четностью числа k-1. С другой стороны, длина каждой из них равна (6k-1-3)/2=3k-2. Получено противоречие, так как числа k-1 и 3k-2 имеют разную четность.

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

Решение: Возьмем соседние звенья AB и BC и назовем уголком угол, симметричный углу ABC относительно B (на рис. уголок заштрихован). Такие же уголки можно рассмотреть для всех вершин ломаной. Ясно, что число особых пар равно числу точек пересечения звеньев с уголками. Остается заметить, что число звеньев ломаной, пересекающихся с одним уголком, четно, так как по пути от A к C ломаная входит в уголок столько же раз, сколько выходит из него.

В С

А

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

0

0

0

1 2

1

2

1 2

1 1

Решение: Рассмотрим отрезки, на которые разбита сторона 01. Пусть а - число отрезков вида 00, b-число отрезков вида 01. Для каждого отрезка рассмотрим число нулей, стоящих на его концах, и сложим все эти числа. В итоге получим 2а+b. С другой стороны, все « внутренние » нули входят в эту сумму дважды, а есть еще один нуль, стоящий в вершине исходного треугольника. Поэтому число 2а+b нечетно, т.е. b нечетно.

Перейдем теперь к разбиению треугольника. Пусть а₁-общее количество треугольников вида 001 и 011, а b₁- число треугольников вида 012. Для каждого треугольника рассмотрим число его сторон вида 01 и сложим все эти числа. В итоге получим 2а₁+b_1. С другой стороны, все « внутренние » стороны входят в эту сумму дважды, а все « граничные » лежат на стороне 01 исходного треугольника и число их нечетно по предыдущему рассуждению. Поэтому число 2а₁+b₁ нечетно, в частности, b₁=0.

8. Вершины правильного 2n-угольника А₁…А_2n разбиты на n пар. Докажите, что если n=4m+2 или n=4m+3, то две пары вершин являются концами равных отрезков.

Решение: Предположим, что все пары вершин задают отрезки разной длины. Отрезку A_pA_q поставим в соответствие наименьшее из чисел |p-q| и 2n-|p-q|. В результате для данных n пар вершин получим числа 1, 2…, n; пусть среди этих чисел k четных и n-k нечетных. Нечетным числам соответствуют отрезки A_pA_{q, где} числа p и q разной четности. Поэтому среди вершин остальных отрезков будет k вершин с четными номерами и k вершин с нечетными номерами, причем отрезки соединяют вершины с номерами одной четности. Следовательно, число k четно. Для чисел n вида 4m, 4m+1, 4m+2 и 4m+3 количество k четных чисел равно 2m, 2m+1, 2m+2, 2m+3 соответственно, поэтому n=4m или n=4m+1.

3. Делимость

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

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