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

Кружок 9-11 классов

Графы, князья, халифы и прочая знать. 5 марта 2011 года

Задачки попроще

1.

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

Указание

Указание. Попробуйте посчитать количество пар знакомых.

2.

Каждый из 102 кроликов имеет не менее 68 знакомых. Докажите, что найдутся четверо, имеющие одинаковое число знакомых.

3.

Может ли случиться, что в компании из 11 девочек и 10 мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики — с одним и тем же числом девочек? А если девочек 10, а мальчиков 9?

Указание

Указание. То же самое.

4.

У каждого пациента спецлечебницы №1414 ровно один друг и ровно один враг. Докажите, что их можно разделить на две нейтральные палаты (дружба и вражда взаимные).

5.

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

Задачки посложнее

6.

Каждый из 750 народных любимцев оскорбил ровно одного из коллег за цвет верхней одежды. Докажите, что можно выбрать 250 любимцев, среди которых никто никого не оскорблял.

7.

a) Докажите, что среди любых 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. Докажите, что среди любых b) 10; c)* 9 человек найдутся либо трое попарно знакомых, либо четверо попарно незнакомых.

Указание

Указание. Выберем одного человека, тогда среди оставшихся пяти будет три человека, которых он знает, либо три человека, которых он не знает (а почему, кстати?).

8.

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

9.

Назовем пони малообщительным, если у него менее 10 знакомых. Назовем пони чудиком, если все его знакомые малообщительны. Докажите, что малообщительных пони не меньше, чем чудиков.

10.

Во дворе стоят несколько столбов, некоторые пары соединены проводами. Всего протянуто mn проводов, и эти провода раскрашены в n цветов, причем ни от какого столба не отходят провода одинакового цвета. Докажите, что можно перекрасить эти провода так, чтобы проводов всех цветов было поровну и по-прежнему ни от какого столба не отходили два провода одного цвета.

Задачки для знатоков

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

11.

В однокруговом турнире по волейболу участвовало n команд. Докажите, что их можно занумеровать числами от 1 до n так, что первая команда выиграла у второй, вторая у третьей, ..., (n − 1)-я команда у n-й.

12.

Маньяк Петр по одной перерезает веревочки волейбольной сетки, имеющей вид прямоугольника m×n. Какое наибольшее число веревочек может он разрезать до того, как сетка распадется на куски?

13.

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

14.

В компании из 20 человек среди любых трех есть двое незнакомых. Докажите, что в этой компании не более 100 пар знакомых.

Указание

Указание. Индукция по числу вершин.

15.

На плоскости нарисовано n точек. Двое по очереди соединяют их линиями так, чтобы линии не пересекались. Кто не может сделать ход, тот проиграл. Кто выигрывает при правильной игре?