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

 

Идея №6

Инварианты

 

Инвариант – величина, которая не изменяется в результате некоторых операций (например, разрезание и перестановка частей фигур не меняет суммарной площади). Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться чётность или раскраска. В задачах про сумму цифр используют остатки от деления на 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. Докажите, что сумма квадратов расстояний от вершин праивльного n-угольника до любой прямой, проходящей через его центр есть величина постоянная.
5. (сизифов труд). На горе 1001 ступенька, на некоторых лежат камни, по одному на ступеньке. Сизиф берёт любой камень и переносит его вверх на ближайшую свободную ступеньку (т.е. если ближайшая ступенька свободна, то на неё, а если она занята, то на несколько ступенек вверх до первой свободной). После этого Аид скатывает на одну ступеньку вниз один из камней, у которых предыдущая ступенька свободна. Камней 500 и первоначально они лежали на нижних 500 ступеньках. Сизиф и Аид действуют по очереди, начинает Сизиф. Цель Сизифа положить камень на верхнюю ступеньку. Может ли Аид ему помешать?
6. Столица страны соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с 10 городами (если А соединён с В, то В соединён с А). Известно, что из любого города можно попасть в любой другой (может быть, с пересадками). Докажите, что можно закрыть половину авиалиний, идущих из столицы, так что возможность попасть из любого города в любой другой сохранится.
7. Во время перемирия за круглым столом разместились рыцари из двух враждующих станов. Оказалось, что число рыцарей, справа от которых сидит враг, равно числу рыцарей, справа от которых сидит друг. Докажите, что число рыцарей делится на 4.

 

Идея №7

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

 

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

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

Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.

Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше чем n/k*k = n. Противоречие.

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

Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы А можно назвать кроликами, а элементы В – ящиками.

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

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

 

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

Решение. Всего в году 365 дней. Назовём дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше 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. Докажите, что по крайней мере три из этих прямых проходят через одну точку.

 

Идея №8

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

 

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

Остаток может выступать в роли инварианта (например, остаток от деления на 9 в задачах про сумму цифр).

 

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

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

 

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

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

 

 

Задачи

 

1. Какие числа можно представить в виде разности двух квадратов целых чисел?
2. Если p – простое число, большее 3, то p2 – 1 делится на 24.
3. При каких n число 2n – 1 делится на 7?
4. Известно, что сумма нескольких натуральных чисел делится на 6. Докажите, что сумма кубов этих чисел тоже делится на 6.
5. Если в целочисленной арифметической прогрессии встретился квадрат целого числа, то квадратов в ней бесконечно много. Докажите.

 

Идея №9

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

 

 

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

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

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