МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Руководитель Степан Львович Кузнецов
2015/2016 учебный год

Группа ББ (cтарший преподаватель К. Н. Бондаренко)

Занятие 7 (7 ноября 2015 года). Принцип Дирихле

1.: Осенью отряд из 21 белки пополнял запасы и собрал 200 орехов. Докажите, что какие-то 2 белки собрали одинаковое число орехов.
Решение

Решение. Если у всех разное число орехов, то всего было бы собрано не меньше 0 + 1 + 2 + 3 + ... + 20 = 210 орехов, что противоречит условию задачи.
2.: На территории МГУ припарковано 100 машин. Среди них — 30 чёрных, 20 синих и 20 белых мерседесов. Никакие два мерседеса разного цвета не стоят рядом. Докажите, что тогда какие-то три мерседеса, стоящие подряд — одного цвета.
Решение

Решение. На территории МГУ припарковано 70 мерседесов и 30 других машин. По условию, рядом с мерседесом может стоять либо мерседес того же цвета, либо «другая» машина. Чем больше мерседесов будут стоять парами, тем меньше понадобится других машин. Но пар мерседесов 35, и на их окружение понадобится 34 машины. Если мерседесы стоят не обязательно парами, то машин понадобится еще больше. Но «других», по условию, всего 30, значит поставить можно только 31 пару. Значит, рядом окажутся три одинаковых мерседеса.
3.: Олимпиаду писали 70 школьников. Аркаша набрал 33 балла, остальные меньше. Докажите, что по крайней мере три школьника набрали одинаковое количество баллов.
Решение

Решение. Предположим, что не нашлось таких трёх школьников. Тогда одинаковое количество баллов (от 0 до 32) набрали не более двух школьников. Тогда школьников, не считая Аркаши, не более 33·2 = 66, а их 69. Противоречие.
4.: Докажите, что в любой компании есть двое, имеющие одинаковое число знакомых в этой компании.
Решение

Решение. Пусть в компании n человек. Тогда у каждого человека имеется от 0 до n − 1 друзей. Таким образом, количество друзей может принимать n различных значений: 0, 1, 2, ..., n − 1. Поэтому если бы n человек имели различное число друзей, то в компании присутствовало бы по одному человеку, имеющему 0, 1, 2, ..., n − 1 друзей. С другой стороны, если есть человек, имеющий n − 1 друга, то он дружит со всеми, следовательно, нет человека, который имеет 0 друзей. Противоречие.
5.: В кинотеатре 7 рядов по 10 мест. Группа из 50 человек сходила на утренний и вечерний сеансы. Докажите, что найдутся два человека, которые и утром, и вечером сидели на одном ряду.
Решение

Решение. Если бы в каждом из 7 рядов сидело не более 7 детей, то всего детей было бы не более 49. Следовательно, есть ряд, в котором сидело не менее 8 детей. Поскольку рядов всего 7, хотя бы двое из этих детей окажутся в одном ряду на вечернем сеансе.
6.: Можно ли расставить на окружности числа 1, 2, ..., 12 так, чтобы разность между двумя рядом стоящими числами была 3, 4 или 5?
Решение Ответ

Решение. Заметим, что числа 1, 2, 3, 10, 11, 12 не могут стоять рядом. Так как всего двенадцать позиций, то эти числа должны стоять через один (иначе по принципу Дирихле какие-то два из этих чисел будут стоять рядом). Осталось заметить, что число 4 должно соседствовать с двумя числами из стоящих через один, а оно может соседствовать только с числом 1.

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

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

Случай 2. У человека A среди остальных пяти есть три незнакомых ему. Среди этих трех людей есть либо двое незнакомых — тогда они вместе с A образуют нужную тройку незнакомых, либо они все трое попарно знакомы.

Другое решение.. Поставим шесть точек, соответствующие шести людям. Если люди знакомы между собой, соединим соответствующие точки красным отрезком, если не знакомы, то синим. Тогда, если на нашем рисунке есть красный треугольник, это означает, что существует три попарно знакомых между собой человека, а если есть синий треугольник, то существует три попарно незнакомых между собой человека. Рассмотрим любую из шести точек. Из неё выходит пять отрезков. Из пяти отрезков есть по крайней мере три одного цвета. Предположим, есть три синих отрезка (случай, когда есть три красных отрезка, рассматривается аналогично.) Если какие-то два конца этих отрезков соединены между собой синим, то есть синий треугольник. Если же все концы этих отрезков соединены между собой красным, то получается, что есть красный треугольник.
8.: Докажите, что если a, b, c — нечётные числа, то хотя бы одно из чисел ab − 1, bc − 1, ca − 1 делится на 4.
Решение

