Question

В офисе Тинькофф работают 2022 человека. На данный момент все сотрудники занимаются nn проектами. Известно, что для любых двух проектов не больше 2018 сотрудников работают по крайней мере над одним из них. Но при этом для любых трёх проектов каждый сотрудник работает хотя бы над одним. Найдите наибольшее возможное значение nn.​

Answer 1

Ответ:

Бро есть ответ?

Пошаговое объяснение:

Answer 2

Давайте рассмотрим эту задачу более подробно.

У нас есть 2022 сотрудника и nn проекта. Для любых двух проектов не более 2018 сотрудников работают хотя бы над одним из них, это означает, что каждый сотрудник может работать максимум над одним из nn проектов - 1 проектом.

Теперь давайте рассмотрим условие, что для любых трёх проектов каждый сотрудник работает хотя бы над одним. Это означает, что сумма уникальных сотрудников, работающих над каждым из трех проектов, должна быть равна или больше 2022 (всего сотрудников). Если мы рассматриваем 3 проекта и каждый сотрудник работает хотя бы над одним из них, то в сумме они покроют всех сотрудников. Таким образом, сумма уникальных сотрудников для каждых трех проектов равна 2022.

Теперь мы можем воспользоваться неравенством Пиджака (также известным как теорема Суммы Холла), которое утверждает, что если есть nn множеств (в данном случае проектов) и для каждой пары множеств из nn множеств мы имеем не менее m (в данном случае 2018) элементов, то существует паросочетание, которое покрывает все nn множества.

Исходя из этого, мы можем записать:

2018 * nn >= C(2022, 2) - это условие для пар множеств проектов. 2018 * nn >= 2022 - это условие для троек множеств проектов.

Где C(n, k) - это биномиальный коэффициент, равный числу способов выбрать k элементов из n элементов. В данном случае, мы выбираем 2 элемента из 2022 для первого условия и 3 элемента из 2022 для второго условия.

Теперь мы можем решить эти неравенства:

Для первого условия: 2018 * nn >= C(2022, 2) 2018 * nn >= (2022 * 2021) / 2 nn >= (2022 * 2021) / (2 * 2018) nn >= 2053.5

Для второго условия: 2018 * nn >= 2022 nn >= 2022 / 2018 nn >= 1.002

Итак, наибольшее возможное значение nn равно 2, так как это минимальное целое число, удовлетворяющее обоим условиям. Таким образом, наибольшее возможное значение nn равно 2.