В футбольном турнире, проходящем в один круг (каждая команда должна сыграть с каждой ровно по одному разу), играют 30 команд. В некоторый момент турнира тренер команды $A$ заметил, что любые две команды, отличные от $A$, сыграли разное количество игр. Какое наибольшее количество игр к этому моменту могла сыграть команда $A$?
Ответ:
Решение:
У Ольги есть конфеты $30$ сортов. Она хочет выложить конфеты по кругу так, чтобы для любых двух сортов нашлись рядом лежащие конфеты этих сортов. Какого наименьшего количества конфет ей для этого хватит?
Ответ:
Решение:
У Олега есть конфеты 32 сортов. Он хочет выложить конфеты в ряд так, чтобы для любых двух сортов нашлись рядом лежащие конфеты этих сортов. Какого наименьшего количества конфет ему для этого хватит?
Ответ:
Решение:
У Олега есть конфеты $16$ сортов. Он хочет выложить конфеты в ряд так, чтобы для любых двух различных сортов нашлись рядом лежащие конфеты этих сортов. Какого наименьшего количества конфет ему для этого хватит?
Ответ:
Решение:
Имеется палитра из нескольких различных оттенков цветов. Известно, что все оттенки из неё кроме сиреневого сочетаются с разными количеством других оттенков палитры (включая сиреневый), а сиреневый сочетается ровно $13$-ю. Какое наименьшее количество оттенков может быть в такой палитре?
Ответ:
Решение:
Двести школьников собирают наклейки, среди которых есть наклейки редких видов. Оказалось, что у каждого школьника есть наклейки ровно двух редких видов, и для каждого редкого вида наклеек найдётся школьник, у которого есть наклейка такого вида. Также известно, что каких бы $10$ школьников ни взять, найдётся редкий вид наклеек такой, что его нет ни у кого из этих $10$ школьников. При каком наименьшем количестве редких видов наклеек такая ситуация возможна?
Ответ:
Решение:
К середине XXII века человечество освоило $100$ обитаемых планет в других звездных системах. От каждой планеты расходится $40$ гиперпространственных порталов, и к каждой планете ведёт $40$ порталов от других планет. Все порталы строго односторонние, т. е. если есть портал, ведущий из $A$ в $B$, то нет портала, ведущего из $B$ в $A$. Мистер Риггз хочет добраться с Галатеи-37 на Пандору за наименьшее число гиперпространственных прыжков. Сколько прыжков ему может потребоваться (укажите все варианты)?
Ответ:
Решение:
В первенстве по футболу участвует $20$ команд, которые играют по разу друг с другом. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трёх команд нашлись две, уже сыгравшие между собой?
Ответ:
Решение:
На собрание пришло $n$ человек ($n\gt 1$). Оказалось, что у любых двух из них есть среди собравшихся ровно два других общих знакомых.
а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.
б) Покажите, что $n$ может быть больше $4$.
а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.
б) Покажите, что $n$ может быть больше $4$.
Ответ:
Решение:
В шахматном турнире каждый участник встретился с каждым один раз. В каждом туре каждый участник проводил по одной встрече. Не меньше чем в половине всех встреч оба участника были земляками (из одного города). Докажите, что в каждом туре была хотя бы одна встреча между земляками.
Ответ:
Решение:
В некоторой стране есть 100 городов, которые связаны такой сетью дорог, что из любого города в любой другой можно проехать только одним способом без разворотов. Схема сети дорог известна, развилки и перекрестки сети необязательно являются городами, всякая тупиковая ветвь сети обязательно заканчивается городом. Навигатор может измерить длину пути по этой сети между любыми двумя городами. Можно ли за 100 таких измерений гарантированно определить длину всей сети дорог?
Ответ:
Решение:
В турнире по теннису (где не бывает ничьих) участвовало более 4 спортсменов. Каждый игровой день каждый теннисист принимал участие ровно в одной игре. К завершению турнира каждый сыграл с каждым в точности один раз. Назовём игрока упорным, если он выиграл хотя бы один матч и после первой своей победы ни разу не проигрывал. Остальных игроков назовём неупорными. Верно ли, что игровых дней, когда была встреча между неупорными игроками, больше половины?
Ответ:
Решение:
В Камелот съехались $100$ рыцарей Круглого Стола, любые два из которых либо дружат, либо враждуют (дружба и вражда взаимны). Фея Моргана может выбрать любого рыцаря и сделать так, что он поссорится со всеми своими друзьями и при этом подружится со всеми своими врагами. Накладывать это заклинание Моргана может сколько угодно раз. Докажите, что она сможет добиться того, чтобы в итоге образовались такие две группы по $5$ рыцарей, что каждый рыцарь из первой пятёрки будет враждовать с каждым рыцарем из второй.
Ответ:
Решение:
В классе, состоящем из $k\geqslant 5$ учеников (девочек и мальчиков), провели контрольную работу. Известно, что во время работы каждая пара школьников пообщалась и ровно один из учеников в этой паре помог другому. В результате оказалось, что для каждого ученика среди тех, кому он помог, поровну девочек и мальчиков. Сколько учеников могло быть в классе?
Ответ:
Решение:
Графом называют конечное множество точек вместе с линиями, соединяющими некоторые из этих точек. Точки называют вершинами графа, а соединяющие их линии — рёбрами (некоторые рёбра могут быть замкнутыми линиями, соединяющими вершину с собой).
На координатной плоскости задан отрезок \[ x=0,\quad |y|\leqslant5 \] и окружности \[ (x-3)^2+y^2=25,\quad (x+3)^2+y^2=25,\quad (x-7)^2+y^2=1,\quad (x-6)^2+y^2=4. \] Вершинами графа являются концы отрезка, а также точки пересечения и касания этих окружностей. Рёбрами этого графа являются части указанных выше линий, соединяющих его вершины.
Сколькими способами можно начертить все ребра этого графа одним росчерком, не отрывая карандаш от бумаги и не проводя более одного раза по одному и тому же ребру?
На координатной плоскости задан отрезок \[ x=0,\quad |y|\leqslant5 \] и окружности \[ (x-3)^2+y^2=25,\quad (x+3)^2+y^2=25,\quad (x-7)^2+y^2=1,\quad (x-6)^2+y^2=4. \] Вершинами графа являются концы отрезка, а также точки пересечения и касания этих окружностей. Рёбрами этого графа являются части указанных выше линий, соединяющих его вершины.
Сколькими способами можно начертить все ребра этого графа одним росчерком, не отрывая карандаш от бумаги и не проводя более одного раза по одному и тому же ребру?
Ответ:
Решение:
В группе из $80$ человек некоторые знакомы друг с другом (знакомства взаимны). Известно, что в группе есть человек, который знает ровно $1$ из оставшихся, человек, который знает ровно $2$ из оставшихся, …, человек, который знает ровно $54$ из оставшихся. Докажите, что в группе есть три человека, каждые два из которых знакомы.
Ответ:
Решение:
В классе $24$ ученика, у каждого ровно $3$ друга среди одноклассников. Однажды на каникулах $6$ учеников подписались на канал по олимпиадной математике. После этого ученики стали общаться между собой. Когда ученик узнаёт, что хотя бы двое из его друзей уже подписались на канал, он также подписывается на этот канал. Могло ли в итоге случиться, что весь класс подписался на канал?
Ответ:
Решение:
На плоскости отметили $4n$ точек, после чего соединили отрезками все пары точек, расстояние между которыми равно $1$ см. Оказалось, что среди любых $n+1$ точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее $7n$ отрезков.
Ответ:
Решение:
Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества $\{1, 2, 3, \ldots, 2^k\}$, а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.
Ответ:
Решение:
В королевстве некоторые пары городов соединены железной дорогой. У короля есть полный список, в котором поименно перечислены все такие пары (каждый город имеет свое собственное имя). Оказалось, что для любой упорядоченной пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, а король не заметил бы изменений. Верно ли, что для любой пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, второй город оказался названным именем первого города, а король не заметил бы изменений?
Ответ:
Решение: