Методическая разработка по теме: "Из опыта работы подготовки школьников к олимпиадам по математике". Принцип Дирихле и его применение при решении задач Инварианты и их применение при решении задач Полуинварианты. Метод крайнего. Литература.

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

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

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

повышение интереса школьников к занятиям математикой;

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

подведение итогов и стимулирование работы с одаренными детьми.

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

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

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

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

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

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

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

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

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

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

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

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

Количество часов

Тема занятия

1 – 2

3 – 4

5 – 6

7 – 8

9 – 12

Делимость.

12 часов.

Свойства делимости. Четность. Остатки. Признаки делимости.

Использование числовых сравнений. Сравнения по модулю, свойства.

Сведение к делителям фиксированного числа.

Простые и составные числа. Взаимно – простые числа

НОД. НОК. Алгоритм Евклида.

Уравнения и системы уравнений в целых числах. Наибольший общий делитель. Линейные уравнения. Нелинейные уравнения.

13 – 14

15 – 16

17 – 18

19 – 20

21 – 22

22 – 24

Логические задачи

12 часов.

Сюжетные логические задачи (нахождение соответствия между множествами). Истинные и ложные высказывания. Рыцари, лжецы, хитрецы.

Переливание. Взвешивание

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

Принцип крайнего.

Инварианты, полуинварианты, раскраски.

Графы. Подсчет числа ребер. Графы с цветными ребрами. Ориентированные графы. Деревья.

24 – 25

26 – 28

29 – 30

Уравнения, системы уравнений,
неравенства.

6 часов.

Уравнения и неравенства, содержащие целую и дробную часть числа.

Доказательство неравенств на основании определения. Выделение полного квадрата. Доказательство неравенств с помощью «опорных» неравенств.

Метод оценки при решении неравенств и уравнений, систем уравнений.

31 – 34

Геометрия.

4 часа.

Вписанная и описанная окружности: формула Эйлера, прямая Симпсона, теорема Птолемея, вневписанные окружности. Вспомогательная окружность.

Решение задач городских математических олимпиад.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если внутри фигуры площадью 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 имеются вершины обоих цветов.

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

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

B

E

D

C

A

Решение.

Возьмем отрезок АВ длиной 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 или меньше, то найдутся два столбца, в каждом из которых стоит не более одной звездочки (принцип Дирихле). Вычеркнем оставшиеся два столбца. После этого останется не больше двух звездочек, которые можно вычеркнуть вместе со строками, в которых они стоят.

Выводы.

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

определить, что удобно в задаче принять за «клетки», а что за «зайцев»;

получить «клетки». Чаще всего «клеток» меньше (боль­ше), чем «зайцев» на одну;

выбрать для решения требуемую формулировку принципа Дирихле.

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

В лесу растет миллион ёлок. Известно, что на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся две ёлки с одинаковым количеством иголок.

В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начина­ются с одной буквы?

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

В мешке лежат 10 белых и 10 черных шаров. Они тща­тельно перемешаны и неразличимы на ощупь. Какое наи­меньшее число шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара: 1) одного цвета, 2) разного цвета, 3) белого цвета?

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

В классе 37 учеников. Докажите, что среди них найдут­ся 4 ученика, отмечающие день рождения в одном месяце.

В школе учатся 1200 учеников. Найдется ли день, в ко­торый отмечают свои дни рождения не меньше, чем 4 ученика данной школы?

В школе 33 класса, 1150 учеников. Найдется ли класс, в котором меньше 35 учеников?

В магазин привезли 26 ящиков с яблоками трёх сортов, причём в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

В классе 29 учеников. Петя Иванов сделал в диктанте 13 ошибок, остальные ученики — меньше. Докажите, что в классе найдётся, по крайней мере, 3 ученика, сделавших оши­бок поровну.

В классе 26 учеников, из них более половины — маль­чики. Докажите, что какие-то 2 мальчика сидят за одним сто­лом. (В классе 13 столов).

На шахматной доске размером 8x8 Вася расставил 14 фигур. Докажите, что найдется квадрат размером 2x2, в котором не будет фигур. (Фигуры размещаются внутри клеток размером 1x1).

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

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

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

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

30 команд участвует в первенстве по футболу. Каждые 2 команды должны сыграть между собой один матч. Докажи­те, что в любой момент состязаний имеются 2 команды, сыг­равшие к этому моменту одинаковое число матчей.

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

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

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

Коля хочет записать на доске 55 различных двузнач­ных чисел так, чтобы среди них не было двух чисел, дающих в сумме 100. Сможет ли он это сделать?

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

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

15 девочек собрали 100 орехов. Докажите, что какие-то две из них собрали одинаковое число орехов.

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

Докажите, что в любой компании из пяти человек двое имеют одинаковое число знакомых.

Докажите, что в любой компании найдутся 2 человека, у которых одинаковое число знакомых в этой компании (воз­можно, ни одного).

Можно ли увезти 50 камней весом 370, 372, 374, 376, ..., 466, 468 кг на семи трёхтонках?

Дано 70 натуральных различных чисел, каждое из ко­торых не превосходит 200. Доказать, что какие-то 2 из них отличаются на 4; 5 или 9.

Какое максимальное количество натуральных чисел от 1 до 50 можно выбрать так, чтобы среди них не было двух чи­сел, отличающихся ровно в два раза?

Даны 8 натуральных различных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

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

