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

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

Занятие 13. Принцип Дирихле (20.03.05)

1.

За победу в турнире Архимеда команда из 8 человек получила 12 конфет. Дети поделили конфеты между собой, не разламывая их. Определите, верны ли следующие утверждения:
«кому-то досталось по крайней мере 2 конфеты»;
«кому-то досталось по крайней мере 3 конфеты»;
«двум людям досталось по крайней мере две конфеты»;
«каждому досталась хотя бы одна конфета».

Ответ Решение

Ответ. Первое утверждение верно, все остальные — нет.

Решение.
1) Да, верно. Предположим противное, т.е. что существует ситуация, когда дети поделили конфеты так, что каждый получил 0 или 1 конфету. Тогда все дети в сумме получили не более 8 конфет, что противоречит условию. Значит наше предположение неверно, и такая ситуация существовать не может. Т. о. всегда найдётся тот, кто получил, по крайней мере, 2 конфеты.
Для всех остальных пунктов можно построить пример, когда дети поделили 12 конфет так, что указанные утверждения не выполняются:
2) 4 человека получили по 2 конфеты, а остальные 4 по одной.
3) Все конфеты забрал один человек.
4) Аналогично пункту 3.

2.

У трёх членов жюри спросили: «Сколько команд будет участвовать в турнире Архимеда?» Один сказал: «Меньше тридцати трех». Другой: «Меньше тридцати одной», а третий: «Меньше тридцати двух». Сколько команд участвовало в турнире Архимеда, если правы оказались в точности двое членов жюри?

Ответ Решение

Ответ. 31 команда.

Решение. Заметим, что из верности второго утверждения вытекает верность остальных. А так как верными оказались ровно два утверждения, то второе утверждение неверно, а первое и третье верны. Т. о. количество команд, с одной стороны, не может быть больше 31 (т. к. иначе неверно третье утверждение), а с другой стороны, не может быть меньше 31 (т.к. иначе верно второе утверждение). Значит. единственно возможное количество команд — 31.
Легко проверить, что 31 удовлетворяет условию задачи.

3.

На финальном матче школьного первенства по баскетболу команда 6А забила 9 мячей. Докажите, что найдутся два игрока этой команды, забившие поровну мячей. (В команде было 5 игроков.)

Решение

Решение. Предположим, что возможен случай, когда такие два игрока не найдутся. Тогда все пять игроков забили разное количество мячей. Пусть первый игрок ничего не забил, второй игрок забил один мяч, третий игрок забил два мяча, четвёртый — три, пятый — четыре. Тогда всего игроки забили десять мячей. Если же кто-то из игроков забил больше мячей, чем мы предположили, то и всего игроки забили больше мячей. Поскольку по условию игроки забили всего девять мячей, наше предположение неверно. Значит, существуют два игрока команды, забившие поровну мячей.

4.

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

Ответ Решение

Ответ. 8!² способов, 8! способов.

Решение. Рассмотрим сначала случай, когда шашки белые. Будем расставлять шашки. В первом столбце мы можем поставить шашку в любую из 8 клеток. Во втором столбце — в любую из 7 клеток. (Т. к. нельзя ставить в ту же строку, в которой стоит первая шашка.) Аналогично в третьей строке мы можем поставить шашку в любую из 6 клеток, в четвёртой строке — в любую из пяти и т. д. Итого получаем 8! способов.
Теперь рассмотрим случай цветных шашек. Возьмём произвольную расстановку белых шашек. Будем раскрашивать эти шашки в 8 цветов, так чтобы любые две из них были покрашены в разные цвета. Первую мы можем покрасить в один из 8 цветов, вторую — в один из 7 оставшихся и.т. д. Т. е. всего 8! способов раскраски. Поскольку способов расстановки тоже 8! , и каждую из этих расстановок мы можем раскрасить 8! способами, то всего способов в этом случае 8!·8!=8!².

5.

В Москве проживает более 10 000 000 людей. На голове у каждого человека не может быть более 300 000 волос. Докажите, что наверняка найдутся 34 москвича с одинаковым числом волос на голове.

Решение

Решение. На голове может быть 0, 1, …, 300 000 волос — всего 300 001 вариант. Каждого москвича отнесём к одной из 300 001 групп в зависимости от количества волос. Если 34 москвича с одинаковым количеством волос не найдутся, то это значит, что в любую из созданных групп входит не более 33 человек. Тогда всего в Москве живёт не более 33·300 001=9 900 033 < 10 000 000 человек, что противоречит условию. Значит, такие 34 москвича обязательно найдутся.

6.

Имеется клетчатая доска размером а) 10×10; б) 11×11. Играют двое. За один ход разрешено в любом столбце или в любой строке закрасить сколько угодно стоящих подряд незакрашенных клеток. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре и как он должен играть?

Ответ Указание

Ответ. а) Второй; б) первый.

Указание. К победе приводит симметричная стратегия.

7.

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

Ответ Решение

Ответ. Да, верно.

Решение. Проведём рассуждения сразу для любой аудитории.
Доказательство от противного. Пусть в аудитории присутствует n человек, и у всех из них разное количество друзей. Друзей может быть 0, 1, 2, …, (n − 1). Всего n возможных вариантов. А т.к. человек тоже n, то все эти варианты используются. Значит, есть человек, у которого 0 друзей, т. е. который ни с кем не дружит. И есть человек, у которого (n − 1) друг, т.е. который дружит со всеми. Однако этого быть не может, т.к. эти два человека должны одновременно и дружить, и не дружить друг с другом. Получаем противоречие. Значит, такие два человека всегда найдутся.