Решить по-русски

СергейП

Ian писал(а):Source of the post Вот эту очень захотелось перевести. Запостили сутки назад, 38 просмотров, на 4й странице таблицы Unanswered posts, значит кто-то еще думает но не придумал, а остальные мало кто посмотрит. Вся надежда на вас

12. По кругу равномерно расположены 12 домиков. 4 человека A,B,C,D занимают некоторые 4 домика по часовой стрелке, а остальные домики пусты. За один ход один человек может переместиться в домик, расположенный через 4 пятым от занимаемого им (в общем, на 5/12 окружности), по часовой стрелке или против, но если домик пустует.
После нескольких ходов оказалось, что эти 4 человека снова занимают 4 соседних домика. В каком порядке по часовой стрелке они могут расположиться?

Всего порядков может быть 12 от ABCD до DCBA, надо среди них отметить какие возможны

Предполагается, что вначале заняты 4 смежных домика?
Тогда, если обозначим начальный порядок ABCD, то ещё можно получить 3 таких порядка DCAB, BADC и CDBA. Остальные получить нельзя.
Причём эти 4 порядка можно получить в любых 4-х смежных домиках, а ещё для этого достаточно перемещений только в одну сторону, любую, например, по часовой стрелке.

Ian · Сообщение **Ian** » 26 дек 2011, 17:17

СергейП писал(а):Source of the post
Тогда, если обозначим начальный порядок ABCD, то ещё можно получить 3 таких порядка DCAB, BADC и CDBA. Остальные получить нельзя.

Браво! А у меня и доказательство есть, 5 строчек и картинка!
А у Вас?

СергейП

Ian писал(а):Source of the post
СергейП писал(а):Source of the post Тогда, если обозначим начальный порядок ABCD, то ещё можно получить 3 таких порядка DCAB, BADC и CDBA. Остальные получить нельзя.
Браво! А у меня и доказательство есть, 5 строчек и картинка!
А у Вас?

Доказательтво у меня есть, довольно простое, но совсем не 5 строчек. Там ручками пришлось много поработать - нарисовать граф ходов и вперёд.
Всё довольно просто и быстро, но писать надо много

Ian · Сообщение **Ian** » 26 дек 2011, 19:02

В общем уже почти все сказано. Мой вариант оформления:
Занумерованные домики перерасположим так, чтобы человек мог переселяться в соседние и только в них.

Тогда на новой окружности порядок людей ACBD, или, обозначив транспозицию $\tau=(23)$ , $\pi\tau (ABCD)$ , где $\pi$ элемент циклической подгруппы $$G=<(1234)>=(e,(1234),(13)(24),(1432))$$

, потому что по новой окружности люди могут переходить, сохраняя порядок, в любые 4 домика. То что домики на старой окружности стоят подряд, равносильно тому, что на новой окружности они будут в вершинах трапеции с основаниями, стягивающими дуги 5/12 и 3/12 окружности, таких трапеций существует 12. Это $\pi\tau (ABCD)$ соответствует их порядку на новой окружности, начиная со 2го по часовой стрелке тупого угла. А порядок их по красным стрелкам. т.е. на старой окружности, будет $\tau\pi\tau (ABCD)$ , 2й и 3й элемент надо поменять местами. Придавая $\pi$ ее 4 разных значения, получаем ответ СергеяП.
Такая "занимательная алгебра", надеюсь, понятная даже тем, кто алгебру забыл
Тут видно для чего она служит: эти общие конструкции не дадут ошибиться в частностях.

Ian · Сообщение **Ian** » 06 янв 2012, 00:05

Вот еще :rolleyes:
13. Последовательность задана условиями
$\displaystyle \\a_0=0\\a_1=1\\a_2=2\\a_n=a_{n-1}-\min (a_{n-2},a_{n-3})$
(Дальше отклоняюсь от оригинала) Найти $$a_n$$

компактной формулой от $$n$$