Решение. Нечётные при делении на 4 могут дать остатки 1 или 3. Имеем три числа, следовательно, по крайней мере два числа имеют один остаток. Рассмотрим эти числа. Не нарушая общности, будем считать, что это числа a, b и остаток 3. Запишем a = 4k + 3 и b = 4n + 3. Рассмотрим комбинацию данную в условии: ab − 1 = (4k + 3)(4n + 3) − 1 = 16kn + 12(k + n) + 8 и делаем вывод, что полученное выражение делится на четыре.
9.: Можно ли таблицу 5×5 заполнить числами −1, 0, 1 так, чтобы суммы во всех строках, во всех столбцах и на главных диагоналях были различны?
Решение Ответ

Решение. Каждая из этих сумм состоит из 5 слагаемых, принимающих одно из значений −1, 0, 1, поэтому каждая из сумм принимает целочисленное значение в диапазоне от −5 до 5. Всего возможных значений сумм — 11. Поскольку 11 < 12, какие-то две из сумм обязательно принимают равные значения.
Замечание. В общем случае: в таблице n × n можно получить лишь 2n + 1 разных сумм, т. к. каждая из сумм принимает значения от − n до n, а необходимо 2n + 2.

Ответ. Нельзя.
10.: По кругу записаны 7 натуральных чисел. Известно, что в каждой паре соседних чисел одно делится на другое. Докажите, что найдётся пара несоседних чисел с таким же свойством.
Решение

Решение. Соединим пары соседних чисел так, чтобы стрелка шла от кратного к делителю (если соседние числа равны, то направление стрелки выбираем произвольно). Общее количество стрелок нечётно (семь), поэтому их направления не могут чередоваться. Следовательно, какие-то две соседние стрелки направлены в одну сторону, скажем, X → Y → Z. Отсюда следует, что X делится на Z, но X и Z не соседние.

Дополнительные задачи

11.: Несколько одинаковых ящиков весят вместе 10 т, причём каждый весит не более 1 т. Какого наименьшего числа трёхтонок достаточно, чтобы увезти за один раз весь груз?
Решение

Решение. Покажем, что пяти машин точно достаточно. Будем грузить машины ящиками в любом порядке до тех пор, пока ящики не кончатся, следя лишь за тем, чтобы не наступила «перегрузка» машины. Это возможно, так как в любой момент погрузки будет хотя бы одна машина, загруженная не более чем 2 тоннами. Действительно, если бы все машины были загружены больше, чем на 2 тонны, то общий вес груза составлял бы больше, чем 5·2 = 10 т, что противоречит условию задачи. Эту машину можно догрузить любым ящиком, поскольку по условию задачи он весит не более тонны.
Покажем, что четырёх машин может не хватить. Например, для вывоза 13 ящиков весом ¹⁰/₁₃ т каждый, четырёх машин недостаточно. Действительно, каждая машина может увезти не более трёх таких ящиков, так как 4 ящика весят ⁴⁰/₁₃ > 3 т. Значит, все машины увезут не больше 12 ящиков.
12.: В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
Решение

Решение. Рассмотрим двоих учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого ученика имеется 24 друга, и задача решена.) Пусть этими двумя будут Вася и Петя. Тогда из оставшихся 23 учеников каждый дружит либо с Васей, либо с Петей. Действительно, если бы кто-то (скажем, Коля) не дружил бы ни с Васей, ни с Петей, то мы имели бы троих учеников, среди которых не было бы друзей. Теперь если предположить, что и Вася, и Петя имеют не более 11 друзей, то всего в классе, кроме этих двоих было бы не больше 22 человек. Полученное противоречие показывает, что один из школьников имеет не менее 12 друзей.v


	МАЛЫЙ МЕХМАТ МГУ

