Театральный фестиваль

[Xenia1996]

а) 6

б) 11

театральных трупп приняли участие в фестивале. Каждый день некоторые труппы выступали, а остальные – смотрели выступления. Какое наименьшее количество дней должен продолжаться фестиваль так, чтобы каждая труппа просмотрела (из зала) выступления всех остальных?

[Руст]

Гораздо интереснее $N$.
К примеру, если $(n-1)^2<N\le n^2$, то достаточно $2n$.

[Xenia1996]

Руст в сообщении #463000 писал(а):

...если $(n-1)^2<N\le n^2$, то достаточно $2n$.

Почему?

Нет, стоп!
Для $N=6$ достаточно даже 4.

[Руст]

Можно немного улучшить, до $2[\sqrt{N}+\frac 12]$. Это как раз для $N=6$ даст 4.

[Sender]

Что-то мне кажется, что можно улучшить до $2[\log_2{N}]$.

[Руст]

Ошибаетесь. Порядок $2\sqrt N$ похоже неулучшаем.

[Sender]

Руст в сообщении #463019 писал(а):

Ошибаетесь. Порядок $2\sqrt N$ похоже неулучшаем.

Пусть точное значение минимально необходимого количества дней для N групп равно F(N). Очевидно, F(2)=2. Тогда F(2N)=F(N)+2: разделим 2N трупп на две группы по N, зрительный зал и сцену разделим на две половинки , за F(N) дней 1-я группа познакомится с репертуаром 1-й, а 2-я - с репертуаром 2-й. На F(N)+1-й день сажаем в зрительный зал 1-ю группу трупп, 2-ю выводим на сцену; F(N)+2-й день - наоборот.

[Руст]

Да, я ошибся. Я решал разместив в прямоугольник $n*n$ или $n*(n+1)$. Вначале на сцене выступают все кроме 1 строчки, 2- строчки,...Далее кроме первой вертикали, второй вертикали,...

[Sender]

Да, там у меня должно быть неравенство: $F(2N)\leqslant F(N)+2$. Тогда $F(N)\leqslant 2\log_2 N$. Пока не придумал, как доказать, что нельзя обойтись меньшим количеством.

[Psw]

Точное решение через биномиальные коэффициенты - http://e-science.ru/forum/index.php?act=ST&f=6&t=32259&st=0#entry293737

[Руст]

Sender в сообщении #463038 писал(а):

Да, там у меня должно быть неравенство: $F(2N)\leqslant F(N)+2$. Тогда $F(N)\leqslant 2\log_2 N$. Пока не придумал, как доказать, что нельзя обойтись меньшим количеством.

Можно за меньшее. Я придумал более экономный способ, но только коэффициентом перед логарифмов. Пока оставлю в секрете.

Psw в сообщении #463050 писал(а):

Точное решение через биномиальные коэффициенты - http://e-science.ru/forum/index.php?act=ST&f=6&t=32259&st=0#entry293737

Это растет как корень не экономно.

[sup]

Sender в сообщении #463038 писал(а):

Да, там у меня должно быть неравенство: $F(2N)\leqslant F(N)+2$. Тогда $F(N)\leqslant 2\log_2 N$. Пока не придумал, как доказать, что нельзя обойтись меньшим количеством.

Ну тогда уж можно и $F(6N)\leqslant F(N)+4$. И вообще $F(kN)\leqslant F(N)+F(k)$

[Руст]

Цитата:

Ну тогда уж можно и $F(6N)\leqslant F(N)+4$. И вообще $F(kN)\leqslant F(N)+F(k)$

Последнее верно. Только откуда взяли, что $F(6)=4$.

[sup]

У Ксении подсмотрел

Xenia1996 в сообщении #463002 писал(а):

Руст в сообщении #463000 писал(а):

...если $(n-1)^2<N\le n^2$, то достаточно $2n$.

Почему?

Нет, стоп!
Для $N=6$ достаточно даже 4.

[Sender]

Руст в сообщении #463072 писал(а):

Цитата:

Ну тогда уж можно и $F(6N)\leqslant F(N)+4$. И вообще $F(kN)\leqslant F(N)+F(k)$

Последнее верно. Только откуда взяли, что $F(6)=4$.

Можно привести расписание концертов по дням, например:
1. 4, 5, 6.
2. 2, 3, 6.
3. 1, 3, 5.
4. 1, 2, 4.

Все остальные в эти дни - зрители. Минимальность этого числа очевидна, полагаю?