На некотором пространстве под землёй живут 20 кротов, каждый - в своей пещере-жилище. чтобы общаться друг с другом, не вылезая на поверхность, кроты прорыли между своими жилищами 91 тоннель. каждый тоннель соединяет только два жилища, тоннели не пересекаются, и никакие два тоннеля не соединяют одну и ту же пару жилищ. докажите , что есть крот , который может по вырытым тоннелям переползать в жилища не менее чем 10 других кротов ( посещая, возможно, по пути другие жилища)

Для решения этой задачи мы будем использовать принцип Дирихле, также известный как принцип ящика со шарами.

Итак, у нас есть 20 кротов и 91 тоннель, каждый из которых соединяет два жилища. Давайте предположим, что ни один из кротов не может посетить 10 и более жилищ, используя тоннели.

Тогда мы можем разделить наши 20 кротов на несколько групп, где каждая группа состоит только из кротов, которые могут посещать не более 9 жилищ. Заметим, что каждый крот принадлежит ровно одной такой группе.

Поскольку у нас есть 20 кротов и каждая группа содержит не более 9 кротов, то по принципу Дирихле должна существовать хотя бы одна группа, содержащая более 2 кротов.

Допустим, у нас есть группа, в которой n кротов не может посетить более 9 жилищ. Тогда это означает, что в этой группе есть n(n-1)/2 пар кротов, которые не могут связываться напрямую через тоннели. Но у нас есть всего 91 тоннель, то есть не больше чем 91 пара кротов может быть разделена.

Если ни одна из этих 91 пары кротов не попадает в нашу группу, где n > 2, то, поскольку у нас есть 91 пар кротов, мы должны иметь как минимум 92 группы, где n <= 2, для каждой пары кротов. Но так как у нас всего 20 кротов, это невозможно.

Таким образом, наше предположение неверно, и существует крот, который может посетить 10 и более жилищ, используя тоннели.