Question

В офисе работают 180 человек. Выяснилось, что для k любых (k— некое фиксированное число, k∈N) людей в офисе найдутся двое (отличных от них) незнакомых сотрудников, каждый из которых знает любого из этих. При каком наибольшем k так могло случиться?

Answer 1

Ответ: k=15 человек

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

Answer 2

Данная задача связана с теорией графов и принципом Дирихле, который утверждает, что если n + 1 объектов распределены по n ящикам, то как минимум в одном ящике будет находиться не менее двух объектов.

В данном случае мы можем рассматривать каждого человека в офисе как вершину графа, а знание между двумя людьми можно представить ребром, соединяющим эти вершины. Из условия задачи следует, что для любого набора из k человек найдутся двое незнакомых сотрудников, каждый из которых знает любого из этих k человек.

Теперь давайте рассмотрим ситуацию, когда в офисе есть k человек. Всего возможно C(180, k) способов выбрать k человек из 180. Если для каждого из этих C(180, k) наборов найдутся двое незнакомых сотрудников, каждый из которых знает любого из этих k человек, то мы найдем наибольшее возможное значение k.

Но заметим, что в каждом наборе из k человек существует только k*(180-k) ребер, соединяющих их со всеми остальными сотрудниками в офисе. Таким образом, чтобы все эти k*(180-k) ребер были различными, должно выполняться условие:

k*(180-k) >= C(180, k)

Чтобы найти наибольшее возможное значение k, которое удовлетворяет этому неравенству, нужно перебрать все значения k от 1 до 180 и найти первое значение, для которого неравенство выполняется.

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