ГЛАВНАЯ СТРАНИЦА НАША КОМАНДА О КРУЖКАХ РАСПИСАНИЕ ВОПРОС-ОТВЕТ ЛЕКЦИИ МАТЕРИАЛЫ ЗАНЯТИЙ 5 класс 6 класс 7 класс 8 класс Перечневые олимпиады 2-3 уровень АРХИВ МАЛЫЙ МЕХМАТ — ШКОЛЕ ЛИТЕРАТУРА ССЫЛКИ	Кружок 7 класса Руководитель Степан Львович Кузнецов 2015/2016 учебный год Группа ББ (cтарший преподаватель К. Н. Бондаренко) Занятие 7 (7 ноября 2015 года). Принцип Дирихле 1. Осенью отряд из 21 белки пополнял запасы и собрал 200 орехов. Докажите, что какие-то 2 белки собрали одинаковое число орехов. Решение Решение. Если у всех разное число орехов, то всего было бы собрано не меньше 0 + 1 + 2 + 3 + ... + 20 = 210 орехов, что противоречит условию задачи. 2. На территории МГУ припарковано 100 машин. Среди них — 30 чёрных, 20 синих и 20 белых мерседесов. Никакие два мерседеса разного цвета не стоят рядом. Докажите, что тогда какие-то три мерседеса, стоящие подряд — одного цвета. Решение Решение. На территории МГУ припарковано 70 мерседесов и 30 других машин. По условию, рядом с мерседесом может стоять либо мерседес того же цвета, либо «другая» машина. Чем больше мерседесов будут стоять парами, тем меньше понадобится других машин. Но пар мерседесов 35, и на их окружение понадобится 34 машины. Если мерседесы стоят не обязательно парами, то машин понадобится еще больше. Но «других», по условию, всего 30, значит поставить можно только 31 пару. Значит, рядом окажутся три одинаковых мерседеса. 3. Олимпиаду писали 70 школьников. Аркаша набрал 33 балла, остальные меньше. Докажите, что по крайней мере три школьника набрали одинаковое количество баллов. Решение Решение. Предположим, что не нашлось таких трёх школьников. Тогда одинаковое количество баллов (от 0 до 32) набрали не более двух школьников. Тогда школьников, не считая Аркаши, не более 33·2 = 66, а их 69. Противоречие. 4. Докажите, что в любой компании есть двое, имеющие одинаковое число знакомых в этой компании. Решение Решение. Пусть в компании `n` человек. Тогда у каждого человека имеется от 0 до `n` − 1 друзей. Таким образом, количество друзей может принимать `n` различных значений: 0, 1, 2, ..., `n` − 1. Поэтому если бы `n` человек имели различное число друзей, то в компании присутствовало бы по одному человеку, имеющему 0, 1, 2, ..., `n` − 1 друзей. С другой стороны, если есть человек, имеющий `n` − 1 друга, то он дружит со всеми, следовательно, нет человека, который имеет 0 друзей. Противоречие. 5. В кинотеатре 7 рядов по 10 мест. Группа из 50 человек сходила на утренний и вечерний сеансы. Докажите, что найдутся два человека, которые и утром, и вечером сидели на одном ряду. Решение Решение. Если бы в каждом из 7 рядов сидело не более 7 детей, то всего детей было бы не более 49. Следовательно, есть ряд, в котором сидело не менее 8 детей. Поскольку рядов всего 7, хотя бы двое из этих детей окажутся в одном ряду на вечернем сеансе. 6. Можно ли расставить на окружности числа 1, 2, ..., 12 так, чтобы разность между двумя рядом стоящими числами была 3, 4 или 5? Решение Ответ Решение. Заметим, что числа 1, 2, 3, 10, 11, 12 не могут стоять рядом. Так как всего двенадцать позиций, то эти числа должны стоять через один (иначе по принципу Дирихле какие-то два из этих чисел будут стоять рядом). Осталось заметить, что число 4 должно соседствовать с двумя числами из стоящих через один, а оно может соседствовать только с числом 1. Ответ. Нет. 7. Докажите, что из 6 сидящих за столом человек всегда найдутся трое попарно знакомых или трое попарно незнакомых. Решение Другое решение. Решение. Возьмем человека A. Распределим остальных в две группы: в первую группу тех, кто знаком с A, во вторую группу — тех, кто не знаком с A. По принципу Дирихле, в одной из групп найдутся три человека, то есть, среди остальных пяти есть либо не менее трех знакомых, либо не менее трех незнакомых ему. Случай 1. У человека A среди остальных пяти есть трое знакомых. Среди этих трех людей есть либо двое знакомых — тогда они вместе с A образуют нужную тройку знакомых, либо они все трое попарно незнакомы. Случай 2. У человека A среди остальных пяти есть три незнакомых ему. Среди этих трех людей есть либо двое незнакомых — тогда они вместе с A образуют нужную тройку незнакомых, либо они все трое попарно знакомы. Другое решение.. Поставим шесть точек, соответствующие шести людям. Если люди знакомы между собой, соединим соответствующие точки красным отрезком, если не знакомы, то синим. Тогда, если на нашем рисунке есть красный треугольник, это означает, что существует три попарно знакомых между собой человека, а если есть синий треугольник, то существует три попарно незнакомых между собой человека. Рассмотрим любую из шести точек. Из неё выходит пять отрезков. Из пяти отрезков есть по крайней мере три одного цвета. Предположим, есть три синих отрезка (случай, когда есть три красных отрезка, рассматривается аналогично.) Если какие-то два конца этих отрезков соединены между собой синим, то есть синий треугольник. Если же все концы этих отрезков соединены между собой красным, то получается, что есть красный треугольник. 8. Докажите, что если `a`, `b`, `c` — нечётные числа, то хотя бы одно из чисел `ab` − 1, `bc` − 1, `ca` − 1 делится на 4. Решение Решение. Нечётные при делении на 4 могут дать остатки 1 или 3. Имеем три числа, следовательно, по крайней мере два числа имеют один остаток. Рассмотрим эти числа. Не нарушая общности, будем считать, что это числа `a`, `b` и остаток 3. Запишем `a` = 4`k` + 3 и `b` = 4`n` + 3. Рассмотрим комбинацию данную в условии: `ab` − 1 = (4`k` + 3)(4`n` + 3) − 1 = 16`kn` + 12(`k` + `n`) + 8 и делаем вывод, что полученное выражение делится на четыре. 9. Можно ли таблицу 5×5 заполнить числами −1, 0, 1 так, чтобы суммы во всех строках, во всех столбцах и на главных диагоналях были различны? Решение Ответ Решение. Каждая из этих сумм состоит из 5 слагаемых, принимающих одно из значений −1, 0, 1, поэтому каждая из сумм принимает целочисленное значение в диапазоне от −5 до 5. Всего возможных значений сумм — 11. Поскольку 11 < 12, какие-то две из сумм обязательно принимают равные значения. Замечание. В общем случае: в таблице `n` × `n` можно получить лишь 2`n` + 1 разных сумм, т. к. каждая из сумм принимает значения от − `n` до `n`, а необходимо 2`n` + 2. Ответ. Нельзя. 10. По кругу записаны 7 натуральных чисел. Известно, что в каждой паре соседних чисел одно делится на другое. Докажите, что найдётся пара несоседних чисел с таким же свойством. Решение Решение. Соединим пары соседних чисел так, чтобы стрелка шла от кратного к делителю (если соседние числа равны, то направление стрелки выбираем произвольно). Общее количество стрелок нечётно (семь), поэтому их направления не могут чередоваться. Следовательно, какие-то две соседние стрелки направлены в одну сторону, скажем, `X` → `Y` → `Z`. Отсюда следует, что `X` делится на `Z`, но `X` и `Z` не соседние. Дополнительные задачи 11. Несколько одинаковых ящиков весят вместе 10 т, причём каждый весит не более 1 т. Какого наименьшего числа трёхтонок достаточно, чтобы увезти за один раз весь груз? Решение Решение. Покажем, что пяти машин точно достаточно. Будем грузить машины ящиками в любом порядке до тех пор, пока ящики не кончатся, следя лишь за тем, чтобы не наступила «перегрузка» машины. Это возможно, так как в любой момент погрузки будет хотя бы одна машина, загруженная не более чем 2 тоннами. Действительно, если бы все машины были загружены больше, чем на 2 тонны, то общий вес груза составлял бы больше, чем 5·2 = 10 т, что противоречит условию задачи. Эту машину можно догрузить любым ящиком, поскольку по условию задачи он весит не более тонны. Покажем, что четырёх машин может не хватить. Например, для вывоза 13 ящиков весом ¹⁰/₁₃ т каждый, четырёх машин недостаточно. Действительно, каждая машина может увезти не более трёх таких ящиков, так как 4 ящика весят ⁴⁰/₁₃ > 3 т. Значит, все машины увезут не больше 12 ящиков. 12. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей. Решение Решение. Рассмотрим двоих учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого ученика имеется 24 друга, и задача решена.) Пусть этими двумя будут Вася и Петя. Тогда из оставшихся 23 учеников каждый дружит либо с Васей, либо с Петей. Действительно, если бы кто-то (скажем, Коля) не дружил бы ни с Васей, ни с Петей, то мы имели бы троих учеников, среди которых не было бы друзей. Теперь если предположить, что и Вася, и Петя имеют не более 11 друзей, то всего в классе, кроме этих двоих было бы не больше 22 человек. Полученное противоречие показывает, что один из школьников имеет не менее 12 друзей.v	ЗАДАЧИ 7 класс Занятие 1 Занятие 2 Занятие 3 Занятие 4 Занятие 5 Занятие 6 Занятие 7 Занятие 8 Занятие 9 Занятие 10 Занятие 11 Занятие 12 Занятие 13