В классе $24$ ученика, у каждого ровно $3$ друга среди одноклассников. Однажды на каникулах $6$ учеников подписались на канал по олимпиадной математике. После этого ученики стали общаться между собой. Когда ученик узнаёт, что хотя бы двое из его друзей уже подписались на канал, он также подписывается на этот канал. Могло ли в итоге случиться, что весь класс подписался на канал?
Ответ:
Решение:
На плоскости отметили $4n$ точек, после чего соединили отрезками все пары точек, расстояние между которыми равно $1$ см. Оказалось, что среди любых $n+1$ точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее $7n$ отрезков.
Ответ:
Решение:
Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества $\{1, 2, 3, \ldots, 2^k\}$, а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.
Ответ:
Решение:
В королевстве некоторые пары городов соединены железной дорогой. У короля есть полный список, в котором поименно перечислены все такие пары (каждый город имеет свое собственное имя). Оказалось, что для любой упорядоченной пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, а король не заметил бы изменений. Верно ли, что для любой пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, второй город оказался названным именем первого города, а король не заметил бы изменений?
Ответ:
Решение:
У повара в подчинении десять поварят, некоторые из которых дружат между собой. Каждый рабочий день повар назначает одного или нескольких поварят на дежурство, а каждый из дежурных поварят уносит с работы по одному пирожному каждому своему недежурящему другу. В конце дня повар узнает количество пропавших пирожных. Сможет ли он за $45$ рабочих дней понять, кто из поварят дружит между собой, а кто нет?
Ответ:
Решение:
В стране лингвистов существует $n$ языков. Там живет $m$ людей, каждый из которых знает ровно три языка, причём для разных людей эти наборы различны. Известно, что максимальное число людей, любые два из которых могут поговорить без посредников, равно $k$. Оказалось, что $11n\leqslant k\leqslant m/2$. Докажите, что тогда в стране найдутся хотя бы $mn$ пар людей, которые не смогут поговорить без посредников.
Ответ:
Решение:
В Чикаго орудует $36$ преступных банд, некоторые из которых враждуют между собой. Каждый гангстер состоит в нескольких бандах, причём любые два гангстера состоят в разных наборах банд. Известно, что ни один гангстер не состоит в двух бандах, враждующих между собой. Кроме того, оказалось, что каждая банда, в которой не состоит некоторый гангстер, враждует с какой-то бандой, в которой данный гангстер состоит. Какое наибольшее количество гангстеров может быть в Чикаго?
Ответ:
Решение:
На олимпиаду пришло 2018 участников, некоторые из них знакомы между собой. Будем говорить, что несколько попарно знакомых участников образуют «кружок», если любой другой участник олимпиады не знаком с кем-то из них. Докажите, что можно рассадить всех участников олимпиады по 90 аудиториям так, что ни в какой аудитории не будут сидеть все представители какого-либо «кружка».
Ответ:
Решение:
Андрей Михайлович выписал на доску все возможные последовательности длины $2022$, состоящие из $1011$ нулей и $1011$ единиц. Назовём две последовательности совместимыми, если они совпадают ровно в $4$ позициях. Докажите, что Андрей Михайлович может разбить все последовательности на $20$ групп так, чтобы никакие две совместимые последовательности не попали в одну группу.
Ответ:
Решение:
В выпуклом многограннике обозначим через В, Р и Т соответственно число вершин, рёбер и максимальное число треугольных граней, которые имеют общую вершину. Докажите, что $\text{В}\sqrt{\text{Р}+\text{Т}}\geqslant 2\text{Р}$.
Например, для тетраэдра ($\text{В}=4$, $\text{Р}=6$, $\text{Т}=3$) выполняется равенство, а для треугольной призмы ($\text{В}=6$, $\text{Р}=9$, $\text{Т}=1$) или куба ($\text{В}=8$, $\text{Р}=12$, $\text{Т}=0$) имеет место строгое неравенство.
Например, для тетраэдра ($\text{В}=4$, $\text{Р}=6$, $\text{Т}=3$) выполняется равенство, а для треугольной призмы ($\text{В}=6$, $\text{Р}=9$, $\text{Т}=1$) или куба ($\text{В}=8$, $\text{Р}=12$, $\text{Т}=0$) имеет место строгое неравенство.
Ответ:
Решение:
Петя и Вася независимо друг от друга разбивают белую клетчатую доску $100\times 100$ на произвольные группы клеток, каждая из чётного (но не обязательно все из одинакового) числа клеток, каждый — на свой набор групп. Верно ли, что после этого всегда можно покрасить по половине клеток в каждой группе из разбиения Пети в чёрный цвет так, чтобы в каждой группе из разбиения Васи было поровну чёрных и белых клеток?
Ответ:
Решение:
$20$ школьников записываются на кружки по физике, математике и информатике. Каждый школьник может записаться на любое количество из этих трёх кружков, но обязан выбрать хотя бы один из них. Известно, что на информатику записались $13$ школьников, на физику — $10$ школьников, а $9$ человек записались на математику. Оказалось, что ровно $9$ человек записались не менее чем на $2$ кружка сразу. Найдите количество учеников, выбравших все три кружка.
Ответ:
Решение:
Футбольный мяч шьётся из 32 кусочков кожи: белых шестиугольников и чёрных пятиугольников. Каждый чёрный кусочек граничит только с белыми кусочками, каждый белый кусочек граничит с тремя чёрными и тремя белыми. Сколько чёрных кусочков нужно для изготовления мяча?
Ответ:
Решение:
Найдите количество натуральных чисел, кратных $3$, не кратных $5$ и принадлежащих отрезку $[1200;2020]$.
Ответ:
Решение:
На доске выписали в порядке возрастания все натуральные числа от $1$ до $10000$, а потом стёрли те, которые не делятся ни на $4$, ни на $15$. Какое число оказалось на $2017$-м месте?
Ответ:
Решение:
В большую коробку положили $10$ коробок поменьше. В некоторые из них положили $10$ коробок ещё поменьше. В некоторые из этих последних коробок положили $10$ коробок ещё меньшего размера и так далее. В результате оказалось, что имеется ровно $2000$ коробок, в которых что-то лежит. Какое наибольшее число коробок могут при этом быть пустыми?
Ответ:
Решение:
Сколько существует способов переставить местами буквы $abcabe$ так, чтобы никакие две одинаковые буквы не стояли рядом?
Ответ:
Решение:
Дано множество чисел $M=\{2024, 2025, \ldots, 2031\}$. Для каждого непустого подмножества множества $M$ (включая само множество $M$) вычислили сумму чисел, входящих в это подмножество, а затем все эти суммы сложили, получив число $S$. На какое двузначное число заканчивается $S$?
Ответ:
Решение:
Найдите количество пар таких натуральных чисел $a$ и $b$, что $a$ — трёхзначное, $b$ — четырёхзначное, а их произведение делится на $35$.
Ответ:
Решение:
В летнем лагере в первую смену отдыхали $57$ школьников. За время отдыха $27$ ребят читали книги, $25$ ловили рыбу, $26$ собирали грибы, при этом каждый школьник принял участие хотя бы в одном из этих дел. Известно, что $9$ из читающих ребят собирали грибы, $8$ грибников успели сходить на рыбалку. Сколько ребят читали книги, ходили на рыбалку, но не собирали грибы? Какое максимальное число ребят могли, при этих условиях, собирать грибы, но не читать книг и не ловить рыбу.
Ответ:
Решение: