Задача о заходящих в гости

[tolkodelo]

Добрый день!

Не могу решить задачу, имеющую практическое применение (не специалист, а со школы уже материал подзабыл)  Будьте добры, помогите:

Дано:
Скажем, есть группа из 5*N друзей (можно взять N=10), которые договорились каждый день ходить друг к другу в гости по следующим правилам:
   1.Все друзья разобьются на группы по 5 человек.
   2.Каждый друг должен в конкретный день зайти в гости к 5 друзьям  из одной группы по 5 человек (причем любой из них может пойти к нему в гости в тот же день), в другой - к другой группе, и т.д., пока не обойдет все группы. Потом начинает сначала. (Получается, что для него количество друзей  = 5*N-1)

Вопрос:
Сколько человек будет заходить в гости к каждому другу каждый день? Изменится ли ответ, если они будут ходить в гости произвольно, а не по группам (но не навещая того же человека, пока не пройдут по всем остальным)?

Заранее большое спасибо!

[tolkodelo]

Ну пажаааалуйста......... 30 человек посмотрели, ни один не ответил... Хоть скажите, что почитать, чтобы разобраться?

[wital1984]

...Получается, что для него количество друзей  = 5*N-1)

Думаю, это неправильное утверждение. Т.к. ходит он только к другим группам (если бы ходил и к своей, то пришлось бы сходить в гости к самому себе   ). По-моему, друзе
Вопрос:
Сколько человек будет заходить в гости к каждому другу каждый день? Изменится ли ответ, если они будут ходить в гости произвольно, а не по группам (но не навещая того же человека, пока не пройдут по всем остальным)?

Заранее большое спасибо!

[wital1984]

Думаю, что друзей у чела все-таки 5*(N-1) (если свою группу не считать, а если считать то бред получится - должен к себе самому в гости сходить).
За N-1 день к каждому человеку должны сходить все друзья (все 5*(N-1) человек). В один день может не прийти никто, а в другой могут прийти все. Значит, в любой день может прийти произвольное кол-во друзей от 0 до 5*(N-1). При произвольном порядке, очевидно, ответ не изменится. Задача, по-моему, на комбинаторику. В таких проще разбираться от простого к сложному. Т.е. рассмотреть сначала две группы, потом три, а потом можно и обобщить.

[tolkodelo]

Спасибо за ответы!

если свою группу не считать, а если считать то бред получится - должен к себе самому в гости сходить

А если он в этот день сходит к 4 человекам из своей группы?

Думаю, что друзей у чела все-таки 5*(N-1)

При 5 группах (N=5) по 5 человек получаем количество друзей:

1.5*N-1=24
2.5(N-1)=20 (по вашим словам)


Попробую подумать вслух:
1. При простейшем случае получается такое движение визитов: группа I идет к группе I+1, та идет к группе I+2 и т.д. А I+(N-1) идет к группе I. На следующий день смещается на 1 (То есть, группа I идет к I+2). Тогда в каждый день каждый человек в группе должен получить 5 визитов от друзей предыдущей группы (а всего входящих визитов в группу от друзей из прошлой должно быть 25 - по пять на каждого). Тогда за N-1 дней  он получит (N-1)*5 визитов (5 чел от каждой группы кроме своей), а всего визитов будет (N-1)*((N-1)*5)
То есть визитов 5 в день

2.При более сложном случае группа I начинает с себя, т.е. каждый человек получает 4 визита от своей группы и 5 от прошлой группы, а в следующий день будет получать по 5 визитов от прошлой. Тогда получается одна группа будет иметь по 9визитов на человека, другая 0 и последующие по 5, в след день вторая будет иметь 10,в 3й день третья по 10, и в день N первая будет иметь 0, последняя 9. Тогда получаем среднее кол-во визитов (2*(9+0+5*2N)+(N-2)*(10+(N-2)))/N².
То есть в визитов от 0 до 10, при N=10 среднее количество 7,22 , и при увеличении N среднее количество визитов стремится к 5

3.Следующий случай - когда все группы начали одновременно с себя (первый день у всех по 4), последующие у всех по 5., то есть среднее (((N-1)*5)+4)/N, тогда количество визитов от 4 до 9, среднее при N=10 равно 5,6
4.Следующий случай - когда человек выбирает друзей произвольно. Тогда  тут уже вероятность получить конкретного человека в конкретный день равняется 5/(5N-1) (он же к 5 друзьям ходит), тогда вероятно, что каждый день к нему будут приходить N*(5/(5N-1), для N=10 это 5,1
5. Если они будут в произвольные дни  добавлять еще группы по 5 человек, тогда вообще весело...

Интересно, что в любом случае у меня выходит, что в каждый день будут заходить в гости в среднем около 5 человек! И чем большее число друзей участвует в проекте, тем больше это число стремится к 5! Это правильный вывод?

[wital1984]

...Интересно, что в любом случае у меня выходит, что в каждый день будут заходить в гости в среднем около 5 человек! И чем большее число друзей участвует в проекте, тем больше это число стремится к 5! Это правильный вывод?

Думаю, нет. Вы считаете, что все члены одной группы обязательно должны вместе ходить в гости в одну и ту же группу. А если они будут ходить по разным группам? Также ваше предположение о том, что можно ходить и к себе в группу не совсем правильое. Вы не учитываете, что он должн сходить в гости к самому себе. По вашему получается, что он зайдет в гости  всем, коме себя, т.е. сходит в гости 5*N-1 раз, а этого не мжет быть по условий, т.к. каждый день он должен посетить 5 человек, значит и общее число посеений должно быть  кратно 5. если уж он ходит к своей группе, то н должен прийти и к себе. Тогда у каждого посещений может быть в день от 0 до 5N.

[tolkodelo]

мдаааа..... Вы, наверное, правы...

А практическое применение этой задачи вот какое: я пытаюсь оценить эффективность вот этого проекта: ссылка