.
Использовать знаки целой части можно:)

Sonic86 · Сообщение **Sonic86** » 06 янв 2012, 07:14

Эмм. Первые 15 членов считаем. Вектор из следующих 15 членов - это предыдущий вектор, умноженный на 3. Тогда за $O(\ln ^k n)$ можно подсчитать.
Т.е. $a_n=3^{\left[ \frac{n}{15} \right]} a_{n \mod 15}$
Соотношение от начальных данных почти не зависит (иногда есть предпериод из $$a_0,a_1,a_2$$

). И даже если $\min$ заменить на $\max$ остается то же самое.
График красивый Все-таки Excel - хорошая штука.
А вообще рекуррентность, как и ее решение, смахивает на $e^{kn} \sin (\omega n + \varphi)$ .
Еще бы доказать это все...

Ian · Сообщение **Ian** » 06 янв 2012, 07:41

Sonic86 писал(а):Source of the post Т.е. $a_n=3^{\left[ \frac{n}{15} \right]} a_{n \mod 15}$

Ага. Есть надежда,что мы продолжим и найдем выражение через 15 корней 15й степени из единицы, без всяких знаков целой части

Соотношение от начальных данных почти не зависит (иногда есть предпериод из ).
График красивый Все-таки Excel - хорошая штука.
А вообще рекуррентность, как и ее решение, смахивает на $e^{kn} \sin (\omega n + \varphi)$ .
Еще бы доказать это все...

И объяснить, при чем же здесь 15= $$C^2_6$$

. Что $k=\frac{\ln 3}{15}$ и $\omega=\frac{2\pi}{15}$ это ясно

Sonic86 · Сообщение **Sonic86** » 06 янв 2012, 08:23

А почему

? Меняем коэффициенты - уже другой период.
Наверное на целую часть можно забить - нормальный оператор.

Попробую в общем виде сформулировать. Определим М-многочлены (минимаксные).
Опр. 1. $(\forall j=\overline{1,k}) F=x_j$ - М-многочлен.
2. Если $$F,G$$

- М-многочлены, то $-F, F+G, \min (F,G)$ - М-многочлены (отсюда следует, что $\max(F,G)$ - тоже М-многочлен).
3. Других М-многочленов нет.
Гипотеза Пусть $$F$$

- М-многочлен. Тогда рекуррентное соотношение $a_n=F(a_{n-1},\ldots,a_{n-k})$ удовлетворяет некоторому линейному однородному рекуррентному уравнению $a_n=G(a_{n-1},\ldots,a_{n-m})$ ( $$G$$

- обычный многочлен).
Так?

Ian · Сообщение **Ian** » 06 янв 2012, 09:07

Другой период? Например?
Я срочно предложу унифицировать нашу терминологию. Принимая все что у Вас, определим "порядок" $\nu$ М-многочлена как число переменных, находящихся под знаками мин. и макс. из общего числа $$n$$

переменных. Тогда есть гипотеза, что в Вашей гипотезе можно взять $m=C^{\nu}_{k\nu}$
В частности, в задаче было $\nu =2, k=3$

Sonic86 · Сообщение **Sonic86** » 06 янв 2012, 09:22

Ian писал(а):Source of the post Другой период? Например?

Возьмите вместо $\min (a_{n-2},a_{n-3})$ более общее выражение $\min (C_1a_{n-2},C_2a_{n-3})$ и выбирайте разные $$C_j$$

(я брал

).

Ian писал(а):Source of the post Я срочно предложу унифицировать нашу терминологию. Принимая все что у Вас, определим "порядок" $\nu$ М-многочлена как число переменных, находящихся под знаками мин. и макс. из общего числа переменных. Тогда есть гипотеза, что в Вашей гипотезе можно взять $m=C^{\nu}_{k\nu}$
В частности, в задаче было $\nu =2, k=3$

Ого! А до этого я еще не дошел... Ну ладно.

yourdomain.com