22. Задачка с 22 утюМа.

В группе из n^2 человек каждый имеет не более n знакомых среди остальных. Докажите, что можно выбрать n человек, никакие двое из которых не знакомы друг с другом.

В младших лигах было n=10.

Решение. Рассмотрим граф-дополнение. В нем степень каждой вершины не менее n^2-n-1. Значит, ребер не меньше, чем n^2(n^2-n-1)/2.

В графе с v вершинами, где нет K_n, максимальное количество ребер, согласно лемме Турана, равно (n-2)(v^2-r^2)/(2n-2)+r(r-1)/2,

где r- остаток при делении v на n-1.

В нашем случае v=n^2, r=1. Значит, максимальное количество ребер равно

(n-2)(n^4-1)/(2n-2)=(n^4-n^3-n^2-n-2)/2<(n^4-n^3-n^2)/2.

Таким образом, в графе-дополнении есть подграф K_n.

23. Задачка с 18 УТЮМа. Предлагалась школьникам на карусели!!!

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

Решение. Воспользуемся леммой.

Лемма. Число транзитивных троек в турнире с набором количества очков (s_1, s_2, ..., s_n) равно s_1*(s_1-1)/2+s_2*(s_2-1)/2+...+s_n*(s_n-1)/2.

Итак, в нашем турнире 17*7*6/2 транзитивных троек. И 15*14*13/(1*2*3) всего троек. Таким образом, троек команд, которые во встречах между собой одержали по одной победе равно 140.

24. Задачка с 16 УТЮМа.

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

Решение. Рассмотрим город a, из которого выходит хотя бы две дороги. Если есть дорога, которая из a идет в другой город, из которого выходит хотя бы две дороги, то закроем эту дорогу. Если такого сделать нельзя, то оставшийся граф разбит на компоненты связности K_{1,n}. А в таком графе не меньше двух третей вершин являются висячими.

25. Задачка с 28 УТЮМа.

В день Св. Валентина n влюбленных пар провели два однокруговых турнира по пинг-понгу - один для юношей и один для девушек. Юноша и девушка из каждой пары выиграли n-1 игру. Докажите, что количество троек юношей (A,B,C), в которых A выиграл у B, B выиграл у C, а C обыграл A, равно количеству таких троек девушек.

Решение. Занумеруем пары. Пусть юноши выиграли соответственно s_1, s_2, ..., s_n игр. Тогда девушки проиграли s_1,s_2, ..., s_n игр.

Количество транзитивных троек у юношей (считаем тройки, в которых соответствующие юноши выиграли) равно

s_1*(s_1-1)/2+s_2*(s_2-1)/2+...+s_n*(s_n-1)/2.

Количество транзитивных троек у девушек (считаем тройки, в которых соответствующие девушки проиграли) равно

s_1*(s_1-1)/2+s_2*(s_2-1)/2+...+s_n*(s_n-1)/2.

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



26. Задачка с 35 утюМа.

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

Решение. Рассмотрим граф-дополнение. Задача для него будет переформулирована следующим образом:

В группе из 2n+1 человек нет троих, которые попарно друзья. Докажите, что найдется n+1 человек из этой группы, у каждого из которых не более n друзей.

Предположим противное. Пусть найдется n+1 человек, у которых не меньше n+1 друзей.

Среди них найдутся два друга, потому что если бы не нашлись, то все ребра от этих n+1 вершин шли бы только в оставшиеся n вершин, и степень не оказалась бы такой большой.

Из этих двух вершин выходит по n ребер к оставшимся 2n-1 вершине. Значит, есть вершина, смежная с ними обеими. Получили противоречие.

27. Задачка с 13 УТЮМа.

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

Решение. Граф знакомств, очевидно, связный. Значит, в нем не менее 1998 ребер.

Приведем пример графа с таким числом ребер. Рассмотрим одного, который знаком со всеми остальными, а других знакомств нет. Такой граф удовлетворяет условию.

28. В поселке некоторые дома соединены проводами. Соседями называются двое, дома которых соединены проводом. Всегда ли удастся поселить в каждый дом по одному человеку, лжецу или рыцарю, так, чтобы на вопрос: "Есть ли среди ваших соседей лжецы?" каждый ответил положительно?

Решение. Возьмем какой-нибудь дом и поселим в него лжеца.

Во все соседние дома поселим рыцарей.

Возьмем какой-нибудь дом, соседний с рыцарским, если такой есть. А если нет, то любой из оставшихся домой. Поселим туда лжеца.

Во все соседние дома поселим рыцарей. И т.д.

29. Задачка с 12 УТЮМа.

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

Решение. Пусть нет такого ученика. Тогда у каждого не более 7 друзей. Возьмем двоих, которые не дружат. Останется 15 учеников. Найдется хотя бы 15-7*2=1 ученик, который не дружит с ними обоими. Таким образом, найдется трое учеников, которые попарно не дружат. Получили противоречие.

30. Задачка с 27 УТЮМа. Правда, там не 2011, а другое число. :)

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

Решение. Пусть найдется три вершины, степени которых не больше 62.

Теперь надо взять три эти вершины a, b, c и рассмотреть всевозможные случаи соединения ребер между ними.

а) Если они попарно несмежны, то условие задачи не выполнено.

б) Если они попарно смежны, то найдутся вершины d, e, f, что a не смежна с d, b не смежна с e, c не смежна с f, и опять условие задачи не выполнено.

в) Если a смежна с b, то найдутся вершины d и e, которые не смежны с a и вершина f, которая не смежна с b, и снова условие задачи не выполнено.

г) Если a смежна с b и c, но b и c не являются смежными, то найдутся вершины d, e, f, что a не смежна с d, b не смежна с e, c не смежна с f, и опять условие задачи не выполнено.

