Обозначим x1 <> x2 через y1, x3 <> x4 через y2 и т.д. Получим систему
y1 or y2 = 1 y2 or y3 = 1 y3 or y4 = 1 y4 or y5 = 1
Количество наборов y1..y5, удовлетворяющих данным условиям - 13. Набор будет являться решением системы, если в нем нет идущих подряд нулей - тогда в каждой из пар (y1,y2), (y2,y3), (y3,y4), (y4,y5) будет хотя бы одна единица, т.е. все операции or также будут давать единицу. Можно перебрать такие наборы вручную:
Либо воспользоваться формулой F(n) = F(n-1) + F(n-2), F(0) = 1, F(1) = 2; Тогда F(5) = 13. Здесь F(n) - количество последовательностей длины n, где нет двух идущих подряд нулей - их можно разбить на две группы, в одной на первой позиции стоит 1 (их F(n-1), т.к. оставшиеся элементы выбираются в соответствии с тем же правилом), в другой - 0 (их F(n-2), т.к. раз в последовательности нет двух идущих подряд нулей, на второй позиции обязана стоять единица).
Далее каждому значению y соответствуют две пары возможных значений x-ов. Т.е., например, y1 = 1 соответствуют x1 = 1, x2 = 0 и x1 = 0, x2 = 1, а y1 = 0 соответствуют x1 = 0, x2 = 0 и x1 = 1, x2 = 1.
В наборе y1..y5 каждому y соответствует два набора x -> всему набору y соответствует 2^5 = 32 набора x. Всего 13 наборов y -> 13 * 32 = 416 наборов x.
Предлагаю для начала рассматривать только значения вида (x.. xor x..) Очевидно, скажем, если (x1 xor x2) = 0, то (x3 xor x4) = 1 Так что достаточно посчитать количество цепочек значений xor'ов, где нет двух стоящих подряд 0. Всего пять значений, так что можно посчитать все вручную. Например, составить дерево. Получилось 13 цепочек. Т.к. каждому значению .. xor .. соответствует пара возможных значений x (01 и 10), каждая цепочка будет соответствовать 2^5 = 32 возможным значениям x1..10. Соответственно, ответ: 13 * 32 = 416
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку
