Внеклассная работа по предмету.

Подготовка учащихся к олимпиадам.

В целях развития у учащихся интереса к математике проводятся математические олимпиады различных уровней. Умение решать задачи, особенно олимпиадные, всегда являлось одним из показателей математической одаренности ученика. Недаром многие вузы для победителей и призеров различного уровня олимпиад устанавливают льготы. Многие часто представляют математические олимпиады как соревнование на «самого умного математика школы (города, области, …)». Будь это так, олимпиады не стоили бы десятой доли тех усилий, которые вкладываются в них. К счастью, цели олимпиад гораздо богаче. Кроме спортивных, это:

• повышение интереса школьников к занятиям математикой;
• выявление одаренных учащихся и привлечение их к систематическим внеклассным и внешкольным занятиям математикой;
• подведение итогов и стимулирование работы с одаренными детьми.

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

Работу олимпиадных кружков я строю на следующих принципах.

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

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

3. Принцип опережающей сложности.Не следует загружать ученика большой по объему, но несложной работой, так же как и ставить его в положение лисицы перед виноградом, задавая для него непосильные задачи. Условия задач должны быть понятны и привлекательны для учеников, решения ярки, неожиданны и красивы. Слишком легко и слишком трудно – равно плохо. Не случайно оптимальными для развития цивилизации оказались широты, климатические условия которых, не позволяя человеку расслабиться, в тоже время не превращали его жизнь в сплошную борьбу за существование. На практике реализовать этот принцип можно, например, следующим образом. Задавая на дом очередную недельную порцию задач (от 10 до 15), желательно подобрать их так, чтобы 7 – 8   из них были доступны практически всем членам кружка, 3 – 4 были по силам лишь некоторым, а 1 – 2 , пусть не намного, но превышали возможности даже самых сильных учеников. Ученик имеет право отложить трудную задачу, если он потрудился над ее решением определенное время, и она у него не получилась. В этом случае процесс усвоения новых идей будет более эффективным. Действие принципа будет тем лучше, чем ближе друг к другу по уровню математического развития члены кружка. Кроме того, он развивает такие полезные качества, как сознательность, внутренняя честность, научное честолюбие.

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

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

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

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

7. Принцип работы с текстом.Необходимо, чтобы ученик понял, что математические книги нужно не читать, а изучать с карандашом, бумагой и напряжением мысли. Часто олимпиадные задачи снабжены лишь краткими указаниями. Понять эти указания, заполнить логические пробелы, выполнить промежуточные вычисления, рассмотреть самостоятельно варианты, сопровождающиеся оборотом «аналогично»,  - главное назначение этих задач.

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

Трудно рекомендовать какой-либо общий план кружка – форма их может широко варьироваться. Занятия могут проходить в виде лекции или семинара, олимпиады, математической регаты или математического боя, командного соревнования по решению задач, носить шутливый или критический характер. Планирование кружковых занятий тоже должно носить гибкий характер: неожиданно возникший на уроке вопрос может послужить темой ближайшего занятия. Интересная книга или статья также должна обсуждаться на кружке. Приведу пример тематического планирования занятий олимпиадного кружка в 8 классе.

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

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

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

Принцип Дирихле и его применение
при решении задач

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

На первый взгляд, непонятно, почему это совершенно оче­видное предложение, тем не менее, является мощным матема­тическим методом решения задач, причем самых разнообраз­ных. Всё дело оказывается в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «зай­цев», а что — в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток». Выбор «зайцев» и «клеток» часто неочевиден. Далеко не всегда по формулировке задачи можно определить, что следует применить принцип Дирихле. Глав­ное же достоинство данного метода решения состоит в том, что он дает неконструктивное решение, (то есть мы знаем, что такие клетки есть, но где именно они находятся, часто указать не можем); попытка же дать конструктивное доказательство приводит к большим трудностям.

Рассмотрим другие формулировки принципа Дирихле:

«Пусть в п клетках сидят т зайцев, причем п> т. Тогда найдется хотя бы одна пустая клетка». (Доказывается анало­гично — методом от противного);

«Если т зайцев сидят в п клетках, то найдется клетка, в которой сидят не меньше, чем  зайцев, и найдется клетка, в  которой сидят не больше, чем  зайцев»;

«Если т зайцев съели п килограммов травы, то какой-то  заяц съел не менее   килограммов травы и какой-то заяцсъел не больше  килограммов (а если кто-то съел больше среднего, то кто-то съел меньше среднего)» (непрерывный принцип),

«Если в п клетках сидят т зайцев и , то в какой-то из клеток сидят, по крайней мере,  заяц» (обобщенный принцип)

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

Сформулируем дан­ные утверждения (все они легко доказываются методом от противного):

1. Если на отрезке длиной 1 расположено несколько отрез­ков, сумма длин которых больше 1, то, по крайней мере, два из них имеют общую точку.
2. Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2π, то, по крайней мере, две из них имеют общую точку.
3. Если внутри фигуры площадью 1 расположено несколько фигур, сумма площадей которых больше 1, то, по крайней мере, две из них имеют общую точку.

Примеры задач, решаемых данным методом.

Задача №1. Внутри равностороннего треугольника со стороной 1 см расположено 5 точек. Докажите, что расстояние между неко­торыми двумя из них меньше 0,5 см.

Решение.На примере  решения этой задачи очень хорошо видны все досто­инства принципа Дирихле. Итак, при решении сначала надо выбрать что-то за «зайцев». Так как в условии задачи фигури­рует число «5», то пусть 5 точек будут «зайцами». Так как «клеток» должно быть меньше, и чаще всего на 1, то их долж­но быть 4. Как получить эти 4 «клетки»? Так как в условии задачи есть еще 2 числа: 1 и 0,5; причем второе меньше перво­го в 2 раза, то можно получить 4 «клетки», разбив равносто­ронний треугольник с помощью проведения средних линий. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками».

Так как «зайцев» — 5, «клеток» — 4 и 5 > 4, то по прин­ципу Дирихле найдется «клетка» — равносторонний тре­угольник со стороной 0,5 см, в который попадут не менее 2 «зайцев» — точек. А так как все 4 треугольника равны и рас­стояние между точками в любом треугольнике будет меньше, чем 0,5 см, то мы доказали, что между некоторыми 2 точками из 5 расстояние будет меньше, чем 0,5 см.

Замечание. Можно разбить треугольник и на другие фигу­ры (в этих случаях придется вместо средних линий треуголь­ника (одной, двух или трех) проводить соответственно дуги радиуса 0,5 см с центром в вершинах треугольника).

Возможные варианты получения «клеток» показаны на рисунках

Задача №2. Дано 12 целых чисел. Докажите, что из них можно вы­брать 2, разность которых делится на 11.

Решение, Примем числа за «зайцев». Так как их 12, то «клеток» должно быть меньше. Пусть «клетки» — это остатки от деления целого числа на 11. Всего «клеток» будет 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Тогда по принципу Дирихле найдется «клетка», в которой будут сидеть не менее чем 2 «зайца», то есть найдутся 2 целых числа с одним остатком. А разность 2 чисел с одинаковым остатком от деления на 11, будет де­литься на 11.

Задача №3.  В ковре размером 4x4 метра моль проела 15 дырок. До­кажите, что из него можно вырезать коврик размером 1x1 метр, не содержащий внутри себя дырок. (Дырки можно счи­тать точечными).

Решение. Разрежем ковёр на 16 ковриков размерами 1x1 метр. Так как ковриков — «клеток» — 16, а дырок — «зайцев» — 15, то найдется хотя бы одна «клетка», в которой не будет «зайцев», то есть найдётся коврик без дырок внутри. Здесь мы применили другую формулировку принципа Дирихле.

Задача №4.  В классе 27 учеников. Найдётся ли месяц, в котором от­мечают свои дни рождения не меньше, чем три ученика этого класса.

Решение. В году 12 месяцев. Обозначим их за «клетки», аучеников за «зайцев». Так как 27 > 12 • 2 + 1, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «зайцев», то есть найдется месяц, в котором дни рождения празднуют не менее 3 учеников.

Замечание. Задачу можно решить, применяя метод от про­тивного.

Задача №5.  16 учеников сидят за круглым столом, причем больше половины из них девушки. Докажите, что какие-то 2 девушки сидят напротив друг друга.

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

Задача №6.  Плоскость раскрашена в 2 цвета. Можно ли всегда най­ти 2 точки, расположенные на расстоянии 1 метра друг от дру­га, окрашенные в одинаковый цвет?

Решение. Так как цветов — 2, то надо рассмотреть фигуру, в которой точек больше 2. Лучше всего для этого подойдет равносторонний треугольник со стороной 1 метр. У него 3 вершины. Принимая вершины треугольника за «зайцев», а цвета за «клетки», имеем: 3 > 2. Тогда по принципу Дирихле найдутся 2 вершины треугольника, расположенные на рас­стоянии 1 метра друг от друга, окрашенные в один цвет.

Задача №7.  Каждая точка плоскости окрашена в один из двух цветов. Известно, что у любого правильного треугольника со стороной 1 имеются вершины обоих цветов.

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

б) Приведите пример раскраски плоскости, удовлетворяющей условию задачи.

Решение.

