Задача
COM-B1-M10-P012 Без соседних чисел
#12
★★☆☆☆ Уровень 2 из 5
Сколько подмножеств множества \(\{1,2,\ldots,7\}\) не содержат двух соседних чисел?
Разделите по тому, входит ли число \(7\).
Пусть \(a_n\) - число таких подмножеств для \(\{1,\ldots,n\}\). Если \(n\) не входит, есть \(a_{n-1}\) способов. Если \(n\) входит, то \(n-1\) не входит, и остается \(a_{n-2}\) способов. Значит \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Поэтому \(a_7=34\).
Связывает строки и подмножества.