Числовые превращения

Swetlana · Сообщение **Swetlana** » 17 окт 2015, 21:33

Swetlana · Сообщение **Swetlana** » 20 окт 2015, 21:13

Andrew58 писал(а):Source of the post Готовы ли участники обсуждения дать ответ на вопрос, заданный автором темы?

Как, уже? Я человек слабомыслящий, рано меня на 7-й странице к ответу призывать. Тем более, что ещё не ответили на вопрос, который я задала ТС: важен ли порядок элементов, полученных в результате преобразований. Но раз надо значит надо. Попробую на него ответить.
---------------------------------------------------------------------------------------------
Сабжевое преобразование может быть прямым и обратным; упорядоченным и неупорядоченным.
Под "цепочкой" в дальнейшем подразумевается конечная последовательность прямых упорядоченных преобразований. "Табличка" - представление цепочки в виде таблицы.
Под "последовательностью" - упорядоченная перестановка чисел $$1, ..., n$$

, $n \geq 4$ , а также любая последовательность, полученная из неё в результате конечного числа прямых упорядоченных преобразований.
Опр. 1. Для любых двух элементов последовательности $$i, j$$

, находящихся в последовательности на разных местах, транспозиция $(i, j) \rightarrow (j, i)$ называется выполнимой, если существует цепочка такая, что эл-ты $$i, j$$

меняются местами, остальные эл-ты остаются на месте.
Л.1. Если транспозиция $$(i, j)$$

выполнима, то выполнима и транспозиция $$(j, i)$$

.
Док.-во. В табличке, выполняющей транспозицию $$(i, j)$$

, меняем местами $$i-$$

й и

й столбцы.
Л. 2. Пусть для последовательности $$[1, ..., n]$$

, $n \geq 4$ все транспозиции выполнимы. Тогда для последовательности длины $$n+1$$

все транспозиции выполнимы, если выполнима транспозиция $(n+1, 1)\rightarrow (1, n+1).$
Док.-во. Для всех эл-тов $i,j \leq n$ транспозиции выполнимы в силу предположения. Докажем, что любая транспозиция $(n+1, i), i \in {1, ..., n}$ выполнима.
1. Выполняем транспозицию $(1, i) \rightarrow (i, 1)$ в силу предположения.
2. Выполняем транспозицию $(n+1, 1)\rightarrow (1, n+1)$ в силу предположения.
3. Выполняем транспозицию $(1, i) \rightarrow (i, 1)$ .

Л.3. Пусть для последовательности $$[1, ..., n-1]$$

, $n \geq 5$ все транспозиции выполнимы. Тогда для последовательности длины $$n$$

транспозиция $(n, 1)\rightarrow (1, n)$ выполнима.
Это уже нетривиально. После рассматривания табличек возникла следующая идея доказательства. Отдельно рассмотреть 3 случая, в зависимости от значения n mod 3.
Для случая n mod 3 = 1 получила цепочку в 6 шагов. Приведу пока саму цепочку. потом проиллюстрирую её таблицей.
Обозначения: d = n div 3; m = n mod 3 (1).
В последовательности длины n преобразуются только элементы n, d-1, d, 1, находящиеся в 1-м, d-1-м, d-м, n-м столбцах соответственно. Остальные элементы в преобразованиях не участвуют, соответственно, столбцы с этими номерами не изменяются.
$(n, ..., d-1, d, ..., 1_{last}) \rightarrow (1, ..., d-1, d, ..., n).$
Шаг 1. $(d, n) \rightarrow (-m = -1, 4d - 3) = (-1, 4d - 3).$ Изменили d и n.
Шаг 2. $(d-1, 4d - 3) \rightarrow (-d, d - 4).$ Изменили d-1.
Шаг 3. $(-1, d - 4) \rightarrow (1-d, -n).$
Шаг 4. $(-d, -n) \rightarrow (1_{first}}, -4d+3).$ Получили "первую" 1.
Шаг 5. $(1-d, -4d+3) \rightarrow (d, 4-d).$ Получили d.
Шаг 6. $(1_{last}, 4-d) \rightarrow (d-1, n_{last}).$ Получили d-1 и n с заменой "последней" 1 на n.
Элемент n находится, как и требовалось, на месте "последней" 1, остальные эл-ты упорядочиваются согласно предположению.
ч.т.д.

