За круглым столом сидят несколько гостей. Некоторые из них знакомы между собой; знакомство взаимно. Все знакомые любого гостя (считая его самого) сидят вокруг стола через равные промежутки. (Для другого человека эти промежутки могут быть другими.) Известно, что любые двое имеют хотя бы одного общего знакомого. Докажите, что все гости знакомы друг с другом.


+ -

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 4

Tov Kronsteen 2016-05-27 22:27:47 пишет:

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

ввввв 2016-04-30 18:07:26 пишет:

Пусть N - расстояние между знакомыми. У каждого есть общий знакомый с каждым. Тогда если N у всех одинаковы, значит все будут знать всех, иначе не могло бы быть у каждого общих знакомых с каждым. Допустим, у разных людей разные N. Возьмём человека А с наименьшим N. Но тогда у его ближайших соседей по правую и левую руки от него N не меньше. И у их ближайших соседей тоже. Следовательно не существует человека с наименьшим N, значит N у всех одинаково. Выходит, все всех знают.

очть 2011-10-11 16:39:43 пишет:

Допустим, два соседа а и б не знакомы друг С другом. По условию у них есть общий знакомый С, сидящий от них через равные промежутки вокруг стола. Но! раз С сидит от а и б через равные промежутки, то он знаком со всеми сидящими за столом, т.к. все остальные сидят от него через равные промежутки. Значит, если С знаком со всеми, то его соседи тоже знакомы со всеми, т.к. знакомы с С, и т.д.

Админ:

014 2011-08-19 15:32:42 пишет:

Попробуем так: за столом сидят, допустим, трое, двое из них имеют хотя бы одного общего знакомого. Значит они сидят через равные промежутки вокруг стола от этого самого общего знакомого. теперь возьмем любого из знакомых этого знакомого. По условию у него тоже есть хотя бы два общих знакомых, сидящих от него через равные промежутки. Это значит, что стол, за которым сидят эти люди, делится на три равные части - следствие того, что все гости знакомы друг с другом

Админ:

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

© 2009-201x Логические задачи