Задача #sixseven

[KonstantinDedov]

Придумал такую задачу чуть больше 2-х лет назад, но после выхода трека Газана снова о ней вспомнил. Если у вас есть ученики-подростки, можете заинтересовать их ей.

Есть прямоугольник 6x7 клеток. Заполните его цифрами 6-7 так, чтобы любой горизонтальный или вертикальный отрезок из 5 клеток содержал уникальную комбинацию шестёрок и семёрок, если читать слева-направо или сверху-вниз. Интерес в том, что отрезков 32 и упорядоченных пятёрок из цифр 6 и 7 тоже ровно 32.

[wrest]

Интересная задача, но непонятно как решать без перебора.
То есть: можно ли сконструировать решение?
Например: отрезок длиной 9, прямоугольник 20х21

[gris]

Интересная задача! Но решил начать с маленьких отрезков, отрезков, перебора, а заодно заменил 67 на противопожарность:)
Позабавился немного и вот:
1: 2 [0, 1]
2: 5 [0, 0, 1, 1, 0]
3: 10 [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
4: 19 [0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0]
То есть для отрезка 3 минимальная длина отрезка в котором найдутся все комбинации равна 10. Приведён пример. На самом деле их много: инвертированные и симметричные подойдут.
Натурально, радостно понёс результаты в Энциклопедию и обнаружил их там, а заодно теорию и прочие дела, в которых можно и поковыряться на досуге. Сейчас пробую увеличить стороны прямоугольника.

[wrest]

gris в сообщении #1725556 писал(а):

Сейчас пробую увеличить стороны прямоугольника.

Следующий 7х11 и отрезок 6
Но заполнить не удалось [пока]

[slavav]

Подходящие длины отрезков: 1, 2, 5, 6, 8, 9, 12, 17, 19, ...
Этой последовательности нет в OEIS и я даже не знаю бесконечна ли она.

[wrest]

slavav в сообщении #1725644 писал(а):

Подходящие длины отрезков: 1, 2, 5, 6, 8, 9, 12, 17, 19, ...

Это-то как раз понятно. Непонятно как точно узнать что решение есть (например для длины 6) и как его быстро (не за годы) найти.
Для отрезка длины 5 на всякий случай если кто ещё не нашёл:

0 0 0 0 0 1 1
0 0 1 0 1 1 0
1 1 1 0 0 0 1
1 1 1 1 0 1 0
0 1 1 0 0 1 1
1 0 1 0 0 1 0

-- добавлено через 13 минут --

slavav в сообщении #1725644 писал(а):

Этой последовательности нет в OEIS и я даже не знаю бесконечна ли она.

Бесконечна, т.к. подходят по крайней мере $n=2^{k+1}+1, k \in \mathbb{N}$

[mihaild]

А какое обобщение рассматривается? Для любого ли $k$ можно заполнить какой-то прямоугольник $m\times n$ со свойством $(m - k + 1) \cdot n + m \cdot (n - k + 1) = 2^k$ нулями и единицами так, чтобы любая последовательность длины $k$ встречалась?

[wrest]

mihaild в сообщении #1725647 писал(а):

Для любого ли $k$ можно заполнить какой-то прямоугольник $m\times n$ со свойством $(m - k + 1) \cdot n + m \cdot (n - k + 1) = 2^k$ нулями и единицами так, чтобы любая последовательность длины $k$ встречалась?

Да, это. Ну не для любого $k$ существует сам прямоугольник, но если существует то можно ли заполнить.
Ну и как такое заполнение найти.

[slavav]

wrest в сообщении #1725645 писал(а):

Бесконечна, т.к. подходят по крайней мере $n=2^{k+1}+1, k \in \mathbb{N}$

Расскажите подробнее.

-- добавлено через 1 минуту --

Ссылка на близкую задачу: https://en.wikipedia.org/wiki/De_Bruijn_sequence

[wrest]

slavav в сообщении #1725661 писал(а):

Расскажите подробнее.

Обозначения. Внимание: обозначения отличаются от тех что дал mihaild. Прошу прощения за это.

$n$ - длина отрезка (в стартовом посте $n=5$).
$k,m$ - стороны прямоугольника, в старотовом посте это $k=6,m=7$ (понятно, с точностью до перестаровки).

Тогда длины сторон нужного нам прямоугольника должны удовлетворять уравнению

$$m(k-n+1)+k(m-n+1)=2^n \eqno{(1)}$$

И при том должно быть $k,m > n-1$ (то есть обе стороны не короче отрезка)

Введём замены $x=2m-n+1;y=2k-n+1$
Подставляем $x,y$ в (1). Легко видеть ( ), что

$$xy=2^{n+1}+(n-1)^2 \eqno{(2)}$$

Пусть теперь $n=2^a+1,a>1$

Перепишем правую часть (2) с учётом этого:

$$xy=2^{2^a+2}+2^{2a} \eqno {(3)}$$

Положим
$x=2^{2a-1}$
$y=2(2^{2^a+2-2a}+1)$
Тогда легко видеть ( ) что
$m=2^{2a-2}+2^{a-1}$
$k=2^{2^a+2-2a}+1+2^{a-1}$

Ну собсно и всё.
Подставляем например $a=4$, получаем $n=17;m=72;k=1033$
То есть для длины отрезка 17 подошёл прямоугольник 72х1033

Это показывает бесконечность "подходящих" отрезков и прямоугольников для них, но конечно это не все, а только одна серия.

-- добавлено через 41 минуту --

slavav в сообщении #1725661 писал(а):

Ссылка на близкую задачу: https://en.wikipedia.org/wiki/De_Bruijn_sequence

Полагаю, она не такая уж близкая :)

