Задача Штейнгауза (двоичный треугольник)

[Fireball]

В книге Штейнгауза "100 задач" на 48-49 страницах приведена задача, которая на момент издания не имела решения. Она называется "Плюсы и минусы".
Верхняя строка содержит плюсы и минусы. Следующая строка формируется след образом: под двумя одинаковыми знаками стоит "+", под двумя разными стоит "-". И так далее. Таким образом каждая последующая строка будет на один знак меньше предыдущей. Возможно ли для любого n построить треугольник, содержащий одинаковое число плюсов и минусов?
Естественно, что решение может быт найдено только в том случае, если число (n/2)*(n+1) является четным.

Вот, например, ссылка на книгу: http://www.e-reading.org.ua/djvureader. ... adach.html

Посерфив в Сети, ничего не нашел. Может ее уже давно решили, а может и нет) Может есть некие частные решения или что-то в этом роде.

[mserg]

Задачка, кстати, забавная. Рекомендую. . Я решил ее в "детстве" (где-то 1990 году) без компьютера.

Подсказка.
Ответ задачи: да. Доказано построением явного решения для любого (допустимого по модулю 4) n.

Если не получится, могу сделать еще одну подсказку.

P.S. переживать что тема старая не стоит.

[waxtep]

mserg, кажется, я нашел эмпирическое правило построения, правда, доказать пока не возьмусь.
Работает для $n=3,4,7,8$. Очень интересно, совпадает ли конструктивная часть с Вашим решением?

1. Обозначения: занумеруем строки $i=0,1,\ldots ,n-1$ и столбцы $j=0,1,\ldots ,n-i-1$.
Используем $0$ вместо "$+$" и $1$ вместо "$-$". Тогда, операция получения элемента - исключающее или, $a_{i+1,j}=a_{i,j}\oplus a_{i,j+1}$

2. Построение: в каждую строку будем записывать поочередно $0$ и $1$, причем, для каждой строки $i$, только в один столбец $j=i \bmod (n-i)$. Затем, восстановим весь треугольник "снизу вверх", опираясь на записанные $n$ двоичных цифр.

3. Пример для $n=3$: задаем $a_{0,0}=0, a_{1,1}=1, a_{2,0}=0$ и получаем:

$ \begin{tabular}{c} 0 . . \\ . 1\\ 0 \end{tabular} \Rightarrow \begin{tabular}{c} 0 1 0\\ 1 1\\ 0 \end{tabular} $

Аналогично, для $n=8$:

$ \begin{tabular}{c} 0 . . . . . . .\\ . 1 . . . . .\\ . . 0 . . .\\ . . . 1 .\\ 0 . . .\\ . . 1\\ 0 .\\ 1 \end{tabular} \Rightarrow \begin{tabular}{c} 0 1 0 0 0 1 0 1\\ 1 1 0 0 1 1 1\\ 0 1 0 1 0 0\\ 1 1 1 1 0\\ 0 0 0 1\\ 0 0 1\\ 0 1\\ 1 \end{tabular} $
​

-- 02.04.2016, 09:22 --

Эххх, уже сам вижу, что не работает для $n=11$. Возможно, $n=3,4,7,8$ хороши, поскольку имеют вид $2^n, 2^n-1$

[mserg]

Искать общее решение можно в виде: s+k*T
Здесь
s - некоторое частое решение, т.е. последовательность знаков + и -, которая дает решение задачи
T - "период" - магическая последовательность знаков + и -
k - кратность повторения, т.е. 0, 1, 2, 3, ...
+ - конкатенация последовательностей
* - обозначение кратности k повторения последовательности T
Т.е. добавление любого количества "магических периодов" T справа дает решение.

Можно написать программу, которая будет перебирать s и T, найдет частное решение, и убедится для достаточно большого количества k, что прибавление "периода" T также приводит к решению. Дальше дело техники - нужно выбрать частные решения, покрывающие всю задачу, и потом методом индукции доказать, что прибавление T даст решение для каждого из выбранных частных случаев.