Возьмем отрезок АВ длиной 2 с разноцветными концами. Такой отрезок существует: в противном случае все точки окружности радиуса 2 с центром в произвольной точке О были бы окрашены в тот же цвет, что и точка О, а всевозможные окружности радиуса 2 с центром на окружности заполнили бы круг радиуса 4 с центром О, все точки которого были бы одного цвета, что невозможно. Пусть цвет точки С – середины отрезка АВ – совпадает с цветом точки А. Построим правильные треугольники ACDи ACEпо разные стороны от прямой АВ. По условию задачи точки Dи Е окрашены в тот же цвет, что и точка В, поэтому треугольник BDEбудет искомым.

б) Разобьем плоскость на горизонтальные полосы шириной , включающей верхние границы, но не включающей нижние границы, и раскрасим их так, чтобы соседние имели разный цвет.

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

Решение. 

Рассмотрим суммы

Если хотя бы одна из сумм делится на 100, то наша цель достигнута.

Допустим, что ни одно из чисел не делится на 100. Эти числа будем считать «зайцами». За клетки же примем числа 1, 2, …, 99. Сопоставим каждому числу остаток от деления его на 100. Поскольку числа на 100 не делятся, они будут давать остаток от 1 до 99, то есть каждый «заяц» попадет в какую-то «клетку». По принципу Дирихле найдутся два «зайца», попавшие в одну «клетку», то есть числа и (пусть для определенности ), дающие одинаковые остатки при делении на 100. Но тогда число делится на 100. Таким образом, сумма является искомой.

Задача №9. Числа и взаимно просты. Докажите, что найдется натуральное число , для которого число при делении на дает остаток 1.

Решение.Числа 1, 2, …, будем считать «зайцами». Если  - один из «зайцев», то число  не делится на (поскольку и взаимно просты и ), то есть  при делении на дает один из остатков 1, 2, …, . Допустим, что ни при каком 1, 2, …,  число при делении на  не дает остаток 1. Тогда возможными остатками являются лишь числа 2, …, . Эти числа будем считать «клетками» («зайцев» больше, чем «клеток»). По принципу Дирихле найдутся два «зайца», попавшие в одну «клетку», то есть среди чисел 1, 2, …, найдутся  такие два , что числа и при делении на дают одинаковые остатки (мы можем считать ), а поэтому число -= делится на . Так как и взаимно просты, то отсюда вытекает, что делится на . Но это невозможно, поскольку . Полученное противоречие показывает, что найдется натуральное число , для которого число при делении на дает остаток 1.

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

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

Решение.

Ясно, что расположение 7 звездочек, показанное на рисунке, удовлетворяет условию задачи. Если же звездочек 6 или меньше, то найдутся два столбца, в каждом из которых стоит не более одной звездочки (принцип Дирихле). Вычеркнем оставшиеся два столбца. После этого останется не больше двух звездочек, которые можно вычеркнуть вместе со строками, в которых они стоят.

Выводы.

Таким образом, применяя данный метод, надо:

1. определить, что удобно в задаче принять за «клетки», а что за «зайцев»;
2. получить «клетки». Чаще всего «клеток» меньше (боль­ше), чем «зайцев» на одну;
3. выбрать для решения требуемую формулировку принципа Дирихле.

Задачи для самостоятельного решения.

1. В лесу растет миллион ёлок. Известно, что на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся две ёлки с одинаковым количеством иголок.
2. В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начина­ются с одной буквы?
3. На дискотеку в студенческое общежитие, в котором 42 комнаты, пришли 36 гостей. Докажите, что найдется ком­ната, в которую не пришел ни один гость.
4. В мешке лежат 10 белых и 10 черных шаров. Они тща­тельно перемешаны и неразличимы на ощупь. Какое наи­меньшее число шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара: 1) одного цвета, 2) разного цвета, 3) белого цвета?

Верно ли, что из любых трех целых чисел можно выбрать два, сумма которых четна?

1. В классе 37 учеников. Докажите, что среди них найдут­ся 4 ученика, отмечающие день рождения в одном месяце.
2. В школе учатся 1200 учеников. Найдется ли день, в ко­торый отмечают свои дни рождения не меньше, чем 4 ученика данной школы?
3. В школе 33 класса, 1150 учеников. Найдется ли класс, в котором меньше 35 учеников?
4. В магазин привезли 26 ящиков с яблоками трёх сортов, причём в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?
5. В классе 29 учеников. Петя Иванов сделал в диктанте 13  ошибок, остальные ученики — меньше. Докажите, что в классе найдётся, по крайней мере, 3 ученика, сделавших оши­бок поровну.
6. В классе 26 учеников, из них более половины — маль­чики. Докажите, что какие-то 2 мальчика сидят за одним сто­лом. (В классе 13 столов).
7. На шахматной доске размером 8x8 Вася расставил 14  фигур. Докажите, что найдется квадрат размером 2x2, в котором не будет фигур. (Фигуры размещаются внутри клеток размером 1x1).
8. Дано 9 целых чисел. Докажите, что из них можно вы­брать 2, разность которых делится на 8.
9. Внутри правильного шестиугольника со стороной 1 см расположено 7 точек. Докажите, что расстояние между неко­торыми двумя точками меньше, чем 1 см.
10. В прямоугольнике 3x4 расположено 6 точек. Докажи­те, что среди них найдутся 2 точки, расстояние между кото­рыми не превосходит  .
11. В первенстве по хоккею участвует 5 команд. Каждые две из них должны сыграть между собой один матч. Доказать, что в любой момент соревнований имеются две команды, сыг­равшие одинаковое число матчей.
12. 30 команд участвует в первенстве по футболу. Каждые 2 команды должны сыграть между собой один матч. Докажи­те, что в любой момент состязаний имеются 2 команды, сыг­равшие к этому моменту одинаковое число матчей.
13. Несколько дуг окружности покрасили в красный цвет. Сумма длин окрашенных дуг меньше половины длины ок­ружности. Докажите, что существует диаметр, оба конца ко­торого не окрашены.
14. В классе 13 мальчиков и 6 девочек. Каждый день они в течение двух недель ходили в кино, причем не было двух та­ких дней, когда в кино ходило бы одинаковое количество де­тей. Докажите, что найдется день, когда в кино ходила, по крайней мере, одна девочка в компании не менее чем восьми мальчиков.
15. На далекой планете, имеющей форму шара, суша за­нимает больше половины поверхности планеты. Докажите, что можно прорыть туннель, проходящий через центр плане­ты, который соединит сушу с сушей.
16. Коля хочет записать на доске 55 различных двузнач­ных чисел так, чтобы среди них не было двух чисел, дающих в сумме 100. Сможет ли он это сделать?
17. В городе 15 школ. Доказать, что как бы ни распределя­ли между ними 90 компьютеров, обязательно найдутся две школы, получившие одинаковое количество компьютеров (возможно, ни одного).
18. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть решившие ровно одну задачу, решившие ровно две задачи и решившие ровно три задачи. Докажите, что среди них есть школьник, решивший не менее пяти задач.
19. 15 девочек собрали 100 орехов. Докажите, что какие-то две из них собрали одинаковое число орехов.
20. Какое наибольшее число шахматных королей можно поставить на шахматной доске, чтобы никакие два из них не били друг друга?
21. Докажите, что в любой компании из пяти человек двое имеют одинаковое число знакомых.
22. Докажите, что в любой компании найдутся 2 человека, у которых одинаковое число знакомых в этой компании (воз­можно, ни одного).
23. Можно ли увезти 50 камней весом 370, 372, 374, 376, ..., 466, 468 кг на семи трёхтонках?
24. Дано 70 натуральных различных чисел, каждое из ко­торых не превосходит 200. Доказать, что какие-то 2 из них отличаются на 4; 5 или 9.
25. Какое максимальное количество натуральных чисел от 1 до 50 можно выбрать так, чтобы среди них не было двух чи­сел, отличающихся ровно в два раза?
26. Даны 8 натуральных различных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.
27. Докажите, что в любой компании из 6 человек найдутся трое людей попарно знакомых, либо попарно незнакомых.
28. Имеется 11 натуральных различных чисел, не больше: 20. Докажите, что из них можно выбрать два числа, одно и которых делится на другое.
29. В квадрате со стороной 10 см находится 51 точка. Докажите, что найдутся три точки, принадлежавшие кругу с радиусом  см.
30. В кубе со стороной 1 м находится 2003 таракана. Докажите, что хотя бы трех из них можно поймать сферой радиуса 1/11 м.
31. За пять лет обучения в вузе студент сдал 31 экзамен причем в каждом году он сдавал экзаменов больше, чем в предыдущем. На пятом курсе экзаменов втрое больше, чем на первом. Сколько экзаменов на четвёртом курсе?

Ответы и указания к решению