Swetlana · Сообщение **Swetlana** » 21 окт 2015, 10:43

Замечание. Цепочка для случая остаток равен 1 не проходит для n=4. Там нет элемента d-1=0. Этого ничего. Случай n=4 будет основанием индукции. А вот для n=7 проверю на досуге.
Так что пока эта цепочка верна, начиная с n=10, с чьей таблички, собственно, и записывала. (Затем проверила для n=13, 16.)

Swetlana · Сообщение **Swetlana** » 21 окт 2015, 17:18

С n=7 всё в порядке, 1 на последнем шаге снова превращается в 1. Табличка сделана точно по алгоритму:

Swetlana · Сообщение **Swetlana** » 21 окт 2015, 17:21

Со нулевым остатком от деления на 3 сурово, запуталась, увы.

Случай n mod 3 = 2. 12 шагов, смотрела по табличке для 5.
В последовательности длины n преобразуются только элементы n, d+1, d+2, 1, находящиеся в 1-м, d+1-м, d+2-м, n-м столбцах соответственно. Остальные элементы в преобразованиях не участвуют, соответственно, столбцы с этими номерами не изменяются.
$(n, ..., d+1, d+2, ..., 1_{last}) \rightarrow (1, ..., d+1, d+2, ..., n).$
Шаг 1. $(d + 1, n) \rightarrow (1, 4d + 7).$ Изменили d+1.
Шаг 2. $(d + 2, 1) \rightarrow (3d + 5, 13d + 23).$ Изменили d+2.
Шаг 3. $(4d + 7, 13d +23) \rightarrow (-d - 2, 13d + 22).$
Шаг 4. $(3d + 5, 13d +22) \rightarrow (-4d - 7, -1).$
Шаг 5. $(-d - 2, -4d - 7) \rightarrow (d + 1, -d - 5).$
Шаг 6. $(-1, -d - 5) \rightarrow (d + 2, 3d + 2).$
Шаг 7. $(d + 1, 3d + 2) \rightarrow (1, 4d + 7).$ Получили первую 1.
Шаг 8. $(d + 2, 4d + 7) \rightarrow (-d - 1, d + 5).$
Шаг 9. $(1_{last}, -d - 1) \rightarrow (d + 4, 3d + 16).$ Последний эл-т последовательности d+4.
Шаг 10. $(d + 5, 3d + 16) \rightarrow (-1, 4d + 17).$
Шаг 11. $(d + 4, 4d + 17) \rightarrow (-d - 5, d + 1).$ Получили d+1. Последний эл-т последовательности -d-5.
Шаг 12. $(-1, -d - 5) \rightarrow (d +2, 3d + 2 = n).$ Получили d+2. Последний эл-т последовательности n.

Swetlana · Сообщение **Swetlana** » 21 окт 2015, 20:48

Красивая табличка для 9 только для 9. Попробую (на досуге) получить цепочку для нулевых остатков из 15-шаговой табличке для 12. Терпенье и труд всё перетрут, даже здоровье. Всё же интересно, как это задача должна была решаться на самом деле.
n=12

Swetlana · Сообщение **Swetlana** » 21 окт 2015, 20:52

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

Swetlana · Сообщение **Swetlana** » 22 окт 2015, 11:02

Так, для n (mod 3) $\equiv$ 0 не получается записать алгоритм транспозиции $(n, 1) \rightarrow (1, n)$ в общем виде. Все таблички какие-то уникальные.
Для n (mod 3) $\equiv$ 1 первый шаг был $(d, n) \rightarrow (-m = -1, 4d - 3) = (-1, 4d - 3).$
Для n (mod 3) $\equiv$ 2 первый шаг был $(d + 1, n) \rightarrow (1, 4d + 7).$
Видимо, для n (mod 3) $\equiv$ 0 первый шаг должен быть (d-1, n).
Какое отношение имеют вычеты по модулю 3 к решению задачи?

12d3 · Сообщение **12d3** » 22 окт 2015, 11:18

Swetlana писал(а):Source of the post Какое отношение имеют вычеты по модулю 3 к решению задачи?

Количество чисел, кратных трем, не изменяется при преобразованиях.

12d3 · Сообщение **12d3** » 22 окт 2015, 13:29

Удалено, фигню написал.

yourdomain.com