Физтех 2024, отборочный этап, 10 класс, первый тур, задача 7

На факультете учится студентов. До зачёта каждые два студента встретились хотя бы на одной лекции по истории. При этом на каждой лекции по истории было не больше студентов. Какое наименьшее число лекций по истории могло пройти до зачёта?

Ответ

Ответ. .

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

Покажем, что если лекций не больше , то найдутся два студента, которые не встретились на лекциях. Действительно, количество «посещений» лекций студентами было не больше . Так как студентов , найдётся студент, который посетил не более лекций. Но на каждой лекции он встретил не более других студентов, значит, всего не более из остальных .

Похожие задачи

Физтех 2025, отборочный этап, 9 класс, второй тур, задача 9

Дано множество чисел M={2024,2025,ldots,2031}. Для каждого непустого подмножества множества M (включая само множество M) вычислили сумму чисел, входящих в это подмножество, а затем все эти суммы сложили, получив число S. На какое двузначное число заканчивается S?

Сложная

Комбинаторика

Физтех 2024, отборочный этап, 9 класс, второй тур, задача 8

Клетки доски размером 21 × 13 раскрасили в чёрный и белый цвета так, что среди любых двух клеток, имеющих общую сторону, есть хотя бы одна чёрная. Какое наименьшее количество чёрных клеток может быть на доске?

Сложная

Комбинаторика

Физтех 2025, отборочный этап, 11 класс, третий тур, задача 10

Каждый из 11 учеников записал к себе в тетрадь какие-то натуральные числа, не превосходящие N. Оказалось, что если взять любых 6 учеников, то в их тетрадях можно найти любое натуральное число, не превосходящее N, а если взять любых 5 учеников — нет (то есть найдётся число, которого нет ни в одной те

Сложная

Комбинаторика

Физтех 2025, отборочный этап, 9 класс, первый тур, задача 8

Сколько существует способов переставить местами буквы abcabe так, чтобы никакие две одинаковые буквы не стояли рядом?

Сложная

Комбинаторика