1. Пусть ёлки — «зайцы», а число иголок на ёлках: 0, 1, 2, 3 ... 600000 — «клетки». «Клеток» будет 600001, а «зайцев» — 1000000. Здесь «зайцев» гораздо больше, чем «клеток». Тогда по принципу Дирихле в какой-то «клетке» будет находиться не менее двух «зайцев». Но если в одной «клетке» сидят два «зайца», то число иголок у этих ёлок будет одинаково.
2. Обозначим 35 учеников за «зайцев», а буквы за «клет­ки». В русском алфавите 33 буквы. Фамилии не могут начи­наться разве что на Ъ и Ь. Так как 35 > 31, то по принципу Ди­рихле найдется 2 ученика, у которых фамилия начинается с одной буквы.
3. Обозначив комнаты — «клетками», а гостей — «зайца­ми», имеем: 36 < 42. Тогда по принципу Дирихле найдется как минимум одна пустая «клетка», т.е. в какую-то комнату не придет ни одного гостя.
4. 1) Цвета шаров обозначим за «клетки» (их две), значит «зайцев» надо больше. Достанем 3 шара из мешка. Так как 3 > 2, то по принципу Дирихле найдется «клетка» (цвет шара), в которую попадут как минимум 2 «зайца» (шара). Значит, надо достать наименьшее число шаров три.
5. Так как подряд могут попадаться все время шары одно­го цвета, то наименьшее число шаров надо достать 11.
6. Наименьшее число шаров будет 12.
7. Так как числа бывают чётные или нечётные, а всего чи­сел — три, то, применяя принцип Дирихле, как минимум 2 из них будут оба чётные или оба нечётные. В первом и во втором случае сумма чисел будет чётной. Значит, верно.

1 способ.Пусть 37 учеников — «зайцы», а 12 месяцев — «клетки». Так как 37 > 12 · 3 + 1, то, применяя обобщенный принцип Дирихле, мы получаем, что найдется 4 ученика, родившиеся в один месяц.

2 способ.Если в каждый месяц родилось не более 3 уче­ников, то всего учеников будет не больше 36. А по условию их 37, значит, такого быть не может. Поэтому найдется 4 уче­ника, отмечающиеся день рождения в один месяц.

1. Обозначим 1200 учеников за «зайцев», а 366 дней за «клетки» (возьмем високосный год). Так как 1200 > 366-3 + 1, то найдется, как минимум, 4 ученика, отмечающие свой день рождения в один день.

Замечание.Можно применить метод от противного, ана­логично предыдущей задаче.

1. Допустим, что во всех классах не менее 35 учеников, то­гда во всей школе будет не менее чем 35 · 33 = 1155 (учени­ков), что противоречит условию задачи. Значит, в школе най­дется класс, в котором меньше, чем 35 учеников.
2. 26 ящиков — «кроликов» рассадим по трём «клеткам» —  сортам. Так как 26 = 3 · 8 + 2, то применим обобщенный принцип Дирихле для т = 3, к = 8 и получим, что в какой-то «клетке» — сорте не менее 9 ящиков.
3. Обозначив число ошибок: 0, 1, 2, ... 11, 12 за «клетки», а 28 учеников (без Пети) за «зайцев», получим: 28 > 13 · 2 + 1. Применяя обобщенный принцип Дирихле, получим, что не менее 3 учеников сделали ошибок поровну.
4. Обозначим мальчиков за «зайцев», а столы — за «клет­ки». Так как мальчиков больше половины, то есть больше 13 — числа столов, то по принципу Дирихле, найдется стол, за которым сидят не менее 2 мальчиков. А так как больше 2 мальчиков за стол не помещается, то это означает, что най­дется стол, за которым сидят 2 мальчика.
5. Разобьем квадрат 8x8 следующим образом на клетки:

Тогда получаем 16 «клеток» и 14 «зайцев» — фигур. Так как 16 < 14, то найдется как минимум одна клетка, которая будет пустой.

1. Обозначим за «клетки» — остатки от деления на 8: 0, 1, 2, 3, 4, 5, 6, 7. «Клеток» будет 8. За «зайцев» обозначим 9 целых чисел. Так как 9 > 8, то 2 целых числа будут иметь одинаковый остаток при делении на 8, а поэтому их разность будет делиться на 8.

1. Примем 7 точек за «зайцев». Построим 6 «клеток». Для этого разобьем правильный шестиугольник на 6 правильных треугольников, как на рисунке. Так как 7 > 6, то по принципу Дирихле хотя бы в один треугольник попадут не менее 2 точек. А расстояние между любыми 2 точками в правильном треугольнике со стороной 1 см, меньше 1 см.
2. Разобьем прямоугольник на 5 фигур, как на рисунке:

Обозначим 6 точек за «зайцев», а 5 фигур за «клетки».
Так как 6 > 5, то минимум 2 точки попадут в одну фигуру. А так как расстояние между любыми 2 точками вzкаждой фигуре не превосходит , то этим мы доказали, что такие точки найдутся.

1. Рассмотрим 2 случая.
2. Все команды сыграли хотя бы один матч. Тогда число сыгранных матчей каждой командой могло быть 1, 2, 3 или 4. Обозначим эти 4 варианта за «клетки»; тогда 5 команд будут «зайцами». Так как 5 > 4, то по принципу Дирихле найдется не менее 2 команд, сыгравших одинаковое число матчей.
3. Пусть есть команда, не игравшая матчей. Тогда число сыгранных матчей может быть 0, 1, 2 или 3. Так как команд 5, а вариантов опять 4, то найдутся как минимум 2 команды, которые сыграли к данному моменту одинаковое число мат­чей (возможно, ни одного).
4. Рассмотрим 2 случая.
5. Пусть все команды к данному моменту времени сыгра­ли хотя бы один матч. Тогда число сыгранных матчей каждой командой могло быть 1, 2, 3 ... 28, 29. Обозначим эти 29 вари­анта за «клетки»; тогда 30 команд будут «зайцами». Так как 30 > 29, то по принципу Дирихле найдется не менее 2 команд, сыгравших одинаковое число матчей.
6. Пусть есть команда, не игравшая матчей. Тогда число сыгранных матчей может быть 0, 1, 2 ... 28. Так как команд 30, а вариантов снова 29, то найдутся как минимум 2 команды, которые сыграли к этому моменту одинаковое число матчей (возможно, ни одного).
7. Покрасим в синий цвет дуги, симметричные красным относительно центра окружности. Так как сумма длин синих дуг равна сумме длин красных, то общая длина окрашенных дуг меньше длины окружности. Значит, найдутся неокрашен­ная точка с такой же симметричной неокрашенной ей точкой. Диаметр, проходящий через них, и будет искомым.
8. Рассмотрим день, в который кино посетило больше всего народу. Так как дней в 2 неделях 14, то посетило в этот день кино не менее 14 учеников. Так как мальчиков в классе 13, то, как минимум одна, есть девочка среди 14 учеников. Но девочек в классе 6, поэтому мальчиков будет не менее 8.

Замечание:В данной задаче принцип Дирихле применялся неоднократно.

1. Покрасим сушу на планете в зеленый цвет, а поверх­ность планеты, симметричную суше — в синий цвет. Так как суша занимает больше половины поверхности планеты, то найдется точка на планете, покрашенная в оба цвета. На про­тивоположной стороне планеты также будет точка, покрашен­ная в два цвета. Через эти две точки, которые находятся на суше, и надо рыть туннель.
2. Двузначных чисел всего 90. Нет среди них «пары» (в смысле получения 100 в сумме) у чисел 50, 91, 92, ..., 99, т.е. десяти чисел. Оставшиеся 80 чисел образуют 40 «пар». Дан­ные 40 «пар» и 10 чисел без «пары» можно обозначить за «клетки». Тогда «зайцами» будут 55 чисел. Так 55 > 50, то найдется минимум 2 числа, которые или совпадают или в сумме дают 100. Значит, Петя не сможет осуществить свой замысел.
3. Найдём сумму чисел от 0 до 14: (0 + 14):2-15 = 105.

В этом случае все 15 школ получат разное число компьютеров. А так как 90 < 105, то найдутся обязательно две школы, полу­чившие одинаковое количество компьютеров (возможно, ни одного).

1. Так как есть школьники, решившие ровно одну, ровно две и ровно три задачи, то остальные 7 школьников решили 35 - 6 = 29 задач. Так как 29  4 · 7 + 1, то найдется школьник, решивший не менее 5 задач.
2. Пусть все девочки собрали разное число орехов: 1, 2, 3 ... 15. Так как сумма числа орехов

(1+15):2- 15=120  больше 100, то какие-то две девочки собрали одинаковое чис­ло орехов.

1. В каждой клетке шахматной доски размером 2x2 можно поставить лишь одного короля. Так как всего таких клеток — 64 : 4 = 16, то поставить можно 16 королей.
2. Построим 5 «клеток»: № 0, № 1, № 2, № 3, № 4. Пусть номер «клетки» равняется числу знакомых у «содержащихся» в ней людей. Возможны 2 случая: есть человек, у которого нет знакомых, или такого человека нет.

В первом случае в «клет­ке» № 4 никого нет (иначе «сидящие» в «клетке» № 4 и в «клетке» № 0 были бы знакомы между собой) и 5 человек бу­дут размещены по 4 «клеткам».

Во втором случае тоже 5 человек «размещены» по 4 «клет­кам» (так как «клетка» № 0 пуста). Так как 5 > 4, то, по край­ней мере, двое людей находятся в одной «клетке», т.е. имеют одинаковое число знакомых.

