Задачка по математике

Vitaminka

во задачку вспомнил на зачете по философии прочитал на доске
f(x_1,...,x_n)=x_1x_2+...+x_(n-1)x_n
сложение по модулю 2
найти число наборов на которых функция =1

Tfrn

#реш_n=2^{n-1}
Доказывается по индукции. Для n=1 верно.
Добавляем новую переменную x_{n+1} и рассматриваем два случая x_{n+1}=0,1.
В каждом случае решений #реш_n
#реш_{n+1}=2*#реш_n=2^n

Vitaminka

для n=3
получается 3 решения, и вообще я мягко говоря не понял почему там в каждом случае для 0 и 1 одно и тоже число решений

Ner83

мда

Tfrn

для n=3 получается 3 решения
Да ну!
x_1x_2x_3 = 011 или 110
А ты про какую функцию спрашиваешь, при n=3 я имею ввиду
x_1x_2+x_2x_3

Vitaminka

ну это 2

filippov2005

Для n = 4:
f = x_1*x_2 + x_2*x_3 + x_3*x_4
0000 0
0001 0
0010 0
0100 0
0101 0
0110 1
0111 0
1000 0
1001 0
1010 0
1011 1
1100 1
1101 1
1110 0
1111 1
Получилось 5 решений
ЗЫ Надо ввести две последовательсности - кол-во решений с 0 на конце, кол-во решений с 1 на конце и составить на них реккурентности и решить их.

Tfrn

Да это глюк был, я почему-то считал, что x_1x_2+x_2x_3+x_3 = x_1x_2+x_2(x_3+1)

Vitaminka

короче у меня получается послед.фиб

filippov2005

Пости ответ на n = 6

filippov2005

Вот ведь пропустил последовательность 0011. Так решений для n = 4 получается 6.
00000 0 10000 0
00001 0 10001 0
00010 0 10010 0
00011 1 10011 1
00100 0 10100 0
00101 0 10101 0
00110 1 10110 1
00111 0 10111 0
01000 0 11000 1
01001 0 11001 1
01010 0 11010 1
01011 1 11011 0
01100 1 11100 0
01101 1 11101 0
01110 0 11110 1
01111 1 11111 0
12 решений для n = 5

filippov2005

Что-то очень мало

Vitaminka

короче рек.формула такая S_n=2^(n-2)+2S_(n-2)
s_1=0 (так надо)
s_2=1
s_3=2
s_4=6
s_5=12
s_6=28
s_7=32+24=56
s_8=64+56=120
s_9=128+112=240

haltay

n = 3
011
110
Итого решений: 2
n = 4
0011
0110
1011
1100
1101
1111
Итого решений: 6
n = 5
00011
00110
01011
01100
01101
01111
10011
10110
11000
11001
11010
11110
Итого решений: 12
n = 6
000011
000110
001011
001100
001101
001111
010011
010110
011000
011001
011010
011110
100011
100110
101011
101100
101101
101111
110000
110001
110010
110100
110101
110111
111011
111100
111101
111111
Итого решений: 28

filippov2005

S_4 = 2^(4-2) + 2S_(4-2) = 4 + 2*S_2 = 4 + 2*1 = 6. Верно
S_5 = 2^(5-2) + 2*S_(5-2) = 8 + 2*S_3 = 8 + 2*2 = 12. Верно
Похоже на правду. Если оканчивается на 01 или 00, то в сумме 2*S_(n-2). Если на 10 или на 11, то в сумме 2^(n-2).
Правильная формула.

Vitaminka

00111 - откуда?

Vitaminka

считай заново короче n=3 неправильно

haltay

Я писал раньше, чтобы сумма была 0 . Сейчас исправил на 1.

haltay