[wrest]

wrest в сообщении #1725641 писал(а):

Следующий 7х11 и отрезок 6
Но заполнить не удалось [пока]

Решение всё ещё не нашлось.
Меня терзают смутные сомнения, что и не найдётся.
Можно ли это доказать?
Вариантов заполнить прямоугольник 7х11 получается $2^{77} \approx 10^{24}$, все не перебрать

[mihaild]

wrest в сообщении #1725666 писал(а):

Это показывает бесконечность "подходящих" отрезков и прямоугольников для них

А почему прямоугольник тако размера можно заполнить?

wrest в сообщении #1725683 писал(а):

Решение всё ещё не нашлось

ortools ищет час, пока что тоже не нашло.

[wrest]

mihaild в сообщении #1725688 писал(а):

А почему прямоугольник тако размера можно заполнить?

Что можно заполнить, я не говорил. Прямоугольники я назвал "подходящими" в том смысле, что в них умещаются ровно $2^n$ отрезков (одномерных окон) размера $n$ как описано в стартовом посте.
А вот можно ли заполнить окнами без повторов (ну или чтобы любая комбинация встречалась - это то же самое) такие прямоугольники - это и есть вопрос темы.

-- добавлено через 14 минут --

mihaild в сообщении #1725688 писал(а):

ortools ищет час, пока что тоже не нашло.

У меня правильно заполняется максимум 74 клетки из 77 (для прямоугольника 11х7 и окна длиной 6).
Заполнение идёт сверху-вниз, слева-направо (т.е. построчно).

[wrest]

В общем, сдаётся мне, что прямоугольник 6х7 и отрезок n=5 -- единственный, который можно заполнить по условиям первого поста, то есть уложить ровно 2^n отрезков с уникальными комбинациями двух цифр так чтобы были и горизонтальные и вертикальные отрезки.
Отрезок длиной 6 не укладывается в прямоугольник 7х11 чуть-чуть, а более длинные уже не чуть-чуть.
Для отрезков 3 и 4 нет подходящих прямоугольников, а отрезки 1 и 2 слишком короткие.

Неожиданно.

[slavav]

Есть размеры в которых поле только на единицу шире длины отрезка. И даже есть размеры в которых равенство.

Длина $8$ поле $9 \times 29$.
Длина $17$ поле $18 \times 6568$.
Длина $31$ поле $32 \times 63161312$.
Длина $37$ поле $38 \times 3435973871$.
Длина $577$ поле $578 \times X$.
Длина $2257$ поле $2258 \times X$.
Длина $5477$ поле $5478 \times X$.
Длина $38117$ поле $38118 \times X$.
Длина $46049$ поле $46050 \times X$.
Длина $49736$ поле $49736 \times X$.
Длина $65537$ поле $65538 \times X$.