Если выбрать любых n человек, то найдется отличный от них человек, знакомый со всеми. Обозначим этого человека за A. При этом мы знаем, что у A есть знакомые в этих n человеках, но также мы знаем, что у A есть знакомые и с оставшимися n+1 людьми. Если мы рассмотрим любые другие n человек, не входящие в первую группу, то мы также найдем человека, отличного от них, но знакомого с каждым из них, и этот человек будет знаком с A. Поэтому мы можем сказать, что для любых n людей, не обязательно входящих в одну группу, найдется человек, знакомый со всеми из них, и знакомый с A.
Рассмотрим оставшиеся n+1 человек: по условию для них тоже найдется человек, отличный от них, но знакомый со всеми. Обозначим его за B. При этом мы знаем, что у B есть знакомые в этих n+1 людях, но также мы знаем, что у B есть знакомые и с A. Таким образом, мы имеем два человека A и B, знакомых со всеми людьми в компании.
Осталось рассмотреть два случая. Если A и B знакомы, то A знаком со всеми, и мы можем остановиться на этом. Если же A и B не знакомы, то у каждого из них есть хотя бы n+1 знакомых в оставшейся группе. Выберем n человек из этих знакомых A и n человек из этих знакомых B, а также еще одного человека из оставшейся группы. Тогда мы имеем две группы по n+1 человек, и для каждой из них мы можем найти человека, знакомого со всеми в этой группе. Один из этих двух людей должен быть знаком с нашим выбранным человеком из оставшейся группы, поскольку в компании для любых n людей найдется отличный от них человек, знакомый со всеми. Пусть этот человек из первой группы и знаком с выбранным нами человеком из оставшейся группы. Тогда он также знаком и с B, поскольку он знаком со всеми второй группы. Но тогда он знаком и с A, потому что он знаком с нашим выбранным человеком из оставшейся группы, который знаком с A. Все. Мы нашли человека, знакомого со всеми людьми в компании.