1. Решение аналогично предыдущей задаче, но «клетки» будут иметь номера: 0, 1, .. п - 1, п.
2. Если обозначить 50 камней за «зайцев», а 7 трехтонок за «кроликов», то по принципу Дирихле на одну из машин придется погрузить не менее 8 камней. Но масса даже самых легких 8 камней будет 370 + 372 + ... + 384 = 3016 > 3000. Значит, увезти 50 камней на 7 трехтонках не удастся.
3. Рассмотрим новые 70 чисел, которые получаются из исходных чисел прибавлением к каждому по 4. Если пересе­чение первоначального и вновь полученного множества со­держит хотя бы один элемент, то в исходном множестве най­дется пара чисел с разностью 4. Допустим, что такой пары нет. Тогда рассмотрим еще 70 чисел, которые получаются из вто­рого набора прибавлением к каждому из чисел по 5. Если пе­ресечение третьего множества с первым или вторым не явля­ется пустым, то найдется в первом множестве пара чисел, отличающихся друг от друга на 5 или 9. Если же пересечение будет пустым множеством в обоих случаях, то мы имеем 210 различных чисел, каждое из которых не превышает 200 + 4 + 5 = 209, что невозможно. Значит, среди указанных чисел обязательно найдутся два, отличающиеся на 4, или на 5, или на 9.
4. Разобьем все числа на следующие 33 группы («клет­ки»): {1, 2}, {3, 6}, {5, 10}, ..., {25, 50}, {27}, {29}, ..., {49} (всего 25 групп), {4, 8}, {12, 24}, {20, 40}, {28}, {36}, {44} (таких групп 6), {16, 32}, {48}. Всего получилось 33 группы. Из каждой группы можно брать не более одного элемента, поэтому чисел будет не более 33. Взяв по первому элементу из каждой группы, мы получим искомый набор: 1, 3,... 25, 27,... 49, 4, 12, 20, 28, 36, 44, 16, 48. Так как в разложение всех этих чисел на простые множители двойка входит в чётной степени (частное двух таких чисел либо нечётно, либо делится на 4 и не может быть равно 2).

Замечание.Есть и другие способы решения.

1. Разностями 2 натуральных чисел, различных и не боль­ших 15, могут быть числа 1, 2,... 14. Их можно обозначить за «клетки». Всего разностей может быть 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28. Это «зайцы». Имеем 28 «зайцев» и 14 «клеток». Но в клетку с разностью 14 можно «поместить» только одну разность: 14 = 15-1.

Таким образом, в оставшиеся 13 «клеток» размещаем не менее 27 «зайцев». Применяя обобщенный принцип Дирихле, полу­чаем, что найдется «клетка», в которой сидят не менее 3 «зай­цев», т.е. найдутся минимум три одинаковые попарные разно­сти.

1. Пусть эти шестеро: А, В, С, Д Е, М. А находится в од­ном из двух отношений: «знаком» или «не знаком» хотя бы с тремя из них. Пусть это будут В, С, Д. Если какие-то 2 из них находятся в том же отношении друг с другом, то они вместе с А образуют искомую тройку. В противном случае искомая тройка В, С, Д.

1. Выберем из 11 чисел все чётные числа и разделим ка­ждое из них на максимальную степень двойки (например: 12 = 3 · 4), тогда в частном получим нечётное число. Обозна­чим эти частные и остальные нечётные числа за «зайцев» (их 11). Но всего нечётных чисел, меньших 20, будет 10. Тогда «клеток» будет 10. Так как 11 > 10, то найдется 2 одинаковых нечётных числа. Так как сами исходные нечётные числа раз­личные, то совпадет нечётное число с нечётным частным, т.е. найдутся 2 числа, одно из которых делится на другое.
2. Разобьём квадрат на 25 квадратиков со стороной 2 см, это будут «клетки». А 51 точка — «зайцы». Так как 51 > 2 · 25 + + 1, то по обобщенному принципу Дирихле найдутся как ми­нимум 3 точки, попавшие в один квадрат. Найдём радиус кру­га, описанного вокруг квадрата со стороной 2 см: см. Так как  , то найдутся три точки, которые будут при­надлежать кругу радиуса  см.
3. Распилим куб на 1000 кубиков со стороной  м. То­гда найдётся кубик, в котором как минимум сидят 3 таракана. Вычислим радиус сферы, описанной вокруг такого кубика: м. Так как , то найдется сфера радиуса  м, которая будет содержать кубик с 3 тараканами.
4. Пусть на первом курсе студент сдал х экзаменов. Тогда на втором курсе он сдал не меньше, чем ( + 1) экзаменов, на третьем — не меньше ( + 2) экзаменов, на четвёртом — не меньше ( + 3) экзаменов. С другой стороны, на пятом курсе он сдал Зх экзаменов, значит на четвёртом не больше Зх - 1, на третьем — не больше Зх - 2, а на втором — не больше З - 3. Тогда получаем систему неравенств: 7 + 6<31<13-6, которая имеет единственное целое решение х = 3. Тогда на 5 курсе студент сдал 9 экзаменов, следовательно, на четвёртом — не больше 8. Если бы он сдал на четвёртом курсе 7 экзаме­нов, то всего бы он сдал не больше 3+4+6+7+7+9=30 экзаменов, что противоречит условию. Значит, на четвёртом курсе, он сдал 8 экзаменов.

Инварианты и их применение
при решении задач

Инвариантомнекоторого преобразования называется ве­личина или свойство, не изменяющееся при этом преобразо­вании. В качестве инварианта чаще всего рассматриваются чётность (нечётность) и остаток от деления, хотя встречаются и другие стандартные инварианты: перестановки; раскраски и т.п. Причем, применение чётности — одна из наиболее часто встречающихся идей при решении олимпиадных задач.

Сформулируем наиболее важные утверждения, на которых основано применение этой идеи:

1. чётность суммы нескольких целых чисел совпадает с чёт­ностью количества нечётных слагаемых;
2. знак произведения нескольких (отличных от нуля) чисел определяется  чётностью количества отрицательных со­множителей.

Примеры задач, решаемых данным методом.

Задача №1. На доске записано 15 чисел: 8 нулей и 7 единиц. Вам предлагается 14 раз подряд выполнить такую операцию: за­черкнуть любые два числа и если они одинаковые, то допиши­те к оставшимся числам нуль, а если разные, то единицу. Ка­кое число останется на доске?

Решение.

Сумма 15 исходных чисел равна 7. 7 — число нечётное. Рассмотрим, какая сумма чисел будет получаться после выполнения операции. Если вычеркнем 2 нуля, то после дописывания нуля на доске будет 7 нулей и 7 единиц. Сумма этих 14 чисел будет нечётная. Если вычеркнем 2 единицы, то на доске останется после дописывания нуля 9 нулей и 5 еди­ниц. Сумма данных 14 чисел будет нечётной. Наконец, вычер­кивая нуль и единицу и приписывая единицу, мы получим на доске 7 нулей и 7 единиц, сумма которых снова является не­чётным числом. Таким образом, мы замечаем, что после вы­полнения данной операции получается на 1 число на доске меньше, причём сумма оставшихся чисел всё время остаётся нечётной. Так как 1 — нечётное число, а 0 — чётное, то на доске после выполнения 14 раз указанной операции получает­ся нечётное число, то есть 1.

Задача №2. На плоскости расположено 13 шестерёнок, соединённых по цепочке. Могут ли все шестерёнки вращаться одновремен­но? А если шестерёнок 14?

Решение.

Пусть первая шестерёнка вращается по часовой стрелке, тогда вторая — против часовой стрелки, третья — по часовой стрелке и т.д. Получим, что двенадцатая будет вра­щаться против часовой стрелки, а тринадцатая - по часовой стрелке. Значит, первая должна вращаться против часовой стрелки, что противоречит тому, что она вращается по часо­вой стрелке. Поэтому, все 13 шестерёнок вращаться одновре­менно не могут. А вот 14 уже могут.

Вывод. Часто при решении подобного рода задач важно найти чередующиеся объекты.

Задача №3.Все костяшки домино выложены в цепь. На одном кон­це цепи оказалось 3 очка. Сколько очков на другом конце?

Решение.

Всего костяшек с тройкой на конце 7: 0-3, 1-3, 2-3, 3-3, 4-3, 5-3, 6-3. Костяшка 3-3 имеет «тройку» на обоих концах. Без нее остается 6 костяшек. Так как при игре в доми­но в цепи они должны располагаться парами, то на другом конце цепи будет 3 очка.

Вывод. При решении аналогичных задач полезно иногда объекты разбивать на пары.

Задача №4.Можно ли разменять купюру достоинством 50 рублей с помощью 15 монет достоинством 1 и 5 рублей?

Решение.

Так как сумма 15 нечётных чисел является чис­лом нечётным, а 50 — число чётное, то разменять 50 рублей на 15 монет по 1 и 5 рублей нельзя.

Задача №5.Хулиганы Вася и Петя порвали школьную стенгазету, в которой была заметка об их плохой учёбе. Причём Вася рвал каждый кусок на 5 частей, а Петя на 9. Заместитель директора школы, заметив такое безобразие, потребовала собрать обрыв­ки стенгазеты. Ребята нашли 1999 обрывков. Все ли обрывки были найдены и почему?

Решение.

Рассмотрим, какое число обрывков могло полу­читься. Если Вася первоначально порвал стенгазету на 5 кус­ков, а затем один из кусков снова на 5, то всего их получается 9. Если теперь Вася будет дальше рвать некоторые куски на 5, а Петя на 9, то число кусков может получаться 5, 9, 13, 17, 21 и т. д. Можно заметить, что общее число кусков можно запи­сать как 4n+ 1. Так как 1999 = 499 • 4 + 3, то ученики собрали не все обрывки стенгазеты.

Вывод. В данной задаче в качестве инварианта выступил остаток от деления на 4.

Задача №6.   Квадрат 5x5 заполнен числами так, что произведение чисел в каждой строке отрицательно. Доказать, что найдется столбец, в котором произведение чисел также отрицательно.

Решение.

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