Если решать задачу вручную, то не трудно убедиться, что минимальная длина T равна 12. Затем догадаться, что имеет место периодичность по строкам. Потом догадаться, что количество плюсов и минусов должно в периоде совпадать. Потом увидеть, что 12 есть 6*2, 4*3, 3*4, 2*6, 1*12. Небольшим перебором можно найти полупериод (для случая 2*6):
- - - - + +
Тогда период T может быть таким (12 знаков):
- - - - + +- - - - + +
Продлив последовательность вправо, и выстроив строки ниже, не трудно догадаться, что делать дальше.

[waxtep]

mserg в сообщении #1111408 писал(а):

Искать общее решение можно в виде: $s+kT$

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

[waxtep]

mserg в сообщении #1111408 писал(а):

Тогда период $T$ может быть таким (12 знаков):
$- - - - + + - - - - + +$

Погонял все таки немножко программно, действительно, такое $T$ является решением для $n=12$, но, $T+T$, если не напутал, уже не решение для $n=24$, там получается минусов на два меньше, чем положено. Получается, нельзя взять какое попало $s$ ? (как в данном случае, $s=T$).

[mserg]

Насколько я помню, указанный выше период подходит не для всех вариантов (по модулю 12). Тем более, взять s=T просто так нельзя.
Можно s составлять из периода T, но перебирать первые 4 знака - тогда периодичность не нарушится. Т.е. n составить полностью из знаков периода T и перебрать 4 левых знака.

[waxtep]

Нашел (наверное, очевидную) вещь, задача эквивалентна эволюции конечного автомата, заданного rule 60.
Он аддитивный и "функция Грина" из одной единички дает треугольник Серпинского, что позволяет вычислять $a_{i,j}=\sum_{k=0}^i C_i^k a_{0,j+k} \bmod 2$

[waxtep]

mserg, добрый день! Я, кажется, воспроизвел Ваше удивительное решение, по крайней мере, частично.
Например, $T=111100111100$, по всей видимости, работает для всех $n$, кроме $n=3\bmod 12$ (никакое $abc111100111100$ не является решением). А, для $n=4\bmod 12$, частное решение $s=0101$ подходит для любого количества повторений $T$ (по факту, проверял программно для $290$ и менее повторений).
Но, скажу честно, пока не разобрался, как и почему работает эта магия
Получается, за ней стоит какое-то нетривиальное утверждение по поводу четности наборов биномиальных коэффициентов?
Буду Вам очень признателен за более подробное пояснение, например, для того же случая $0101+k\cdot 111100111100$.

P.S.: я на эту задачу "подсел", и сам пытался искать другие варианты решений (их ведь очень много, скажем, $5160$ штук для $n=16$). Например, состоящих из минимального количества единиц (предположение, что это $m$ для $n=4m,4m-1$), или, состоящих только из блоков $01$ и $10$, или, состоящих из решений для меньших $n$ и т.д. Но, все эти "мелкоблочные" гипотзы неизменно ломались при довольно скромных $n\le 32$.

[mserg]

Ну, подсказки уже все сделаны.
Могу еще раз повториться...

Решение для (k+1) получается добавлением T справа к решению k (положим, что k достаточно большое).
Нетрудно заметить, что при этом добавляемое количество знаков + и - минус суммарно по строкам 1 и 2 равно (в нашем случае равно 12).
То же самое для строк 3 и 4 - добавляемое количество знаков + и - равно 12.
И т.д. - это справедливо за исключением нижней части треугольника, которая зависит от s.
Если s состоит также из T, за исключением 4-х левых знаков, то добавляемые знаки в нижних строках будут одними и теми же что при получение решения (k+1) из решения k, (k+2) из решения (k+1), и т.д. - это дает возможность для индуктивного доказательства решения для любого k.

Кажется так, надеюсь ничего не попутал...

Припоминаю, что для полного решения использовал два разных T (заметим, что циклический сдвиг, зеркальное отражение, период из второй строчки, получаемой из T, у меня считались одинаковыми). Таким образом, нужно найти подходящий период для случая, для которого период ----++----++ не подходит. Он должен удовлетворять требованиям
* Период по горизонтали - 12
* Период по вертикали - 4 (ну, или в частном случае, 2)
* Суммарное количество знаков периодов + и - по 4-м смежным строкам должно совпадать (т.е. 12*4/2 = 24).