За круглым столом
*
Двадцать четыре участника важных переговоров проводят заседания за круглым столом, сидя на одинаковом расстоянии друг от друга. Место каждого участника за столом указано карточкой с его именем. Как-то раз после бурного обсуждения в кулуарах одного из пунктов повестки дня участники переговоров, сев за стол, обнаружили, что по ошибке каждый из них занял не своё место. Точное расположение участников за столом неизвестно. Можно ли тем не менее повернуть стол так, чтобы по крайней мере двое из участников переговоров оказались против карточек с их именами?
Если изначально ни один из участников переговоров не сидит напротив карточки со своим именем, то стол можно повернуть так, чтобы по крайней мере двое из них оказались «на своём месте».
Поворачивая стол по часовой стрелке каждый раз на 1/24-ю часть окружности, мы получим 23 различных положения стола, отличных от начального. При этом для каждого из участников переговоров будет существовать ровно одно положение стола, при котором он окажется сидящим напротив карточки со своим именем. Но так как участников 24, а различных положений стола всего 23 (в начальном положении, как мы помним, все участники переговоров сидят не на своих местах), то существует как минимум одно положение стола, в котором по меньшей двое участников окажутся сидящими напротив своих карточек.
Использованный при доказательстве подход носит название принцип Дирихле. Его объяснение обычно сводят к примеру кроликов в клетках: если в n клетках сидит не менее n+1 кролика, то хотя бы в одной клетке находится более одного кролика. Этот очень простой и даже нескоьлко наивный принцип позволяет иногда решать весьма трудные задачи.
Комментарии
A fascinating discussion is worth comment. Th&e8e#r217;s no doubt that that you should write more about this subject, it might not be a taboo matter but typically folks don’t discuss these topics. To the next! Many thanks!!
Добавить комментарий