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

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

Руководители Сергей Александрович Дориченко и Степан Львович Кузнецов
2009/2010 учебный год

Занятие 3. Комбинаторика

Вариант I (аудитории 1304 и 1306)

1.

В некоторой стране есть два города. В одном из них живут только люди, которые всегда говорят правду, в другом — только те, кто всегда лжёт. Все они ходят друг к другу в гости, т. е. в любом из этих двух городов можно встретить как честного человека, так и лжеца. Предположим, вы оказались в одном из этих городов. Как, задав один-единственный вопрос первому встречному, определить, в какой город вы попали — в город честных или в город лжецов?

2.

Сколькими способами можно выбрать гласную и согласную буквы из слова „КРУЖОК“?

3.

а): Сколько существует трёхзначных чисел?
б): Каких пятизначных чисел больше: не делящихся на 5 или тех, у которых ни первая, ни вторая цифра слева — не пятёрка?
в): Сколько существует девятизначных чисел, сумма цифр которых чётна?

4.

а): Сколькими способами учитель может построить свой класс из 20 человек в шеренгу?
б): А сколько у него есть способов для того, чтобы выбрать троих учеников и назначить их дежурным, старостой и ответственным за журнал?
в): А тремя дежурными?

5.

а): В классе n школьников. Сколькими способами учитель может выбрать из них k человек и распределить между ними k ролей в школьном спектакле?
б): А сколькими способами можно выбрать из этого класса команду из k человек для математического боя?

6.

Один поезд едет из Москвы в С.-Петербург, а другой — из С.-Петербурга в Москву, выезжая на час позже первого. Какой из этих поездов будет ближе к Москве, когда они встретятся?

7.

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

8.

30 команд сыграли турнир по олимпийской системе (проигравший вылетает). Сколько всего было сыграно матчей?

9.

На дворе бегают куры и поросята, у всех вместе 20 голов и 52 ноги. Сколько всего кур и сколько поросят?

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

10.

В таблице m×n расставлены числа так, что сумма чисел в любой строке и в любом столбце равна 10. Докажите, что m=n.

11.

На Марсе обитает племя трёхруких аборигенов, у каждого из которых растёт на голове некоторое количество антенн (у разных марсиан количество антенн может быть разным). На празднике Харуча-Бабучара все марсиане этого племени взялись за руки (ни одна из рук не осталась свободной). Оказалось, что в каждой паре марсиан, взявшихся за руки, один имеет в 8 раз больше антенн, чем другой. Докажите, что у всего племени не может быть в сумме 2009 антенн.

12.

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

Вариант II (аудитории 1303 и 1311)

1.

2.

а): Каких пятизначных чисел больше: не делящихся на 5 или тех, у которых ни первая, ни вторая цифра слева — не пятёрка?
б): Сколько существует девятизначных чисел, сумма цифр которых чётна?

3.

а): Сколькими способами учитель может построить свой класс из 20 человек в шеренгу?
б): А сколько у него есть способов для того, чтобы выбрать троих учеников и назначить их дежурным, старостой и ответственным за журнал?
в): А тремя дежурными?

4.

а): В классе n школьников. Сколькими способами учитель может выбрать из них k человек и распределить между ними k ролей в школьном спектакле?
б): А сколькими способами можно выбрать из этого класса команду из k человек для математического боя?

5.

6.

Вася заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько друзей у Васи? (Укажите все решения.)

7.

Сколько существует способов разложить 20 одинаковых носков по 5 различным ящикам?

8.

У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 7 соседних баронств?

9.

На дворе бегают куры и поросята, у всех вместе 20 голов и 52 ноги. Сколько всего кур и сколько поросят?

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

10.

11.

12.

Докажите, что существует ровно 2^{n − 1} способов выбрать чётное число предметов из n.

Вариант III (аудитория 1302)

1.: На почте продаются 10 видов конвертов и 7 видов марок. У Андрея есть 60 знакомых. Он хочет каждому послать письмо, чтобы при этом любые 2 письма не совпадали (письмо — это конверт и марка). Удастся ли ему это?
2.: Из города А в город Б ведут 20 дорог. Сёма хочет сходить из города А в город Б и вернуться, не проходя по одной дороге дважды. Сколько возможных маршрутов у Сёмы?
3.: В классе учатся 15 мальчиков и 10 девочек. Сколькими способами можно составить 10 пар (мальчик с девочкой) для участия в конкурсе по бальным танцам?

Запись n! означает произведение целых чисел от 1 до n, то есть n!=1·2·…·n. 1!=1, 2!=1·2=2, 3!=1·2·3=6.

4.

Сколько существует трехзначных чисел без 0 таких, что все цифры различны? А четырехзначных?

5.

Семья из 4 человек каждый вечер по-новому садится ужинать на кухне на 4 имеющихся мест. Сколько дней они смогут делать это без повторений?

6.

Сколько 9-ти значных чисел таких, что в их записи используются все цифры от 1 до 9?

7.

Есть 25 различных шаров. Сколько существует различных способов поставить их в ряд?

8.

На сколько нулей оканчивается 26! ?

9.

На фабрике работают 23 служащих.

а): бешеный директор хочет дать одному служащему премию, а другому выговор.
б): бешеный директор хочет дать двум служащим по выговору.
в): бешеный директор хочет дать трём служащим по выговору.
г): бешеный директор хочет дать десяти служащим по выговору.
Сколько вариантов выбрать счастливщиков у директора?

10.

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

11.

Доктор Ватсон должен отдежурить в больнице 6 дней в месяц. Сколько для него возможно различных вариантов расписания дежурств на июнь (в котором, как известно, 30 дней)?

12.

Сколько различных чисел можно составить из 6 единиц и 24 двоек?

13.

Сколькими способами на доске 7×9 можно поставить пару ладей, которые не бьют друг друга?

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!