Вывод. В задаче использовалась идея — нахождение про­изведения чисел.

Задача №7.  В таблице    расставлены знаки «+» и «-» так, как показано на рисунке. Разрешается изменить знак на противоположный одновременно во всех клетках, расположенных одновременно в одной строке, в одном столбце или вдоль прямой, параллельной какой-нибудь из диагоналей (в частности, в любой угловой клетке). Можно ли с помощью таких операций получить таблицу, не содержащую ни одного минуса?

Решение.

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

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

Задача №8. На доске написано несколько нулей, единиц и двоек. Разрешается стереть две неравные цифры и вместо них написать цифру, отличную от стертых (2 вместо 0 и 1, 1 вместо 0 и 2, 0 вместо 1 и 2). Докажите, что если в результате нескольких таких операций на доске останется одна-единственная цифра, то она не зависит от порядка, в котором производились стирания. 

Решение.

Обозначим через х₀, х₁, х₂ число нулей, единиц и двоек соответственно. Выполнив один раз  разрешенную операцию, мы изменим каждое из этих чисел на 1 и, следовательно, изменим четность всех трех чисел. Когда на доске останется одна цифра, два из этих чисел х₀, х₁, х₂ становятся равными нулю, а третье – единице. Значит, с самого начала два из этих чисел имеют одну четность, а третье – другую. Поэтому независимо от того, в каком порядке производятся стирания, в конце единице может равняться лишь одно из чисел х₀, х₁, х₂, которое с самого начала имело не туже четность, что два других.

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

Решение.

Заметим, что и . То есть значения многочленов и  в точке делятся на 3. Однако если для произвольных многочленов и их значения в точке делятся на 3, то и значения , , также делятся на 3. Однако  не делится на 3, то многочлен на доске появиться не может.

Задача №10. Квадратный трехчлен разрешается заменить на один из трехчленов или . Можно ли с помощью таких операций из квадратного трехчлена получить трехчлен

Решение.

Пусть  - квадратный трехчлен ( с дискриминантом ). После первой операции трехчлен меняется на трехчлен с дискриминантом , а после второй операции – на трехчлен с дискриминантом . Итак, при выполнении разрешенных операций дискриминант сохраняется. Но у трехчлена дискриминант равен 4, а у трехчлена он равен 64. Следовательно из квадратного трехчлена получить трехчленнельзя.

Задачи для самостоятельного решения

1. Конь вышел с поля al шахматной доски и через не­сколько ходов вернулся на него. Докажите, что он сделал чёт­ное число ходов.
2. Можно ли доску размером 5 x 5 заполнить доминошками размером 1 x 2?
3. 2003 человека выстроились в шеренгу. Всегда ли можно их расставить по росту, если за один ход разрешается пере­ставлять только двух людей, стоящих через одного?
4. В древней рукописи приведено описание города, распо­ложенного на 8 островах. Острова соединены между собой и с материком мостами. На материк выходят 5 мостов; на 4 ост­ровах берут начало по 4 моста, на 3 островах берут начало по 3 моста и на один остров можно пройти только по одному мосту. Может ли быть такое расположение мостов?
5. 16 корзин расположили по кругу. Можно ли в них раз­ложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?
6. Можно ли выпуклый девятиугольник разрезать на па­раллелограммы?
7. На столе стоят 7 стаканов - все вверх дном. Разрешает­ся за один раз перевернуть любые 4 стакана. Можно ли за не­сколько раз добиться того, чтобы все стаканы стояли правиль­но, то есть вниз дном?
8. Сумма 2002 натуральных чисел — число нечётное. Ка­ким числом: чётным или нечётным является произведение этих чисел?
9. На доске написаны числа 1, 2, 3, ... 1997, 1998, 1999, 2000, 2001. Разрешается стереть с доски любые 2 числа и вме­сто них записать модуль их разности. В конце концов, на дос­ке останется одно число. Может ли оно равняться нулю?
10. На доске написано в строку 2003 целых числа. Дока­зать, что из них можно стереть одно число так, что сумма ос­тавшихся чисел будет чётной. Верно ли это для 2002 чисел?
11. В каждую клетку квадратной таблицы размером 25 x 25 вписано произвольно одно из чисел: +1 или -1. Под каждым из столбцов записывается произведение всех чисел данного столбца, а справа от каждой строки — произведение всех чи­сел данной строки. Может ли сумма всех 50 произведений быть равной нулю?
12. На доске написано 8 плюсов и 13 минусов. Разрешает­ся стирать любые два знака и написать вместо них плюс, если они одинаковы, и минус в противном случае. Какой знак оста­нется после выполнения 20 таких операций?
13. Учитель написал на листке бумаги число 10. 25 учени­ков передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу — как хочет. Может ли в ре­зультате получиться число 0?
14. В некотором государстве первоначально было 10 бан­ков. С момента перестройки общества все захотели быть бан­кирами. Но, по закону, открыть банк можно только путём деления уже существующего банка на 4 новых банка. Через 2 года министр финансов сообщил президенту, что в стране действует уже 2001 банк, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?
15. Можно ли по правилам игры в домино выложить все 28 костей в одну цепочку так, чтобы сумма на её концах была нечётной? (Дубли кладём вдоль цепи, конечной считаем вто­рую половину кости.)
16. Написанное на доске четырехзначное число можно заменить на другое, прибавив к двум его соседним цифрам по единице, если ни одна из его цифр не равна 9, либо, вычтя из соседних двух цифр по единице, если ни одна из них не равна 0. Моно ли с помощью таких операций из числа 1234 получить число 2002?
17. В таблице т х п расставлены числа так, что сумма чисел в любой строке или столбце равна 1. Докажите, что т = п.
18. По кругу расставлено 7 чисел: 4 единицы и 3 нуля. Ка­ждую секунду над числами проделывают следующую опера­цию: между соседними числами ставят нуль, если они различ­ны, и единицу, если они равны; после этого старые числа сти­рают. Могут ли через некоторое время все числа стать одина­ковыми?
19. Числа 0, 1, 2, ..., 9 записаны по кругу. За один ход раз­решается прибавить к двум соседним числам одно и то же це­лое число. Можно ли за несколько ходов получить десять ну­лей?
20. В вершинах куба записаны числа 2, 0, 0, 3, 1, 9, 5, 7. За один ход разрешается прибавить к числам, стоящим на концах одного ребра, одно и то же целое число. Можно ли за несколь­ко ходов получить нули во всех вершинах?
21. У Ивана-царевича есть два волшебных меча: с помо­щью первого он может отрубить у Змея Горыныча 21 голову, а с помощью второго - 4 головы, но тогда у Змея Горыныча от­растает 1999 голов. Может ли Иван отрубить Змею Горынычу все головы, если в самом начале у него было 30 голов? (При­мечание: если у Змея Горыныча осталось голов 3 или 2 или 1, то никаким мечом рубить нельзя.)
22. На плоскости лежат три шайбы. Хоккеист бьет по од­ной из них так, чтобы она прошла между двумя другими и ос­тановилась в некоторой точке. Можно ли все шайбы вернуть на свои места после 2003 ударов?
23. Страницы книги пронумерованы подряд с первой до последней страницы. Хулиган Вася вырвал из разных мест книги 17 листов и сложил номера всех 34 вырванных страниц. У него получилось число 2002. Правильно ли Вася сосчитал?
24. 101 лошадь разместили в 15 конюшнях. Почему хотя бы в одной конюшне будет обязательно нечётное число лоша­дей?
25. 100 фишек стоят в ряд. Любые две фишки, располо­женные через одну, можно менять местами. Удастся ли распо­ложить фишки в обратном порядке?
26. На чудо-дереве садовник вырастил 45 бананов и 50 апельсинов. Каждый день он срывает 2 плода и тут же на де­реве вырастает новый. Причем, если он срывает 2 одинаковых плода, то вырастает апельсин, а если — 2 разных, то выраста­ет банан. Каким окажется последний плод на дереве?
27. Круг разбит на 10 секторов, в каждом из которых стоит по одной фишке. Одним ходом разрешается любые 2 фишки передвинуть в соседние секторы. Удастся ли через несколько ходов все фишки собрать в одном секторе?
28. В классе у каждого ученика не более трех врагов. До­кажите, что класс можно разбить на 2 группы так, что у каж­дого ученика в одной с ним группе будет не более одного вра­га, (Считается, что если А — враг В, то и В — враг А).
29. Дана некоторая тройка чисел. С любыми двумя разрешается проделывать следующее: если эти числа равны а и в, то их можно заменить на и . Можно ли с помощью таких операций получить тройку из тройки ?

Ответы и указания к решению

1.При каждом своем ходе конь меняет цвет поля, поэтому при возвращении обратно он должен сделать чётное число ходов.

2.Нет, так общее число клеток — 25 не делится на 2

3.  Не всегда. При перестановке сохраняется чётность но­мера места. Поэтому, если самый высокий человек, например, стоит вторым, то он никогда не станет первым. Здесь число 2003 роли не играет.

4.Найдём число концов у всех мостов: 5 + 4 · 4 + 3 · 3 + 1 = 31.

31 — является числом нечётным. Так как число концов у всех мостов должно быть чётным, то такого расположения мостов быть не может.

