2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 11:05 
Аватара пользователя


07/01/16
906
Аязьма
Уважаемые коллеги, доброе утро!

Просьба помочь в решении следующей задачи (источник: 10ый класс, внешкольные умеренно "продвинутые" занятия).

Найти число двоичных последовательностей длины $n$, в которых нет двух нулей стоящих подряд, а все максимальные подпоследовательности из одних единиц нечетной длины.

Попытка решения:
1. Будем называть последовательности, обладающими данным свойством "хорошими", и обозначать их число как $G(n)$. Будем искать выражение для $G(n)$ в рекуррентном виде.

2. Если мы захотим говорить о "хороших" последовательностях длины $n$, начинающихся с определенной последовательности двоичных цифр $abcd...$, то их число будем обозначать как $G(n, abcd)$. Например, $G(4,01)$ - число хороших последовательностей длины $4$, начинающихся с $01$. Легко проверить, что таких последовательности две - $0101$ и $0111$, т.е. $G(4,01)=2$.

3. Набросок попытки решения, основанной на добавлении нулей и единиц в начало последовательности, с минимумом комментариев:
$$G(n)=G(n,01)+G(n,10)+G(n,11) \eqno (1)$$
$$G(n,01)=G(n-1,1) \eqno (2)$$
$$G(n,10)=G(n-1,0) \eqno (3)$$
(добавление нуля слева не изменяет "хорошести" последовательности, начинающейся с единицы, и то же самое верно для добавления единицы к последовательности, начинающейся с нуля).
По определению,
$$G(n-1,0)+G(n-1,1)=G(n-1) \eqno (4)$$
Следовательно, из $(1-3)$ получаем
$$G(n)=G(n-1)+G(n,11) \eqno (5)$$
Далее, при анализе $G(n,11)$ есть соблазн предположить, что "добавление четного количества единиц в начало последовательности не меняет ее свойства хорошести" и, тогда, очевидно,
$$G(n,11)=G(n-2) \eqno (6)$$
$$G(n)=G(n-1)+G(n-2) \eqno (7)$$
Искомое рекуррентное соотношение найдено, известная последовательность Фибоначчи.
К сожалению, это не так, предположение про добавление четного кол-ва единиц неверно, чему легко построить контр-примеры:
$01\to 1101$ - из хорошей последовательности получилась плохая
$1011\to 111011$ - наоборот, из плохой хорошая.
Попробуем понять, чему равна разность между числом улучшаемых плохих последовательностей и ухудшаемых хороших, обозначим ее $d(n-2,11)$. В этом обозначении верная формула для $G(n)$:
$$G(n)=G(n-1)+G(n-2)+d(n-2,11) \eqno (7')$$
Улучшаемые плохие последовательности удовлетворяют следующим критериям:
- в них нет двух нулей подряд;
и
- они начинаются с нечетного количества единиц, на единицу меньшего максимальной длины подпоследовательности из идущих подряд единиц, и, затем, нуля; пример: $1011$.
А, ухудшаемые хорошие таким:
- в них нет двух нулей подряд (по определению);
и
(
- они начинаются с нуля и не содержат $111$; легко видеть, что для любого $n$, такая последовательность ровно одна - $01010...$;
или
- они начинаются с четного количества единиц, на единицу меньшего максимальной длины подпоследовательности из идущих подряд единиц, и, затем, нуля; пример: $110111$.
)
Далее, нестрого, в силу "симметричности" двух определений выше, можно предположить, что
$$d(n-2,11)=-1 \eqno (8)$$
для любого $n$. Но это не работает сразу для $n=3$, и далее "то работает, то не работает".
Опровержение $(8)$ получено прямым построением хороших последовательностей для $n=1,2,...8$ и подсчете $G(n)$ для них:
$$1,2,3,4,6,10,16,26$$
Следующие два члена $G(n)$, для $n=9,10$, предположительно, $44$ и $68$, вручную для них строил только "ухудшаемые" и "улучшаемые" последовательности.
Первые члены $d(n-2,11)$, начиная с $n=3$:
$$0,-1,-1,0,0,0,2,-2$$
===09.01.15 11:25: Исправление супер-дурацкой ошибки! Конечно, $G(1)=1$, а не $2$, как было в исходной версии.
Соответственно, d(1)=0, и формула (8) неверна сразу, для $n=3$.
На OEIS ближайшая по смыслу, но, несовпадающая последовательность - A143283
===
Уважаемые коллеги, запрос о помощи следующий:
1. Возможно, я где-то проврался (в выводе и/или ручном построении), и вы сможете подсказать иной способ решения?
2. Если нет, и все правда мрачно (нет внятной линейной рекуррентности), то что можно сказать о $d(n,11)$ как функции $n$, как можно подойти к вопросу получения нижней и верхней оценки для ее значений?
Заранее большое спасибо!

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 11:52 
Аватара пользователя


29/06/15
272
[0,\infty )
waxtep в сообщении #1089194 писал(а):
... сможете подсказать иной способ решения?
Есть другой способ, который не может не привести к ответу. Рассмотрим случайное блуждание по графу из трех стостояний:
1.На конце строящейся допустимой последовательности 0
2. На конце единицы, в нечетном количестве.
3. На конце единицы, в четном количестве.
Из состояний 1 или 3 - можно перейти только в 2. А из 2 в любое из 1 и 3 (то есть состояние 2- единственная точка бифуркации)
Вот и надо найти число допустимых n-вершинных путей на этом графе.
Хотя, конечно, надо и Ваш текст проанализировать, он разумен, но спешу(

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 12:20 
Заслуженный участник
Аватара пользователя


18/01/13
11952
Казань
waxtep
Честно говоря, читать весь текст затруднительно... Тем более, у вас там много "сопутствующих рассуждений". А вы не пробовали разбить все случаи по числу нулей (групп единиц)?
Например, обозначим через $N(n)$ число искомых последовательностей, начинающихся и заканчивающихся единичками. Тогда ответом будет $N(n)+N(n-2)$ при нечетном $n$ и $2N(n-1)$ при четном.
А для фиксированного числа групп единичек всё можно свести к известной схеме "предметы и перегородки", то есть к размещениям с повторениями.
Правда не уверена, что там получится формула в замкнутом виде...

-- 09.01.2016, 12:27 --

Нет, кажется, суммируется! Причём ответ подозрительно простой...

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 12:47 
Аватара пользователя


07/01/16
906
Аязьма
iancaple в сообщении #1089205 писал(а):
1.На конце строящейся допустимой последовательности 0
2. На конце единицы, в нечетном количестве.
3. На конце единицы, в четном количестве.
Из состояний 1 или 3 - можно перейти только в 2. А из 2 в любое из 1 и 3 (то есть состояние 2- единственная точка бифуркации)

Спасибо!
Здесь, если я правильно понимаю, вот в чем коварство: нельзя запретить переход из 3 в 1.
Например, мы находимся в вершине 011; действительно, последовательность 0110, соответствующая переходу 3->1, будет "плохой". Но, более длинная 0110111, находящаяся на этом же пути, будет "хорошей", т.е. не получается запретить такие переходы.

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 12:52 
Заслуженный участник
Аватара пользователя


18/01/13
11952
Казань
waxtep
Не надо рекуррентной формулы! Я попробовала посчитать "по-своему", значение $N(n)$ -- проще некуда! Вы, кстати, провели эксперимент? Проверили, сколько последовательностей получается при небольших $n$?

(Оффтоп)

Последовательности $101110101$ можно поставить в соответствие последовательность $1(01)(11)(01)(01)$... хм... дальше не подсказываю, будет уже полное решение!

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:05 
Аватара пользователя


07/01/16
906
Аязьма
provincialka в сообщении #1089214 писал(а):
А вы не пробовали разбить все случаи по числу нулей (групп единиц)?
Например, обозначим через $N(n)$ число искомых последовательностей, начинающихся и заканчивающихся единичками. Тогда ответом будет $N(n)+N(n-2)$ при нечетном $n$ и $2N(n-1)$ при четном.
...

Нет, кажется, суммируется! Причём ответ подозрительно простой...

Спасибо! Да, думал о таком подходе, но не смог сообразить, как в нем формализовать условие нечетности длин максимальных последовательностей из идущих подряд единиц. Я могу Вас попросить развернуть этот момент?
Плюс, меня смущает, что последовательности $G(n)$ нет в OEIS, т.е. простого аналитического вида ждать трудно(?) хотя, конечно, я мог просто наврать при ручном построении :roll: Подскажите, пожалуйста, у Вас получается, например, $G(6)=10$?

PS: прошу прощения за длинноты в тексте, хотел показать, в какие тупики уже заходил.

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:11 
Заслуженный участник
Аватара пользователя


18/01/13
11952
Казань
А у меня так не получается!
У меня трудность в том, что нельзя в учебном разделе писать полные решения. Но я советую вам сосредоточиться на вычислении $N(2k+1)$, остальное приложится.
Например, при $n=6$ последовательность обязательно начинается или заканчивается нулем. То есть $G(6)=2N(5)$.
В $N(5)$ входят такие последовательности: $(11111),(11101),(10111),(10101)$, всего 4, то есть $G(6)=8$ Откуда у вас еще две последовательности взялись?

-- 09.01.2016, 13:13 --

Вы прочитали подсказку в оффтопе? На самом деле, данную последовательность можно некиим способом получить из произвольной, но более короткой...

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:14 
Аватара пользователя


07/01/16
906
Аязьма
provincialka в сообщении #1089225 писал(а):
waxtep
Не надо рекуррентной формулы! Я попробовала посчитать "по-своему", значение $N(n)$ -- проще некуда! Вы, кстати, провели эксперимент? Проверили, сколько последовательностей получается при небольших $n$?

Заглянул в "спойлер", попробую побороться, спасибо! Кас. эксперимента для небольших $n$, да, конечно, вот они для $n=1,...,8$:
$$1,2,3,4,6,10,16,26$$
и, с меньшей уверенностью могу сказать, что дальше будут члены 44 и 68 (для них проводил только неполное построение - какие последовательности длины $n-2$ изменят свойство "хорошести" при добавлении к ним двух единиц слева). У Вас столько же получается, например для $n=6, 7$? :roll:

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:17 
Заслуженный участник
Аватара пользователя


18/01/13
11952
Казань
У меня $N(2k+1)=2^k$. И есть простой алгоритм, как найти это число без долгих построений!
Ой! Надеюсь, меня модераторы не накажут ...

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:20 
Аватара пользователя


07/01/16
906
Аязьма
provincialka в сообщении #1089230 писал(а):
В $N(5)$ входят такие последовательности: $(11111),(11101),(10111),(10101)$, всего 4, то есть $G(6)=8$ Откуда у вас еще две последовательности взялись?

Вот они, 10 хороших последовательностей для $n=6$, в порядке возрастания:
010101
010111
011101
011111
101010
101110
110111
111010
111011
111110

И, 6 штук для $n=5$:
01010
01110
10101
10111
11101
11111

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:24 
Заслуженный участник
Аватара пользователя


18/01/13
11952
Казань
waxtep в сообщении #1089232 писал(а):
вот они для $n=1,...,8$:
$$1,2,3,4,6,10,16,26$$

Это $G$ или $N$? У меня получилось $1,2,3,4,6,8,12,16,24,...$

-- 09.01.2016, 13:29 --

А! Я поняла! Мы по-разному понимаем условие задачи! насчёт "максимальных последовательностей из 1".
Там ведь сказано "ВСЕ максимальные последовательности". Например, в цепочке $10111101101$ максимальными будут подпоследовательности $(1),(1111),(11),(1)$, а не только $(1111)$! Иначе зачем о них говорить во множественном числе!
А вот эта подпоследовательность $10\underbrace{111}_{}101101$ максимальной не будет! Потому что её можно продолжить ещё на одну единичку.

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:37 
Аватара пользователя


07/01/16
906
Аязьма
provincialka в сообщении #1089233 писал(а):
У меня $N(2k+1)=2^k$. И есть простой алгоритм, как найти это число без долгих построений!
Ой! Надеюсь, меня модераторы не накажут ...

по следующему Вашему сообщению, понял, что не те примеры привожу, т.к. говорю про $G$, а не про $N$; прошу прощения, сейчас попробую разобраться.
А последовательность 1,2,3,4,6,8,12,16,24 - это у Вас для $G$, верно? Если да, посмотрите плиз мой пример для $G(6)$ - я там выписал все 10 (а не 8) последовательностей в явном виде.

-- 09.01.2016, 13:42 --

provincialka в сообщении #1089237 писал(а):

А! Я поняла! Мы по-разному понимаем условие задачи! насчёт "максимальных последовательностей из 1".

О! Вот это похоже "в яблочко"! Я решал не ту задачу, которую задали :-)
Про самые длинные подпоследовательности, а не про ограниченные нулями.
СПАСИБО!!!

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:48 
Заслуженный участник
Аватара пользователя


18/01/13
11952
Казань
waxtep
Видимо, да. "Моя" формулировка, во-первых, дает простое решение (и простой ответ). А во-вторых, соответствует тому, как слово "максимальный" понимает высшая математика: тот, который нельзя увеличить, а не тот, который больше других о размеру.

А вы все-таки напишите своё решение! (если напишете, я смогу в ответ написать своё)

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 13:59 
Аватара пользователя


07/01/16
906
Аязьма
provincialka в сообщении #1089250 писал(а):
waxtep
Видимо, да. "Моя" формулировка, во-первых, дает простое решение (и простой ответ). А во-вторых, соответствует тому, как слово "максимальный" понимает высшая математика: тот, который нельзя увеличить, а не тот, который больше других о размеру.

А вы все-таки напишите своё решение! (если напишете, я смогу в ответ написать своё)

Да, я, честно говоря, не воспринял "максимальную подпоследовательность" за термин, а самоуверенно списал на корявость формулировки условия :-) сейчас попробую порешать, напишу.

 Профиль  
                  
 
 Re: Нахождение количества двоичных последовательностей
