Шесть разгневанных мужчин

*

Сложность: 

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

Решение

Рассмотрим любого из этих людей. Очевидно, что среди пяти остальных у него есть либо трое знакомых, либо трое незнакомых. Не теряя общности, можно считать, что он знаком по крайней мере с тремя другими: A, B и C. Если хоть какие-то два из них знакомы между собой, то мы получаем тройку попарно знакомых людей. Если же они все незнакомы между собой, то мы получаем тройку попарно незнакомых: A, B и C.




Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.