5.  Если число арбузов в соседних корзинах отличается на 1, то характер чётности числа арбузов в этих корзинах будет разным. Тогда чётность числа арбузов в корзинах бу­дет чередоваться, поэтому в половине корзин будет чётное число арбузов, а в половине нечётное. Тогда общее число арбузов в 8 корзинах с чётным числом арбузов и в 8 корзи­нах с нечётным числом арбузов будет чётным. По условию же всего арбузов — 55, а это нечётное число. Значит, раз­ложить нельзя.

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

7.  Нет, так как в любом случае число перевёрнутых вверх дном стаканов будет числом нечётным.

8.  Так как сумма 2002 чисел — число нечётное, то число нечётных слагаемых — нечётно. Тогда среди 2002 чисел есть хотя бы одно чётное число. А, значит, произведение 2002 чи­сел будет чётным числом.

9.  Сумма всех записанных на доске чисел будет нечётной. При стирании 2 чисел могут быть следующие 3 варианта:

а) стираются 2 чётные числа, тогда модуль разности будет четным числом, а новая сумма будет числом нечётным;

б) стираются 2 нечётные числа, тогда модуль разности бу­дет чётным числом, а новая сумма будет числом нечётным;

в)  стираются 1 чётное и 1 нечётное число, тогда модуль разности будет нечётным числом, а новая сумма будет снова числом нечётным.

Таким образом, в любом случае на доске останется нечёт­ное число. Так как нуль — число чётное, то оставшееся число нулем быть не может.

10.Рассмотрим 3 случая.

а) Среди 2003 целых чисел есть чётные и нечётные числа. Если количество нечётных чисел нечётно, то стираем любое из них. Если количество нечётных чисел четно, то из 2003 це­лых чисел хотя бы одно чётное. Его и стираем.

б) Пусть все 2003 числа — нечётные. Тогда стираем любое из них.

в) Пусть все 2003 числа — чётные. В этом случае стираем любое из них.

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

11.Перемножая все 50 произведений, мы получим 1, так как в каждое произведение любое из чисел, вписанных в клет­ки таблицы, войдёт 2 раза (один раз в произведение по стро­кам, один раз - по столбцам). Тогда в число 50 сомножителей будет входить чётное число произведений с «-1» , а поэтому сумма чётного числа произведений с «1» и чётного числа про­изведений с

«-1» не будет равна 0. (25 — число нечётное, зна­чит, одинакового числа слагаемых не будет).

12.  Заменяя все плюсы нулями, а минусы — единицами, заметим, что сумма двух стираемых чисел имеет тот же харак­тер чётности, что и число, записываемое вместо них. Так как сумма всех чисел была нечётной (13), то и последнее остав­шееся число будет нечётным, то есть единицей, и, значит, на доске останется минус.

13.  От прибавления или вычитания единицы меняется ха­рактер чётности числа. Поэтому, если 25 раз менять характер чётности числа 10, то в результате получится нечётное число. Следовательно, число 0 получиться не может.

14.Заметим, что в результате превращения одного старого банка в четыре новых общее число банков увеличивается на 3. Таким образом, в любой момент времени число банков будет равно 10 + Зn. Первоначально остаток от деления количества банков на 3 был равен 1, а 2001 при делении на 3 даёт остаток 0. Значит, образоваться ровно 2001 банков в стране не могло.

15.  В наборе домино клеток-половинок кости с одинако­вым количеством очков 8 штук, а в цепи они стоят подряд по 2 или 4. Значит, на концах может оказаться только разорван­ная пара. Поэтому сумма очков на концах будет чётной. Зна­чит, выложить цепь так, что сумма очков на концах была не­чётной, нельзя.

16.Пусть на доске написано число . Тогда рассматриваемые операции не изменяют число М = (d+b)– (a+ c), так как они увеличивают (уменьшают) на единицу одно число из первой скобки, и одно число из второй скобки. Для числа 1234 М₁ = (4+2) – (1+3) = 2, а для числа 2002 М₂= (2+0) – (2+0) = 0. Поэтому требуемое невозможно.

17.  Сумма чисел в таблице не зависит от способа ее под­счёта. С одной стороны, это количество строк, умноженное на 1, с другой — количество столбцов, умноженное на 1. То есть, т = п. Здесь инвариант — сумма чисел в таблице, а преобра­зование — нахождение суммы этих чисел.

18. Комбинация из семи единиц раньше, чем семь нулей, получиться не может, так как для появления семи единиц пре­дыдущие цифры должны быть одинаковыми — все нули или все единицы. Если же получилось семь нулей, то на предыду­щей стадии нули и единицы должны были чередоваться, что невозможно, так как их разное количество.

19.Сумма чисел, записанных по кругу, равна 45. Прибав­ляя 2 одинаковых целых числа к соседним числам, мы харак­тер чётности не меняем: сумма по-прежнему остается нечёт­ной. Так как сумма 10 нулей — нуль — число чётное, то ука­занными преобразованиями получить 10 нулей нельзя.

20.  Так как сумма данных чисел: число 27 — нечётное, а при прибавлении двух одинаковых целых чисел чётность суммы не меняется, то получить все нули во всех вершинах не получится (сумма восьми нулей — число чётное).

21.Змей Горыныч теряет либо 21 голову, либо приобрета­ет 1995 голов. Оба эти числа делятся нацело на 7, а в начале поединка остаток был 2. В случае же отсутствия голов у Змея Горыныча, остаток был бы 0. Значит, отрубить все головы Змею Горынычу Иван-царевич не сможет.

22.После каждого удара меняется ориентация обхода шайб А, В и С (по ходу часовой стрелки — против хода часо­вой стрелки). Инвариантом будет сохранение ориентации по­сле чётного числа ударов. Значит, после 2003 ударов шайбы не удастся вернуть на свои места.

23.  На каждом из 17 листов сумма номеров двух страниц число нечётное, так как на одной странице номер чётный, а на другой — нечётный. Тогда сумма 17 нечётных чисел будет нечётной. Так как 2002 — число чётное, то Вася ошибся при подсчёте.

24.Докажем задачу методом от противного. Пусть в каж­дой конюшне находится чётное число лошадей, тогда сумма чётных чисел — число чётное. А по условию всего лошадей 101 — число нечётное. Таким образом, получили противоре­чие. Значит, хотя бы в одной конюшне будет нечётное число лошадей.

25.Так как при перестановке фишек чётность места фиш­ки сохраняется, то первую фишку никогда не сделать послед­ней (1 — число нечётное, а 100 — число чётное)

26.Рассмотрим несколько случаев:

1)  Садовник сорвал 2 апельсина, тогда вырастает 1 апель­син и на дереве будет 45 бананов и 49 апельсинов.

2)  Садовник сорвал 2 банана, в этом случае вырастает 1 апельсин и на дереве будет 43 банана и 51 апельсин.

3)  Если же садовник срывает 2 разных плода: апельсин и банан, то на дереве вырастает банан и всего плодов будет: 45 бананов и 49 апельсинов.

Итак, можно заметить, что ниже и в каждом из трёх случа­ев неизменным остается одно, а именно: количество бананов — нечётное число. Значит, инвариантом будет нечётность числа бананов на дереве, а поэтому последним плодом ока­жется банан.

27.  Занумеруем сектора последовательно числами 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и присвоим каждой фишке номер сектора, в котором она находится. При передвижении какой-либо фишки в соседний сектор номер фишки меняется на единицу. Поэто­му чётность суммы номеров всех фишек при любых передви­жениях двух фишек не меняется. В первоначальном положе­нии сумма всех номеров фишек была равна 1 + 2 +...  + 10 = 55 (нечетное число). Тогда как в случае, если все фиш­ки удалось собрать в одном секторе, то сумма номеров была бы чётной. Значит, собрать фишки в одном секторе не удастся.

28.  Разобьем произвольным образом класс на 2 группы. Если в этом случае получилось, что в каждой группе у каж­дого ученика не более одного врага, то требование задачи выполнено. В противном случае, рассмотрим того ученика, пусть это будет А, у которого в одной с ним группе не менее 2  врагов. Значит, в другой группе у А будет не более одного врага. Переведём ученика А в другую группу (где у него вра­гов не более одного). Поступая аналогично так с каждым из учеников, у которого в одной с ним группе окажется 2 или 3  врага, мы, в конце концов, придём к искомому разбиению класса.

29. Нет. Так как при каждой операции сохраняется сумма квадратов чисел.

Полуинварианты.

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

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

Решение.

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

Но может ли сумма всех чисел в таблице увеличиваться при таких операциях бесконечно много раз?

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

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

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

Решение.

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

В противном случае рассмотрим два пересекающихся перпендикуляра АА₁ и ВВ₁, опущенные из точек А и В на прямые mи n  соответственно. Пусть Р – точка их пересечения. Заменим теперь перпендикуляры АА₁ и ВВ₁ перпендикулярами АА₂ и ВВ₂, на прямые nи mсоответственно. Докажем, что при этой замене сумма длин перпендикуляров уменьшится. В самом деле, и ; складывая эти неравенства, мы получаем .

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

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

С этой точки зрения вторая задача труднее первой, так как в ней нам пришлось придумать не только искомую величину, за изменением которой мы должны проследить, но и саму опера­цию.

Кроме того, вторая задача - прекрасный пример того, как легко можно пойти по ложному следу: новые перпендикуляры АА₂и ВВ₂не пересекаются, и поэтому кажется удобным следить за количеством точек пересечении наших nперпендикуляров, которое, на первый взгляд, всегда уменьшается при описанной операции. Однако это не так (постройте соответствующий при­мер).

