В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Подробнее
а) Двое играют в такую игру. Первый записывает один под другим два ряда по 10 чисел так, чтобы выполнялось следующее правило: если число $b$ записано под числом $a$, а число $d$ - под числом $c$, то $a + d = b + c$. Второй игрок, зная это правило, хочет определить все написанные числа. Ему разрешается задавать первому игроку вопросы типа «Какое число стоит в первой строке на третьем месте?» или «Какое число стоит во второй строке на девятом месте?» и т. п. За какое наименьшее число таких вопросов второй игрок сможет узнать все числа?
б) В таблице $m \times n$ записаны числа так, что для любых двух строк и любых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Часть чисел стерли, но по оставшимся можно восстановить стертые. Докажите, что осталось не меньше чем $m + n - 1$ чисел.
Подробнее
Доказать, что в любой компании число тех, кто знаком с нечетным числом членов компании, четно.
Подробнее
Каждый из участников турнира встретился по одному разу со всеми остальными участниками, причем ни одна встреча не закончилась вничью. Доказать, что среди спортсменов найдется такой, кто назовет всех остальных участников турнира, если станет перечислять тех, кого победил он сам, и тех, кого победили побежденные им соперники.
Подробнее
Фабрика выпускает двухцветные ткани из пряжи шести различных цветов. В расцветках этих тканей каждый цвет сочетается по крайней мере с тремя другими. Доказать, что можно выбрать ткани трех различных расцветок, в которых будут представлены все шесть цветов.
Подробнее
Во время экскурсии выяснилось, что один из любых четырех ее участников встречался ранее с тремя остальными. Доказать, что среди любых четырех участников экскурсии всегда можно найти такого, который встречался ранее со всеми остальными экскурсантами.
Подробнее
Вдоль параллельных границ некоторой территории, имеющей форму квадрата со стороной 10 км, проложены автострады. На территории размещены 4 наблюдательных поста. Требуется построить подъездные дороги из отрезков, параллельных сторонам квадрата, так, чтобы из каждого наблюдательного поста можно было добраться на велосипеде до каждой автострады (по автостраде ездить на велосипеде воспрещается).
Доказать, что независимо от того, где расположены наблюдательные посты, всегда можно построить подъездные пути общей протяженностью не более 25 км (при некоторых расположениях наблюдательных постов меньшая протяженность подъездных путей может оказаться недостаточной).
Подробнее
Допустим, что с помощью некоторой триангуляции мы разбили сферу на «страны». Здесь под триангуляцией мы понимаем такое разбиение сферы, при котором каждая получившаяся «страна» граничит (то есть имеет общий участок границы ненулевой длины) ровно с тремя остальными «странами». Вершину графа, состоящего из граничных линий, мы назовем четной или нечетной, если из нее выходит соответственно четное или нечетное число таких линий. Можно ли построить такую триангуляцию сферы, при которой получились бы ровно две нечетные вершины, причем эти вершины оказались бы смежными?
Подробнее