Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет neklyueva ([info]neklyueva)
@ 2008-11-29 19:09:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Арифметика для взрослых
Сколько существует двоичных последовательностей длинны N, в которых никакие две единицы не стоят рядом.
Получить наиболее простую зависимость от N.

Примечание: рядовому школьку эта задача может оказаться непосильной (хотя знаний и должно хватить), но матшкольнику решение этой задачи вполне доступно.


(Добавить комментарий)


[info]igorpashev
2008-11-30 01:47 (ссылка)
Пока я их могу найти :-)
http://lj.rossia.org/users/igorpashev/12522.html

Завтра буду считать.

(Ответить) (Ветвь дискуссии)


[info]neklyueva
2008-11-30 01:49 (ссылка)
Ага, ага...

(Ответить) (Уровень выше)


[info]666
2008-11-30 04:05 (ссылка)
F(n+2)

(Ответить) (Ветвь дискуссии)


[info]igorpashev
2008-11-30 16:49 (ссылка)
Действительно, последовательность Фибоначчи.

http://lj.rossia.org/users/igorpashev/12522.html?thread=5866#t5866

Почему?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]neklyueva
2008-11-30 18:25 (ссылка)
Почему же ее нельзя написать?
Не такая уж это и сложная формула.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]igorpashev
2008-11-30 20:30 (ссылка)
Формула Бине :-)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]neklyueva
2008-11-30 21:56 (ссылка)
Канешна.

(Ответить) (Уровень выше)


[info]igorpashev
2008-12-01 09:16 (ссылка)
Главный вопрос — как возникла такая задача?

Интересно, если это проверить на троичной системе,
не получится ли последовательности трибоначчи?

Пошёл поверять.

(Ответить) (Ветвь дискуссии)


[info]neklyueva
2008-12-01 09:36 (ссылка)
Ага, похоже.
Но зуб не дам.
Интересно проверить.
Только учтите, что это могут оказаться "другие" числа Фибоначи, то есть рекурентная формула та же, а начальные члены другие.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]igorpashev
2008-12-01 14:45 (ссылка)
Проверил для троичной системы,
ничего особенного не заметил:

Числа без 11:     Числа без 22:
N = 1, t = 3      N = 1, t = 3
N = 2, t = 8      N = 2, t = 8
N = 3, t = 22     N = 3, t = 22
N = 4, t = 60     N = 4, t = 60
N = 5, t = 164    N = 5, t = 164
N = 6, t = 448    N = 6, t = 448
N = 7, t = 1224   N = 7, t = 1224
N = 8, t = 3344   N = 8, t = 3344
N = 9, t = 9136   N = 9, t = 9136


Числа без 11, 22:
N = 1, t = 3
N = 2, t = 7
N = 3, t = 17
N = 4, t = 41
N = 5, t = 99
N = 6, t = 239
N = 7, t = 577
N = 8, t = 1393
N = 9, t = 3363

Числа без 11, 22, 12, 21:
N = 1, t = 3
N = 2, t = 5
N = 3, t = 11
N = 4, t = 21
N = 5, t = 43
N = 6, t = 85
N = 7, t = 171
N = 8, t = 341
N = 9, t = 683


Наверно исходная задача — следствие, а не причина последовательности Фибоначчи :-)

(Ответить) (Уровень выше)


[info]ppkk
2008-12-08 20:16 (ссылка)
"длины"

Кроме конструктивного соображения, дающего рекуррентную формулу (по которой матшкольник должен уметь писать явную!), можно комбинаторно рассуждать: с биномиальными коэффициентами, заодно соотношение получится (но это криво, потому что надо рассматривать всевозможные сочетания a*"0" и b*"10", где a+2b=n+1, учитывая, что последний символ [всегда 0] мы отбросим).

n=6: C_7^0 + C_6^1 + C_5^2 + C_4^3 = 1 + 6 + 10 + 4 = 21 — восьмое число Фибоначчи.

Типа, конструкция — способ доказать формулу.

(Ответить)