2014 dxdy logo

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

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


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


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

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

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

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

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



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


18/01/13
12044
Казань
Ох... что-то нет азарта всё это читать. Вот мое решение.

Рассмотрим "хорошие" последовательности (длины $n$), начинающиеся и заканчивающиеся 1, обозначим их число через $N(n)$. Легко заметить, что такие последовательности существуют только для нечетного $n=2k+1$. Разобьём последовательность на первую единицу и пары цифр: $1110101111101=1(11)(01)(01)(11)(11)(01)$. Пар будет $k$ штук и они будут иметь вид $(01)$ или $(11)$. Поставим им в соответствие цифры $0$ и $1$. Получим последовательность из единицы и $k$ цифр $0$ и $1$ в произвольном порядке (для примера -- $1100110$). Таких последовательностей существует $2^k$. Значит, $N(2k+1)=2^k$.
Теперь вспоминаем про связь $G(n)$ и $N(n)$. Получаем, что
$$G(2k)=2N(2k-1)=2\cdot2^{k-1}=2^k$$ $$G(2k+1)=N(2k+1)+N(2k-1)=2^k+2^{k-1}=3\cdot2^{k-1}$$

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


29/06/15
277
[0,\infty )
provincialka в сообщении #1089321 писал(а):
Получаем, что
$$G(2k)=2N(2k-1)=2\cdot2^{k-1}=2^k$$ $$G(2k+1)=N(2k+1)+N(2k-1)=2^k+2^{k-1}=3\cdot2^{k-1}$$

К сему подпись: W.Edwin Clark,2008 A063579
Только его ответы надо делить на 2, так как начало и конец в позиции 3 у нас не допускаются. А номера состояний у него такие же, как у меня в посте 2 (случайное совпадение)
Извините, вернулся к шапочному разбору, задача и раньше на форумах была
И еще интересное исключение: $G(1)=2$

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


07/01/16
1426
Аязьма
provincialka в сообщении #1089321 писал(а):
Вот мое решение

Согласен, Ваш способ гораздо изящнее, еще раз большое спасибо! :-)

В качестве оффтопика: мне этот способ субъективно дался труднее, поломал голову над связью между $G$ и $N$, а потом снова попытался "соскочить" на рекуррентность, не выписывая в явном виде выражения для $N$. Это в данном варианте не дает решения, а только равенство $G(2m)$ удвоенной знакопеременной сумме $G$ для нечетных индексов $\lt 2m$, типа $16=2(12-6+3-1)$ и т.п.

-- 09.01.2016, 18:11 --

iancaple в сообщении #1089329 писал(а):
К сему подпись: W.Edwin Clark,2008 A063579
Только его ответы надо делить на 2, так как начало и конец в позиции 3 у нас не допускаются. А номера состояний у него такие же, как у меня в посте 2 (случайное совпадение)
Извините, вернулся к шапочному разбору, задача и раньше на форумах была
И еще интересное исключение: $G(1)=2$

Спасибо за участие! Наверное, опечатка, Вы имеете в виду A029744?
Мне очень помогла provincialka, в первую очередь, правильно понять условие решаемой задачи :-) И способ решения, конечно, элегантный, я бы до него точно не быстро допер. В обоснование своего подхода могу только сказать, что он вызван желанием максимально изолироваться от рассмотрения структуры изучаемых последовательностей, поиск легкого пути.

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


29/06/15
277
[0,\infty )
waxtep в сообщении #1089357 писал(а):
iancaple в сообщении #1089329 писал(а):
К сему подпись: W.Edwin Clark,2008 A063579

Наверное, опечатка, Вы имеете в виду A029744?

Другая опечатка, A063759
Примерно в 2006м решалась на аопсе. Потом Кларк написал в oeis о связи ответа этой задачи с уже имевшейся там последовательностью, может, в связи с этим, ну неважно. Потом еще на одном форуме, и там пошла ссылка на этот аопс, сейчас не найти. Но я и так помню, что все математики, решавшие задачу, не сговариваясь, работали с моделью случайных блужданий, как более наглядной, и я полагал, что так проще объяснить, в уме решается. provincialka- редкий человек, увидевшая задачу впервые, но ответ у нее вышел верный с одной поправкой, поздравляю :)

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


18/01/13
12044
Казань
"Поправка" -- это про $G(1)$? Ну, я просто не стала на этом заострять внимание... А что касается "случайных блужданий" -- я их просто плохо знаю :facepalm:

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


07/01/16
1426
Аязьма
iancaple в сообщении #1089466 писал(а):
waxtep в сообщении #1089357 писал(а):
iancaple в сообщении #1089329 писал(а):
К сему подпись: W.Edwin Clark,2008 A063579

Наверное, опечатка, Вы имеете в виду A029744?

Другая опечатка, A063759

Рискну немного позанудничать, A029744 подходит лучше, т.к. это в явном виде "Numbers of the form $2^n$ or $3\cdot2^n$" - в точности решение данной задачи, без поправок. (Прошу прощения, я, похоже, не уловил связи с последовательностю A063759, просто фиксирую лобовое наблюдение, что в ней отсутствует значение $G(2)=2$ из решения данной задачи).

И еще капля: в методе, предложенном provincialka, можно обойтись без "заглядывания внутрь" последовательности $N(n)$, если заметить, что последовательности $N(n+2)$ могут быть однозначно получены из $N(n)$ добавлением к ним слева $10$ или $11$. Это сразу дает $N(n+2)=2\cdot N(n)$ и ответ в явном виде для $N$ и $G$.

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


29/06/15
277
[0,\infty )
Кларк рассматривал последовательности из $1,2,3$, такие, что соседние члены отличаются ровно на единицу.Чтобы его последовательности превратить в Ваши, надо тройки и двойки заменить на единицы, а его единицы на наши нули. А у нас еще условие, чтобы в начале и в конце не было тройки, только это гарантирует нечетность на концах. Оказывается, это просто сдвигает последовательность вправо , т.к. свойство остается: увеличение степени двойки в 2 раза происходит в 2 этапа, сначала в $\frac 32$ раза, потом в $\frac 43$ раза -а как еще оно могло происходить, чтобы числа оставались целыми. То, что увеличение при $n>1$ происходит в одно и то же число раз, следует из того, что $10$ или $01$ -ровно одну из них, и $11$ можно вставлять после 1-й позиции, чтоб не нарушить концы.

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


07/01/16
1426
Аязьма
iancaple в сообщении #1089532 писал(а):
Кларк рассматривал последовательности из $1,2,3$, такие, что соседние члены отличаются ровно на единицу.Чтобы его последовательности превратить в Ваши, надо тройки и двойки заменить на единицы, а его единицы на наши нули. А у нас еще условие, чтобы в начале и в конце не было тройки, только это гарантирует нечетность на концах. Оказывается, это просто сдвигает последовательность вправо , т.к. свойство остается: увеличение степени двойки в 2 раза происходит в 2 этапа, сначала в $\frac 32$ раза, потом в $\frac 43$ раза -а как еще оно могло происходить, чтобы числа оставались целыми. То, что увеличение при $n>1$ происходит в одно и то же число раз, следует из того, что $10$ или $01$ -ровно одну из них, и $11$ можно вставлять после 1-й позиции, чтоб не нарушить концы.

В значительной степени понял, спасибо Вам! Что не допонял, оставлю себе на додумывание :-)
А метод со вставкой двух цифр на вторую позицию, это, похоже, самый быстрый способ решения! (только в нем надо не забыть аккуратно обработать тот самый исключительный случай $n=3$, где последовательность $011$ "нехороша")

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

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



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

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


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

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