Таким образом, у хотя бы 64 вершин степень не меньше 63. Значит, ребер не меньше 64*63.2=2016.

31. В замке живут N рыцарей. Любые двое из них либо дружат, либо враждуют. Ни один из рыцарей не дружит с врагом своего друга, и каждый рыцарь имеет ровно трех врагов. Найдите все N, при которых это возможно.

Решение. Если ни у кого нет друзей, то N=4.

Если есть пара друзей, то они входят в клику (полный подграф). И у каждого из них по три врага. Но каждый из врагов враждует также с тремя. Значит, N=3+3=6.

32. Задачка с 9 УТЮМа.

На первом занятии танцевального кружка пришли школьники, каждый из которых знает ровно трех других. Руководитель кружка хочет расставить несколько человек в круг, чтобы каждый знал своих соседей справа и слева. Он понял, что ни трех, ни четырех школьников расставить таким образом ему не удастся. Чему равно наименьшее возможное число участников кружка?

Решение. Рассмотрим какую-нибудь вершину. Скажем, что она на первом уровне.

Три смежные вершины на втором уровне. Если на втором уровне есть ребро-знакомство, то есть C_3, что противоречит условию.

Со второго уровня на третий идет шесть ребер, т.е. на нем не больше шести вершин. Но если вершин меньше, то есть C_4.

Значит, в нашем графе не меньше 1+3+3*2=10 вершин.

Примером является граф Петерсона.

33. Задачка с 6 УТЮМа.

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

Решение. Построим граф следующим образом. Будем соединять ребром две вершины-писателей, если они не читали произведений друг друга. В этом графе каждая вершина имеет степень хотя бы 15. Значит, в этом графе не меньше 22*15/2=165 ребер.

А если в графе нет K_4, то по лемме Турана в нем не больше [22^2/3]=161 ребер.

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

35. Задачка с 17 УТЮМа

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

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

36. Задачка с 7 УТЮМа.

Кузя прямолинейным разрезом разделил выпуклый бумажный 67-угольник на два, затем так же разрезал один из двух получившихся, затем 0 один из трех получившихся и т.д. В итоге у него получилось 8 n-угольников. Чему может равняться n?

Решение. Восемь треугольников получить легко можем, просто их отрезав с краев. Ну, а что останется, то останется. :)

Рассмотрим случай n>3. Тогда у нас 8 n-угольников и x еще каких-то многоугольников, минимум из трех сторон. Применим формулу Эйлера. У нас В=67, Г=8+x, Р>=(8n+3x+67)/2.

2=В-Р+Г<= 67-(8n+3x+67)/2+(8+x), откуда 8n+x<=79, т.е. n<=9.

Если мы возьмем x треугольников, то равенства будут достигаться, и примеры будут для всех указанных n.

37. Задачка с районного тура Московской областной олимпиады 1994-95 учебного года, 10 класс.

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

Решение. Найдется команда, которая выиграла хотя бы 6 матчей. Выберем эту команду.

Осталось 12-(6+1)=5 команд. В подтурнире среди них найдется команда, выигравшая 2 матча. Выберем эту команду. Осталось 5-(2+1)=2 команд. Выберем эту команду.

Ура! Эти три команды удовлетворяют условию.

38. Задачка была на областной олимпиаде, 10 класс, 1996-97 учебный год.

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

Решение. Пусть в графе G степени вершин d_1, d_2, ..., d_n.

Тогда число подграфов K_{r,1} в графе G равно C_{d_1}^r+C_{d_2}^r+...+C_{d_n}^r.

Если граф G не содержит полного двудольного графа K_{r,s} в качестве подграфа, то у каждых r вершин может быть не более s-1 общих соседей, и общее число "ёжиков" K_{r,1} не может превышать величины (s-1) C_n^r.

В нашей задаче r=s=3, n=20, d_1=d_2=...=d_n=10.

20*С_10^3=2400 > (3-1)C_20^3=2280

Получили противоречие. Значит, в нашем графе есть K_{3,3}.

39. Задачка с 25 УТЮМа.

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

40. Задачка с областной олимпиады 2000/01 учебного года, 9 класс.

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

Решение. Докажем индукцией по числу вершин. База n=2 очевидна.

Пусть при n=k доказано. Рассмотрим дерево с k+1 вершиной. Пусть вершин в первой доле не меньше, т.е. |X_1|>=|X_2|.

Если висячая вершина была во первой доле, то всё хорошо.

Предположим, что все висячие вершины во второй доле. Удалим какую-нибудь висячую вершину и соответствующее висячее ребро. Станет дерево, в котором на одну вершину меньше, а в первой доле вершин строго больше, и мы можем применить предположение индукции. В первой доле есть висячая вершина. Если она была и до удаления этого ребра, то опять же всё хорошо.

Но вдруг она появилась только сейчас, при удалении ребра. Тогда удалим и её.

Получится граф, в котором k-1 вершина, и по предположении индукции в первой части есть висячая вершина. Но она висячая и в исходном графе!

41. Задачка с областной олимпиады 1996/97 учебного года, 9 класс.

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

Решение. Рассмотрим соответствующий орграф. Степени исхода и захода у каждой вершины равна 1. Значит, граф разбивается на контуры. В контуре по второму условию должно быть хотя бы по 4 вершины. Чтобы попугаев из контура нельзя было рассадить поровну по клеткам, нужны контуры нечетной длины, т.е. длины хотя бы 5. Но если их семь штук, то останется контур длины 3, что нехорошо. Значит, нечетных контуров длины хотя бы 5 не больше шести. Пусть удав съест в каждом нечетном контуре по одной вершине-попугаю, после чего остальные вершины из контура разбиваются поровну на две клетки.

42. Задачка с областной олимпиады 1994/95 года; 10, 11 классы.

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

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