Сообщение09.01.2016, 15:50 
Аватара пользователя


07/01/16
906
Аязьма
Найти число двоичных последовательностей длины $n$, в которых нет двух нулей стоящих подряд, а все максимальные подпоследовательности из одних единиц нечетной длины.

Решение:
$$G(n)=G(n,01)+G(n,10)+G(n,11) \eqno (1)$$
$$G(n,01)=G(n-1,1) \eqno (2)$$
$$G(n,10)=G(n-1,0) \eqno (3)$$
$$G(n-1,0)+G(n-1,1)=G(n-1) \eqno (4)$$
Следовательно, из $(1-3)$ получаем
$$G(n)=G(n-1)+G(n,11) \eqno (5)$$
Далее, новое равенство для $G(n,11)$:
$$G(n,11)=G(n-2,1) \eqno (6)$$
(добавление двух единиц слева оставлят хорошими только последовательности, начинающиеся с единицы, но не с нуля)
Рассмотрим, что такое $G(m,1)$ и получим рекуррентно:
$$G(m,1)=G(m)-G(m,0)=G(m)-G(m-1,1)=$$
$$=G(m)-G(m-1)+G(m-2)-...+{-1}^{m-1}G(1,1) \eqno (7)$$
Подставим $(7)$ в $(6)$ и далее в $(5)$, записанное для $n$ и $n+1$:
$$G(n)=G(n-1)+G(n-2)-G(n-3)+...+{-1}^{n-1}G(1,1) $$
$$G(n+1)=G(n)+G(n-1)-G(n-2)+...+{-1}^{n}G(1,1) \eqno (8)$$
И сложим, получая
$$G(n+1)+G(n)=G(n)+2G(n-1) \eqno (9)$$
Т.е.
$$G(n+1)=2G(n-1) \eqno (9')$$
(Заметим, что это равенство верно только при $n\ge 3$)
Значения для $n<3$ вычисляем эмпирически $(1,2,3)$, а далее, $G(2m)=2^m, G(2m+1)=3\cdot2^{m-1}$, что и дает первые члены
$$1,2,3,4,6,8,12,16,24,32,48,...$$

-- 09.01.2016, 15:55 --

provincialka в сообщении #1089250 писал(а):
waxtep

А вы все-таки напишите своё решение! (если напишете, я смогу в ответ написать своё)

Решил, посмотрите плз предыдущее сообщение в теме. Таки через рекурретность, осознаю, что довольно громоздко, но, гм, это решение :-)
Я воспроизвел в сообщении условие и начало поиска отношеия; новое начинается с формулы (6) - в правильной постановке задачи упрощается и рекурретно выражается $G(n,11)$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group