Уважаемые коллеги, доброе утро!
Просьба помочь в решении следующей задачи (источник: 10ый класс, внешкольные умеренно "продвинутые" занятия).
Найти число двоичных последовательностей длины
, в которых нет двух нулей стоящих подряд, а все максимальные подпоследовательности из одних единиц нечетной длины.Попытка решения:
1. Будем называть последовательности, обладающими данным свойством "хорошими", и обозначать их число как
![$G(n)$ $G(n)$](https://dxdy-04.korotkov.co.uk/f/f/6/5/f65042d63b48751a253ee3503ef0f2c482.png)
. Будем искать выражение для
![$G(n)$ $G(n)$](https://dxdy-04.korotkov.co.uk/f/f/6/5/f65042d63b48751a253ee3503ef0f2c482.png)
в рекуррентном виде.
2. Если мы захотим говорить о "хороших" последовательностях длины
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
, начинающихся с определенной последовательности двоичных цифр
![$abcd...$ $abcd...$](https://dxdy-03.korotkov.co.uk/f/6/5/d/65d092b4c80278e748be149249904f2882.png)
, то их число будем обозначать как
![$G(n, abcd)$ $G(n, abcd)$](https://dxdy-04.korotkov.co.uk/f/7/1/8/718ca51d760d92594c38fb158404bd5b82.png)
. Например,
![$G(4,01)$ $G(4,01)$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f45e92c12cd1eb9802e12ba71e59fa382.png)
- число хороших последовательностей длины
![$4$ $4$](https://dxdy-03.korotkov.co.uk/f/e/c/f/ecf4fe2774fd9244b4fd56f7e76dc88282.png)
, начинающихся с
![$01$ $01$](https://dxdy-03.korotkov.co.uk/f/2/a/8/2a8dfa554b06260e6dd6ed4a6440c0fe82.png)
. Легко проверить, что таких последовательности две -
![$0101$ $0101$](https://dxdy-03.korotkov.co.uk/f/6/d/6/6d66f304afc79dc811ed7d59fd90e40082.png)
и
![$0111$ $0111$](https://dxdy-02.korotkov.co.uk/f/9/4/9/94971f8cb691fb181930a85cedb9bc3d82.png)
, т.е.
![$G(4,01)=2$ $G(4,01)=2$](https://dxdy-03.korotkov.co.uk/f/e/f/3/ef391174156207de870dc6df3f02872a82.png)
.
3. Набросок попытки решения, основанной на добавлении нулей и единиц в начало последовательности, с минимумом комментариев:
![$$G(n)=G(n,01)+G(n,10)+G(n,11) \eqno (1)$$ $$G(n)=G(n,01)+G(n,10)+G(n,11) \eqno (1)$$](https://dxdy-03.korotkov.co.uk/f/e/7/a/e7ac526dc4c58f5ca480a33ee757842082.png)
![$$G(n,01)=G(n-1,1) \eqno (2)$$ $$G(n,01)=G(n-1,1) \eqno (2)$$](https://dxdy-03.korotkov.co.uk/f/e/5/5/e5514fe464d985da7e04bdef3d59443c82.png)
![$$G(n,10)=G(n-1,0) \eqno (3)$$ $$G(n,10)=G(n-1,0) \eqno (3)$$](https://dxdy-04.korotkov.co.uk/f/f/f/5/ff51c547938ba3e28d6630e23e17e3a382.png)
(добавление нуля слева не изменяет "хорошести" последовательности, начинающейся с единицы, и то же самое верно для добавления единицы к последовательности, начинающейся с нуля).
По определению,
![$$G(n-1,0)+G(n-1,1)=G(n-1) \eqno (4)$$ $$G(n-1,0)+G(n-1,1)=G(n-1) \eqno (4)$$](https://dxdy-03.korotkov.co.uk/f/2/3/0/2303d2fe5a2c4f587e9671b79d9bf1d682.png)
Следовательно, из
![$(1-3)$ $(1-3)$](https://dxdy-04.korotkov.co.uk/f/f/2/3/f23926dd362801c509e6f946bfbfe4d082.png)
получаем
![$$G(n)=G(n-1)+G(n,11) \eqno (5)$$ $$G(n)=G(n-1)+G(n,11) \eqno (5)$$](https://dxdy-04.korotkov.co.uk/f/f/d/7/fd73f145b12f2292e6ea70e47586db9582.png)
Далее, при анализе
![$G(n,11)$ $G(n,11)$](https://dxdy-04.korotkov.co.uk/f/b/5/6/b56b0f8bebb6fc4cfa58466737a7690d82.png)
есть соблазн предположить, что "добавление четного количества единиц в начало последовательности не меняет ее свойства хорошести" и, тогда, очевидно,
![$$G(n,11)=G(n-2) \eqno (6)$$
$$G(n)=G(n-1)+G(n-2) \eqno (7)$$ $$G(n,11)=G(n-2) \eqno (6)$$
$$G(n)=G(n-1)+G(n-2) \eqno (7)$$](https://dxdy-03.korotkov.co.uk/f/2/9/f/29f73c009f1d36b43984599378b6845582.png)
Искомое рекуррентное соотношение найдено, известная последовательность Фибоначчи.
К сожалению, это не так, предположение про добавление четного кол-ва единиц неверно, чему легко построить контр-примеры:
![$01\to 1101$ $01\to 1101$](https://dxdy-01.korotkov.co.uk/f/0/e/1/0e19dbee7b9a72c2c77ab4c5f484610282.png)
- из хорошей последовательности получилась плохая
![$1011\to 111011$ $1011\to 111011$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5df80fa88e7fd74131af005f326fdf882.png)
- наоборот, из плохой хорошая.
Попробуем понять, чему равна разность между числом улучшаемых плохих последовательностей и ухудшаемых хороших, обозначим ее
![$d(n-2,11)$ $d(n-2,11)$](https://dxdy-02.korotkov.co.uk/f/5/a/3/5a3141505342475885b6bb8bd26b090f82.png)
. В этом обозначении верная формула для
![$G(n)$ $G(n)$](https://dxdy-04.korotkov.co.uk/f/f/6/5/f65042d63b48751a253ee3503ef0f2c482.png)
:
![$$G(n)=G(n-1)+G(n-2)+d(n-2,11) \eqno (7')$$ $$G(n)=G(n-1)+G(n-2)+d(n-2,11) \eqno (7')$$](https://dxdy-03.korotkov.co.uk/f/a/b/3/ab3b918674293e81bd89fa748abfcc8182.png)
Улучшаемые плохие последовательности удовлетворяют следующим критериям:
- в них нет двух нулей подряд;
и
- они начинаются с нечетного количества единиц, на единицу меньшего максимальной длины подпоследовательности из идущих подряд единиц, и, затем, нуля; пример:
![$1011$ $1011$](https://dxdy-01.korotkov.co.uk/f/0/3/3/033f4b5188965814650bfb05b5b4888482.png)
.
А, ухудшаемые хорошие таким:
- в них нет двух нулей подряд (по определению);
и
(
- они начинаются с нуля и не содержат
![$111$ $111$](https://dxdy-03.korotkov.co.uk/f/6/e/c/6ec98194778f0f05f8591ac27247f1ff82.png)
; легко видеть, что для любого
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
, такая последовательность ровно одна -
![$01010...$ $01010...$](https://dxdy-03.korotkov.co.uk/f/a/3/6/a3687e951f0eac0c792bb37c0a77f08e82.png)
;
или
- они начинаются с четного количества единиц, на единицу меньшего максимальной длины подпоследовательности из идущих подряд единиц, и, затем, нуля; пример:
![$110111$ $110111$](https://dxdy-03.korotkov.co.uk/f/6/2/c/62c3080155772073dd6d2666f1788b7c82.png)
.
)
Далее,
нестрого, в силу "симметричности" двух определений выше, можно предположить, что
![$$d(n-2,11)=-1 \eqno (8)$$ $$d(n-2,11)=-1 \eqno (8)$$](https://dxdy-01.korotkov.co.uk/f/0/c/5/0c5649b748484149f1dbe3dee927534d82.png)
для любого
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
. Но это не работает сразу для
![$n=3$ $n=3$](https://dxdy-03.korotkov.co.uk/f/a/a/6/aa6905d780872f0007f642420d7a2d9c82.png)
, и далее "то работает, то не работает".
Опровержение
![$(8)$ $(8)$](https://dxdy-01.korotkov.co.uk/f/0/e/1/0e12a8dbdaae2c913bfa4963acf25fcb82.png)
получено прямым построением хороших последовательностей для
![$n=1,2,...8$ $n=1,2,...8$](https://dxdy-04.korotkov.co.uk/f/b/e/c/bec96e0e84b5fbd60ec1a26bbee927be82.png)
и подсчете
![$G(n)$ $G(n)$](https://dxdy-04.korotkov.co.uk/f/f/6/5/f65042d63b48751a253ee3503ef0f2c482.png)
для них:
![$$1,2,3,4,6,10,16,26$$ $$1,2,3,4,6,10,16,26$$](https://dxdy-02.korotkov.co.uk/f/d/9/3/d939c888244ffb8bbacd901d2fa9eff582.png)
Следующие два члена
![$G(n)$ $G(n)$](https://dxdy-04.korotkov.co.uk/f/f/6/5/f65042d63b48751a253ee3503ef0f2c482.png)
, для
![$n=9,10$ $n=9,10$](https://dxdy-02.korotkov.co.uk/f/d/6/d/d6d93ea2f412ff691baf08ba338c4bb682.png)
, предположительно,
![$44$ $44$](https://dxdy-03.korotkov.co.uk/f/a/1/4/a14ecc0b3db4461a09d33c5a0fd7571682.png)
и
![$68$ $68$](https://dxdy-02.korotkov.co.uk/f/5/4/1/541408fe60cbd21fc0a6d70695ae360782.png)
, вручную для них строил только "ухудшаемые" и "улучшаемые" последовательности.
Первые члены
![$d(n-2,11)$ $d(n-2,11)$](https://dxdy-02.korotkov.co.uk/f/5/a/3/5a3141505342475885b6bb8bd26b090f82.png)
, начиная с
![$n=3$ $n=3$](https://dxdy-03.korotkov.co.uk/f/a/a/6/aa6905d780872f0007f642420d7a2d9c82.png)
:
![$$0,-1,-1,0,0,0,2,-2$$ $$0,-1,-1,0,0,0,2,-2$$](https://dxdy-01.korotkov.co.uk/f/4/9/e/49e57470886c1c930cda70be3f595f6982.png)
===09.01.15 11:25: Исправление супер-дурацкой ошибки! Конечно,
![$G(1)=1$ $G(1)=1$](https://dxdy-03.korotkov.co.uk/f/2/0/9/2097da9f5fe40a195e88d796238c279d82.png)
, а не
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
, как было в исходной версии.
Соответственно, d(1)=0, и формула (8) неверна сразу, для
![$n=3$ $n=3$](https://dxdy-03.korotkov.co.uk/f/a/a/6/aa6905d780872f0007f642420d7a2d9c82.png)
.
На OEIS ближайшая по смыслу, но, несовпадающая последовательность -
A143283===
Уважаемые коллеги, запрос о помощи следующий:
1. Возможно, я где-то проврался (в выводе и/или ручном построении), и вы сможете подсказать иной способ решения?
2. Если нет, и все правда мрачно (нет внятной линейной рекуррентности), то что можно сказать о
![$d(n,11)$ $d(n,11)$](https://dxdy-02.korotkov.co.uk/f/9/c/8/9c8b2863d3438c6c00f099572eb0379d82.png)
как функции
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
, как можно подойти к вопросу получения нижней и верхней оценки для ее значений?
Заранее большое спасибо!