Имеется 11 натуральных различных чисел, не больше: 20. Докажите, что из них можно выбрать два числа, одно и которых делится на другое.

В квадрате со стороной 10 см находится 51 точка. Докажите, что найдутся три точки, принадлежавшие кругу с радиусом см.

В кубе со стороной 1 м находится 2003 таракана. Докажите, что хотя бы трех из них можно поймать сферой радиуса 1/11 м.

За пять лет обучения в вузе студент сдал 31 экзамен причем в каждом году он сдавал экзаменов больше, чем в предыдущем. На пятом курсе экзаменов втрое больше, чем на первом. Сколько экзаменов на четвёртом курсе?

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

Пусть ёлки — «зайцы», а число иголок на ёлках: 0, 1, 2, 3 ... 600000 — «клетки». «Клеток» будет 600001, а «зайцев» — 1000000. Здесь «зайцев» гораздо больше, чем «клеток». Тогда по принципу Дирихле в какой-то «клетке» будет находиться не менее двух «зайцев». Но если в одной «клетке» сидят два «зайца», то число иголок у этих ёлок будет одинаково.

Обозначим 35 учеников за «зайцев», а буквы за «клет­ки». В русском алфавите 33 буквы. Фамилии не могут начи­наться разве что на Ъ и Ь. Так как 35 > 31, то по принципу Ди­рихле найдется 2 ученика, у которых фамилия начинается с одной буквы.

Обозначив комнаты — «клетками», а гостей — «зайца­ми», имеем: 36 < 42. Тогда по принципу Дирихле найдется как минимум одна пустая «клетка», т.е. в какую-то комнату не придет ни одного гостя.

1) Цвета шаров обозначим за «клетки» (их две), значит «зайцев» надо больше. Достанем 3 шара из мешка. Так как 3 > 2, то по принципу Дирихле найдется «клетка» (цвет шара), в которую попадут как минимум 2 «зайца» (шара). Значит, надо достать наименьшее число шаров три.

Так как подряд могут попадаться все время шары одно­го цвета, то наименьшее число шаров надо достать 11.

Наименьшее число шаров будет 12.

Так как числа бывают чётные или нечётные, а всего чи­сел — три, то, применяя принцип Дирихле, как минимум 2 из них будут оба чётные или оба нечётные. В первом и во втором случае сумма чисел будет чётной. Значит, верно.

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

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

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

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

Допустим, что во всех классах не менее 35 учеников, то­гда во всей школе будет не менее чем 35 · 33 = 1155 (учени­ков), что противоречит условию задачи. Значит, в школе най­дется класс, в котором меньше, чем 35 учеников.

26 ящиков — «кроликов» рассадим по трём «клеткам» — сортам. Так как 26 = 3 · 8 + 2, то применим обобщенный принцип Дирихле для т = 3, к = 8 и получим, что в какой-то «клетке» — сорте не менее 9 ящиков.

Обозначив число ошибок: 0, 1, 2, ... 11, 12 за «клетки», а 28 учеников (без Пети) за «зайцев», получим: 28 > 13 · 2 + 1. Применяя обобщенный принцип Дирихле, получим, что не менее 3 учеников сделали ошибок поровну.

Обозначим мальчиков за «зайцев», а столы — за «клет­ки». Так как мальчиков больше половины, то есть больше 13 — числа столов, то по принципу Дирихле, найдется стол, за которым сидят не менее 2 мальчиков. А так как больше 2 мальчиков за стол не помещается, то это означает, что най­дется стол, за которым сидят 2 мальчика.

Разобьем квадрат 8x8 следующим образом на клетки:

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

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

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

Разобьем прямоугольник на 5 фигур, как на рисунке:

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

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

Все команды сыграли хотя бы один матч. Тогда число сыгранных матчей каждой командой могло быть 1, 2, 3 или 4. Обозначим эти 4 варианта за «клетки»; тогда 5 команд будут «зайцами». Так как 5 > 4, то по принципу Дирихле найдется не менее 2 команд, сыгравших одинаковое число матчей.

Пусть есть команда, не игравшая матчей. Тогда число сыгранных матчей может быть 0, 1, 2 или 3. Так как команд 5, а вариантов опять 4, то найдутся как минимум 2 команды, которые сыграли к данному моменту одинаковое число мат­чей (возможно, ни одного).

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

Пусть все команды к данному моменту времени сыгра­ли хотя бы один матч. Тогда число сыгранных матчей каждой командой могло быть 1, 2, 3 ... 28, 29. Обозначим эти 29 вари­анта за «клетки»; тогда 30 команд будут «зайцами». Так как 30 > 29, то по принципу Дирихле найдется не менее 2 команд, сыгравших одинаковое число матчей.

Пусть есть команда, не игравшая матчей. Тогда число сыгранных матчей может быть 0, 1, 2 ... 28. Так как команд 30, а вариантов снова 29, то найдутся как минимум 2 команды, которые сыграли к этому моменту одинаковое число матчей (возможно, ни одного).

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

Рассмотрим день, в который кино посетило больше всего народу. Так как дней в 2 неделях 14, то посетило в этот день кино не менее 14 учеников. Так как мальчиков в классе 13, то, как минимум одна, есть девочка среди 14 учеников. Но девочек в классе 6, поэтому мальчиков будет не менее 8.

Замечание:
Автор: Неверовская Светлана Владимировна