Научиться придумывать нужную пару "операция - величина" далеко не просто. Здесь требуются опыт и интуиция.

Задача 3.  Докажите, что любые 2п точек на плоскости являются концами n непересекающихся отрезков.

Решение.

Проведем n отрезков с концами в данных точках произволь­ным образом. Если никакие два из них не пересекаются, то требование задачи выполнено. В противном случае рассмотримпару пересекающихся отрезков АВ иCD (рис.2). В качестве искомой операции естественно рассмотреть замену пересекающихся отрезков АВ и CD на непересекающиеся отрезки АС и BD.

Осталось найти полуинвариант - величину, которая при этой операции ведет себя монотонно. Так как сумма длин диагоналей АВ и CD выпуклого четырехугольника АСВD больше, чем сумма длин противоположных сторон АС и ВD, в качестве полуинварианта можно взять сумму длин всех n отрезков. Ясно, что эта сумма может принимать лишь конечное число значений. Рассуждая так же, как в предыдущей задаче, в конце концов получаем набор из nотрезков с минимальной суммой длин. Нетрудно понять, что в нем никакие два отрезка не пересекаются.

В задаче 3, по сути дела, вначале не было ни операции, ни полуинварианта. Однако после того, как мы подобрали опера­цию, выбор полуинварианта не представлял труда.

Задача 4.По окружности расставлены n чисел. Если подряд стоят числа а, b, с и dи при этом (а - d)(b- с) >0, то числа b и с разрешается поменять местами. Докажите, что через несколько шагов нам не удастся произвести ни одной такой перестановки.

Решение.

Здесь операция замены чисел задана. Несмотря на то, что она затрагивает лишь два числа, удобно воспринимать эту операцию на всем наборе чисел, считая, что все остальные числа операция оставляет неизменными: ведь в соответствии с нашей «филосо­фией решения» необходимо подобрать некоторую величину, зависящую от всего набора чисел.

Итак, пусть подряд идущие числа а, b, с и dтаковы, что (а - d)(b - с) > 0, т.е.

 ab + сd > ас +bd. При выполнении нашей операции мы перешли от четверки а, b, с, d  к четверке а, с, b, d, причем мы видим, что сумма произведений соседних чисел изменилась:

аb + bc + сd > aс+ cb + bd.

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

Задача 5.С невыпуклым многоугольником производятся следующие операции. Если он лежит по одну сторону от прямой АВ, где А и В - несмежные вершины многоугольника, то одна из частей, на которые контур многоугольника делится точками А и В, центрально симметрично отражается относи­тельно середины отрезка АВ. Докажите, что после нескольких таких операций многоугольник станет выпуклым.

Решение.

Итак, операция снова задана - это преобразование много­угольника. Полуинвариант, монотонно увеличивающийся при этой операции, здесь очевиден - это площадь многоугольника. Несколько менееочевидно, что площадь многоугольника в процессе наших преобразований многоугольника может прини­мать лишь конечное число значений. Чтобы это дока­зать, рассмотрим набор век­торов, идущих по сторонам многоугольника. При дан­ной операции этот набор не меняется; изменяется лишь порядок следования векто­ров друг за другом (рис.3). Значит, количество много­угольников, которые можно получить из данного многоугольника при помощи описанной операции, конечно, откуда и следует, что наш полуинвариант может принимать лишь конечное число значений.

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

Решение.

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

Задача 7.При дворе короля Артура собрались 2N рыцарей, причем каждый из них имеет среди присутствующих не более N - 1 врага. Докажите, что Мерлин, советник Артура, может так рассадить рыцарей за Круглый Стол, что ни один из них не будет сидеть рядом со своим врагом.

Решение.

Рассадим рыцарей за Круглым Столом произвольным обра­зом. Если при этом получится, что никакие два врага не сидят рядом, то требование задачи выполнено. В противном случае рассмотрим рыцаря А, сидящего слева от своего врага В (рис.4,a).

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

Среди друзей рыцаря А обязательно найдется такой рыцарь С, что его правый сосед D - друг рыцаря В (иначе у рыцаря В врагов более N - 1). Теперь "развернем" весь участок пола от В до С (справа от В, рис.4,б) в "обратную" сторону (рис.4,в). При этом рыцарь В станетсоседом рыцаря D, рыцарь С - соседом рыцаря А. Остальные пары соседей не изменятся. Следователь­но, полуинвариант действительно уменьшается.

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

Задача 8.На доске в ряд произвольным образом написаны Nчисел, каждое из которых равно + 1 или -1. За один ход разрешается поменять знак у нескольких подряд идущих чисел. За какое наименьшее число ходов можно заведомо получить из исходного набора набор из одних единиц?

Решение.

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

Докажем теперь, что из набора чисел -1, +1, -1, +1, ... нельзя получить набор +1, +1, +1, ... менее чем за [(N+ 1)/2] шагов. (Через [х]обозначена целая часть числа x.)Рассмотрим отдельно случаи четного и нечетного N. Пусть N= 2k, , т.е. [(N + 1)/2] = k. Тогда вначале полуинвариант равен 2k -1, а в конце он должен быть равен нулю. Но за k - 1 ход добиться требуемого невозможно.

Пусть N= 2k + 1, т.е. [(N + 1)/2] = k + 1. В этом случае полуинвариант исходного набора равен 2k, поэтому за k - 1 ход исходный набор заведомо нельзя перевести в набор из одних единиц. Докажем, что это нельзя сделать и за k ходов. Для этого достаточно заметить,  что по крайней мере один раз полуинвариант изменится не более чем на единицу (это произойдёт тогда, когда операция замены знаков затронет какие-то из крайних чисел -1).

Остается показать, что за [(N+1)/2]ходов из любого исходного набора можно получить набор из одних единиц. Выделим в исходном наборе все группы подряд идущих чисел - 1, их не более [(N + 1)/2]. Теперь последовательно изменим знаки у чисел этих групп.

Задачи для самостоятельного решения

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

2.На плоскости дано Nточек, некоторые из которых соединены отрезками. Известно, что из любой точки выходит нe более 11 отрезков. Докажите, что эти точки можно раскрасить в четыре цвета так, чтобы отрезков с одноцветными концами было не более N.

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

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

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

6.На доске написаны 10 чисел: единица и девять нулей. Разрешается выбрать любые два числа и заменить каждое их средним арифметичес­ким. Какое наименьшее число может оказаться на месте единицы после серии таких операций?

7.На бесконечном клетчатом листе белой бумаги несколько клеток закрашено в черный цвет. В моменты времени t= 1, 2, 3, ... происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка К принимает тот цвет, который имело в предыдущий момент большинство из трех клеток: самой клетки К и ее соседей справа и сверху. Докажите, что через некоторое время на листе не останется черных клеток.

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

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

10.В библиотеке на полке в произвольном порядке расставлены N томов Британской энциклопедии. Робот-библиотекарь каждую минуту делает следующее: берет произвольный том, не стоящий на своем месте, и ставит его на место (т.е. если номер тома - k, то он ставит его k-м по счету). Докажите, что через некоторое время все тома будут стоять на своем месте.

Ответы и указания к решению.

1. Соедините красные точки с синими Nотрезками произвольным образом и к двум пересекающимся отрезкам примените операцию, описанную в задаче №3 так, чтобы два новых отрезка также соединяли красные и синие точки.
2. Раскрасьте точки в четыре цвета произвольным образом. Если отрезок с одноцветными концами больше N, то из какой-то точки выходит не менее трех таких отрезков. Эту точку можно перекрасить так, чтобы количество отрезков с одноцветными концами уменьшилось.
3. В качестве полуинварианта рассмотрите количество отрезков с концами одного цвета.
4. Не могут. В качестве полуинварианта рассмотрите разность между наибольшим и наименьшим из чисел.
5. В качестве полуинварианта рассмотрите сумму всех чисел на окружности.
6. . В качестве полуинварианта рассмотрите величину , где через mобозначено наименьшее положительное число среди написанных на доске, а через n  - количество нулей на доске.
7. Заключим всю совокупность черных клеток в большой прямоугольник и введем прямоугольную систему координат с началом в нижнем углу этого прямоугольника. Для каждой черной клетки вычислим сумму ее координат. В качестве полуинварианта рассмотрите максимальное из этих чисел.
8. Заметим, что минимальное число конфет у одного человека в процессе игры не уменьшается, а максимальное может увеличиться не более чем на единицу, если оно нечетно, и не может увеличиться, если оно четно. Если исходный максимум был равен М₀, то в любой момент сумма чисел на окружности не превосходит (М₀+1)n, где n– число участников игры. Поэтому, начиная с какого-то момента, ведущий перестает добавлять конфеты, а это значит, что начиная с этого момента, все числа будут четны. Теперь в  качестве полуинварианта рассмотрите величину , где М – максимальное число конфет у одного игрока, а k– количество игроков с М конфетами.
9. В качестве полуинварианта рассмотрите величину , где  - номера комнат, в которых живут пианисты в данный момент. Докажите, что эта  величина монотонно возрастает и ограничена сверху (на самом деле каждое из чисел  может принимать лишь конечное число значений).
10. Назовем в данной перестановке том «правым», если он стоит справа от своего настоящего места, и «левым», если он стоит слева от своего настоящего места. С каждым «правым» томом с номером kсвяжем число . В качестве полуинварианта рассмотрите сумму всех этих чисел. Другое решение этой задачи может быть основано на использовании в качестве полуинварианта величины , где  - номер места, на котором стоит k-й том.

Метод крайнего.

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

Примеры задач, решаемых данным методом.

Задача №1. На прямой задано множество точек М такое, что каждая точка  из М является серединой отрезка, соединяющего две другие точки из М. Докажите, что множество М бесконечно.

Решение.

Предположим, что множество М конечно. Применим  правило «крайнего»: если множество М – конечное, то среди его точек есть самая левая и самая правая. Рассмотрим одну из них, например, самую левую; обозначим ее буквой А. Точка А – крайняя и поэтому не может лежать внутри отрезка, соединяющего две другие точки множества М. Полученное противоречие и доказывает, что множество М не может быть конечным.

Приведем еще одно решение этой задачи, использующее правило «крайнего». Допустим снова, что множество М конечно, и рассмотрим длины отрезков, соединяющих точки из М. Этот набор ограничен. Применим к нему наше правило в форме «Рассмотри наибольшее!» -  рассмотрим отрезок ВС наибольшей длины. Ясно, что вне отрезка ВС нет точек из М, иначе существовали бы отрезки с большими длинами. Таким образом, все точки множества М лежат на отрезке ВС и, значит, ни В, ни С не удовлетворяют условию, то есть не принадлежат множеству М. Противоречие.

Задача №2. На плоскости задано некоторое множество точек М такое, что каждая точка из М является серединой отрезка, соединяющего какую-либо пару точек того же множества М. Докажите, что множество М содержит бесконечно много точек.

Решение.

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

Задача №3. На полях бесконечной шахматной доски написаны натуральные числа так, что каждое число равно среднему арифметическому четырех соседних чисел – верхнего, нижнего, правого и левого. Докажите, что все числа на доске равны между собой.

Решение.

Решить эту задачу нам поможет правило «крайнего» в форме «Рассмотри наименьшее!». Среди натуральных чисел, записанных на полях шахматной доски, непременно существует наименьшее. В этом нетрудно убедиться. Если среди чисел, записанных на доске, имеется единица, то она и является таким наименьшим числом (не существует натуральных чисел, меньших единицы). Если единицы нет, посмотрим,  нет ли там двойки. Если есть, то она и является наименьшим числом, если же нет, то поищем тройку, и т.д. Не более чем за kшагов мы отыщем, таким образом,  наименьшее число m. Рассмотрим поле Р, на котором оно записано. Обозначим числа, записанные на соседних полях, буквами a, b, c, d. По условию . Отсюда . В силу выбора числа mимеем  , , . Если хоть одно из этих неравенств было бы строгим, то мы имели бы , что противоречит условию. Значит, .

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

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

Решение.

Правило «крайнего» наталкивает на мысль рассмотреть ту из 2n  линий доски – вертикалей и горизонталей, - на которой стоит меньше всего ладей. Может случиться, что есть несколько таких линий, «одинаково загруженных» ладьями. Тогда выберем любую из них. Пусть эта линия – горизонталь (в противном случае повернем доску на  - вертикали станут горизонталями). Число ладей на этой горизонтали обозначим через k. Если , то на каждой из nгоризонталей не менее ладей, а всего на доске не менее ладей.

Пусть теперь . На рассматриваемой горизонтали n-kсвободных полей, и каждая вертикаль, проходящая через такое свободное поле, содержит, как видно из условия, не менее n-kладей, а все такие вертикали – не менее ладей. Остальныеkвертикалей содержат не менее чем по k  ладей каждая (в силу выбора числа k). Всего на доске стоят не менее чем ладей. Остается доказать, что . Рассмотрим разность: .

Если n– число четное, то можно найти удовлетворяющую условию расстановку, содержащую в точности ладей – достаточно поставить ладьи на все черные поля (или на все белые). Если n– нечетное, то ладей расставить, соблюдая условия задачи, нельзя, так как число  нецелое, но ладей расставить можно: одну ладью ставим на одно из угловых полей, а остальные – на поля того же цвета.

Задача №5. Докажите, что не существует четверки натуральных чисел удовлетворяющих уравнению .

Решение.

Допустим, что такие четверки существуют. Рассмотрим ту из них, для которой величина минимальна (если есть несколько четверок, у которых эта величина одинакова и минимальна, рассмотрим одну из них, любую). Пусть это будет четверка a, b, c, d. Из уравнения  видно, что кратно трем. Но легко доказать, что  кратно трем тогда и только тогда, когда и а, и в делятся на три, потому что квадрат числа, не делящегося на три, дает при делении на три в остатке единицу.

Следовательно, , , откуда . Сокращая последнее равенство на 3, получим: . Мы нашли четверку чисел  удовлетворяющую данному уравнению, причем для этой четверки , а это невозможно в силу выбора четверки a, b, c, d.

Задача №6. Семь грибников собрали вместе 100 грибов, причем никакие двое не собрали одинакового числа грибов. Докажите, что есть  трое грибников, собравших  вместе не менее 50 грибов.

Решение.

Составим «таблицу первенства», поместив в ней грибников в порядке убывания числа собранных ими грибов. Ясно, что рассматривать надо грибников, занявших первые три места – они собрали грибов больше, чем любая другая тройка. Попробуем доказать, что они собрали не менее 50 грибов. Если грибник, занявший 3-е место, собрал 16 грибов или больше, то на втором месте  - грибник, собравший не менее 17 грибов, а на первом – не менее 18 грибов. Вместе они собрали не меньше 16+17+18=51 гриба. Если же грибник, занявший 3-е место, собрал не более 15 грибов, то грибники, занявшие места с 4-го по 7-е, собрали не более 14+13+12+11=50 грибов. На долю первой тройки и в этом случае приходится не менее 50 грибов.

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

Задача №7.Докажите, что если длины всех сторон треугольника меньше 1, то его площадь меньше .

Решение.

Пусть - наименьший угол треугольника. Тогда . Поэтому .

Задача №8. Докажите, что круги, построенные на сторонах выпуклого четырехугольника как на диаметрах, полностью покрывают этот четырехугольник.

Решение.

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

Задача №9. В некоторой стране 100 аэродромов, причем все попарные расстояния между ними различны. С каждого аэродрома поднимается самолет и летит на ближайший к нему аэродром. Докажите, что ни на один аэродром не может прилететь больше 5 самолетов.

Решение.

Если самолеты из точек А и В прилетели в точку О, то АВ – наибольшая сторона треугольника АОВ, т.е. . Предположим, что в точку О прилетели самолеты из точек А₁, А₂,…, А_n. Тогда один из углов не превосходит . Поэтому , т.е. .

Задача №10.   Длины биссектрис треугольника не превосходят 1. Докажите, что его площадь не превосходит .

Решение.

Пусть для определенности - наименьший угол треугольника АВС; AD– биссектриса. Одна из сторон АВ или АС не превосходит , так как иначе отрезок ВС не проходит через точку D. Пусть для определенности . Тогда .

Задачи для самостоятельного решения.

1. Пусть неотрицательных целых чисел расположены в виде таблицы, содержащей nстрок и nстолбцов. При этом выполнено следующее условие: если на некотором месте таблицы записан нуль, то сумма чисел столбца и строки, содержащей нуль, не меньше n. Докажите, что сумма всех чисел не меньше /2.
2. На плоскости заданы nточек. Никакие три из них не лежат на одной прямой. Докажите, что существует окружность, проходящая через три данные точки, не содержащая внутри ни одной из данных точек.
3. На плоскости заданы nпрямых . Никакие две из них не параллельны, никакие три не пересекаются в одной точке. Эти прямые разрезают плоскость на части. Докажите, что какую бы из nпрямых мы ни взяли, хотя бы одна из примыкающих к ней частей плоскости является треугольником.
4. На плоскости заданы nпрямых . Любые две прямые пересекаются и через каждую точку пересечения проходят не менее трех из данных прямых. Докажите, что все прямые пересекаются в одной точке.
5. Внутри круга радиуса 1 лежат восемь точек. Докажите, что расстояние между некоторыми двумя из них меньше 1.
6. Внутри остроугольного треугольника взята точка Р. Докажите, что наибольшее из расстояний от точки Р до вершин этого треугольника меньше удвоенного наименьшего из расстояний от Р до его сторон.
7. Докажите, что в любом выпуклом пятиугольнике найдутся три диагонали, из которых можно составить треугольник.
8. На плоскости расположено nточек, причем площадь любого треугольника с вершинами в этих точках не превосходит 1. Докажите, что все точки можно поместить в треугольник площади 4.
9. Докажите, что если центр вписанной окружности четырехугольника совпадает с точкой пересечения диагоналей, то этот четырехугольник – ромб.
10. Докажите, что многоугольник нельзя покрыть двумя многоугольниками, гомотетичными ему с коэффициентом k, где .

Литература.

1. Васильев Н.Б., Егоров А.А. Задачи Всесоюзных математических олимпиад. – М., Наука, 1988.
2. Горбачев Н.В. Сборник олимпиадных задач по математике. – М.: МЦНМО, 2004. – 560 с.
3. Математический кружок (сост. Егоров А.А.). Вып.4. – М., Бюро «Квантум», 1998.
4. Прасолов В.В. Задачи по планиметрии (в двух частях). – М., Наука, 1986.
5. Фарков А.В. Готовимся к олимпиадам по математике: Учеб.-метод. пособие. – М.: Издательство «Экзамен», 2006. – 160с.