Выборка побольше:
n = 3
011 110
Итого решений: 2
n = 4
0011 0110 1011 1100 1101 1111
Итого решений: 6
n = 5
00011 00110 01011 01100 01101 01111 10011 10110 11000 11001 11010 11110
Итого решений: 12
n = 6
000011 000110 001011 001100 001101 001111 010011 010110 011000 011001 011010 011110 100011 100110 101011 101100 101101 101111 110000 110001 110010 110100 110101 110111 111011 111100 111101 111111
Итого решений: 28
n = 7
0000011 0000110 0001011 0001100 0001101 0001111 0010011 0010110 0011000 0011001 0011010 0011110 0100011 0100110 0101011 0101100 0101101 0101111 0110000 0110001 0110010 0110100 0110101 0110111 0111011 0111100 0111101 0111111 1000011 1000110 1001011 1001100 1001101 1001111 1010011 1010110 1011000 1011001 1011010 1011110 1100000 1100001 1100010 1100100 1100101 1100111 1101000 1101001 1101010 1101110 1110011 1110110 1111000 1111001 1111010 1111110
Итого решений: 56
n = 8
00000011 00000110 00001011 00001100 00001101 00001111 00010011 00010110 00011000 00011001 00011010 00011110 00100011 00100110 00101011 00101100 00101101 00101111 00110000 00110001 00110010 00110100 00110101 00110111 00111011 00111100 00111101 00111111 01000011 01000110 01001011 01001100 01001101 01001111 01010011 01010110 01011000 01011001 01011010 01011110 01100000 01100001 01100010 01100100 01100101 01100111 01101000 01101001 01101010 01101110 01110011 01110110 01111000 01111001 01111010 01111110 10000011 10000110 10001011 10001100 10001101 10001111 10010011 10010110 10011000 10011001 10011010 10011110 10100011 10100110 10101011 10101100 10101101 10101111 10110000 10110001 10110010 10110100 10110101 10110111 10111011 10111100 10111101 10111111 11000000 11000001 11000010 11000100 11000101 11000111 11001000 11001001 11001010 11001110 11010000 11010001 11010010 11010100 11010101 11010111 11011011 11011100 11011101 11011111 11100011 11100110 11101011 11101100 11101101 11101111 11110000 11110001 11110010 11110100 11110101 11110111 11111011 11111100 11111101 11111111
Итого решений: 120
n = 9
000000011 000000110 000001011 000001100 000001101 000001111 000010011 000010110 000011000 000011001 000011010 000011110 000100011 000100110 000101011 000101100 000101101 000101111 000110000 000110001 000110010 000110100 000110101 000110111 000111011 000111100 000111101 000111111 001000011 001000110 001001011 001001100 001001101 001001111 001010011 001010110 001011000 001011001 001011010 001011110 001100000 001100001 001100010 001100100 001100101 001100111 001101000 001101001 001101010 001101110 001110011 001110110 001111000 001111001 001111010 001111110 010000011 010000110 010001011 010001100 010001101 010001111 010010011 010010110 010011000 010011001 010011010 010011110 010100011 010100110 010101011 010101100 010101101 010101111 010110000 010110001 010110010 010110100 010110101 010110111 010111011 010111100 010111101 010111111 011000000 011000001 011000010 011000100 011000101 011000111 011001000 011001001 011001010 011001110 011010000 011010001 011010010 011010100 011010101 011010111 011011011 011011100 011011101 011011111 011100011 011100110 011101011 011101100 011101101 011101111 011110000 011110001 011110010 011110100 011110101 011110111 011111011 011111100 011111101 011111111 100000011 100000110 100001011 100001100 100001101 100001111 100010011 100010110 100011000 100011001 100011010 100011110 100100011 100100110 100101011 100101100 100101101 100101111 100110000 100110001 100110010 100110100 100110101 100110111 100111011 100111100 100111101 100111111 101000011 101000110 101001011 101001100 101001101 101001111 101010011 101010110 101011000 101011001 101011010 101011110 101100000 101100001 101100010 101100100 101100101 101100111 101101000 101101001 101101010 101101110 101110011 101110110 101111000 101111001 101111010 101111110 110000000 110000001 110000010 110000100 110000101 110000111 110001000 110001001 110001010 110001110 110010000 110010001 110010010 110010100 110010101 110010111 110011011 110011100 110011101 110011111 110100000 110100001 110100010 110100100 110100101 110100111 110101000 110101001 110101010 110101110 110110011 110110110 110111000 110111001 110111010 110111110 111000011 111000110 111001011 111001100 111001101 111001111 111010011 111010110 111011000 111011001 111011010 111011110 111100000 111100001 111100010 111100100 111100101 111100111 111101000 111101001 111101010 111101110 111110011 111110110 111111000 111111001 111111010 111111110
Итого решений: 240

Vitaminka

ну и что ЧМы кто-нибудь помнит как решить рекуррентное соотношение?

filippov2005

Применим твою формулу несколько раз.
S_n=2^(n-2)+2S_(n-2) = 2^(n-2) + 2*(2^(n-4) + 2*S(n-4 = 2^(n-2) + 2*(n-3) + 4* S(n-4) = 2^(n-2) + 2^(n-3) + 2^(n-4) + ... + 2^(n-k) + 2^(k-1)*S(n-2k + 2) =
2^(n-1) - 2^(n-k) + 2^(k-1)*S(n-2k + 2).

Vitaminka

короче формула такая s_n=2^(n-1)-2^[(n-1)/2 ]
надо подработать

haltay

^(n-1) - 2^[(n+1)/2]
Здесь [x] - целая часть x

Vitaminka

no

z731a

S_{2n+1}=2^{2n}-2^n
S_{2n}=2^{2n-1}-2^{n-1}

filippov2005

[(n-1)/2]?

Vitaminka

во нормально

filippov2005

^(n-1) - 2^[(n-1)/2]

haltay

Точно. Там надо 2^[(n-1)/2]. Ошибся.
Оставить комментарий
Имя или ник:
Комментарий: