В однокруговом (каждые два участника должны сыграть ровно один раз) шахматном турнире на 40 шахматистов в некоторый момент выяснилось, что в любой тройке шахматистов сыграно хотя бы две партии между ними. При каком наибольшем n можно гарантировать, что найдётся такое подмножество из n участников, что любые двое из них сыграли между собой?
Для решения данной задачи воспользуемся теорией графов. Мы можем представить шахматистов как вершины графа, а сыгранные партии между ними как рёбра. Условие задачи говорит о том, что в любой тройке шахматистов (вершин) сыграно хотя бы две партии (рёбра).
Обозначим количество шахматистов как
В графах, где в каждой т...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
