Рассматриваются наборы из 0 и 1 длины n

Runa

Помогите решить задачу или хотя бы подкиньте идею её решения.
Рассматриваются наборы из 0 и 1 длины n.
Нужно посчитать число таких наборов, для которых выполняется следующее свойство:
при всех k от 1 до n-1 преффикс длины k не совпадает с суффиксом длины k для этого набора.

starmaster

При четном n достаточно решить эту задачу для k от 1 до n/2 и ответ удвоить...

Runa

Почему удвоить?
Искомых же наборов должно быть меньше или столько же, а никак не больше?!

starmaster

Больше!
Ведь они строятся независимо для каждого к

Runa

Например, для n=4 подходят 6 наборов:
1000, 1100, 1110 и противоположные 0111, 0011, 0001.
Если проверим условие для k=1,2 (2=n\2 то это как раз будут все наборы и при данном n ответ не нужно умножать на 2.

tanuhka3

а что такое преффикс и суффикс?

tanuhka3

уже понял

Runa

если набор x_1, x_2,..., x_(n-1 x_n, то преффиксом и суффиксом длины k будут соответственно
x_1, x_2,...,x_(k-1x_k и x_(n-k+1x_(n-k+2...,x_(n-1x_n

tanuhka3

а посчитать те для которых оно совпадает и вычесть из 2 в энной ?

tinka2302

Посчитать те для которых совпадает тоже геморроисто, особенно если префикс и суффикс пересекаются.

tanuhka3

если они пересекаются больше чем наполовину то посл-ть симметрична

Sync755

Причем совпадает хотя бы для одного k.
Можно взять конкретное k,для него посчитать,
а потом посуммировать по k от 1 до n-1.
Хотя так можно в такую чащу залезть.... Ууууу...
Даня

tinka2302

Точно

tanuhka3

по-моему 2 в эн минус первой

tanuhka3

а 1010 и 0101 подходят?

Runa

*(n-1)-это только кол-во тех наборов, у которых первый символ и последний различны.
А ответ, конечно же будет намного меньше 2*(n-1).
В моём примере для n=4 ответ 6.

Runa

и 0101 не подходят, так как для k=2 преффикс длины 2 совпадает с суффиксом длины 2.

Runa

Если считать "плохие" наборы для каждого k, то эти случаи будут пересекаться.
Так, например, набор 101010...1010 будет "плохим" для любого чётного k.
Поэтому так тоже не получается решить.

antcatt77

А n большое?

Runa

n-произвольное натуральное число

antcatt77

то есть ты хочешь формулу? А она вообще есть?

Runa

Насчёт ответа неизвестно.
Хотелось бы формулу (хотя пока не верится, что она есть) или рекурретное соотношение.
Может хоть удасться посчитать ассимптотику.

antcatt77

Так прогони на компе, посмотри что получается.

Runa

В принципе, мне всё равно, что получится для n=10, 100 и т.д... А для больших n не вычислишь.
Нужна либо формула, либо рекурретное соотношение, либо ассимптотика.
Почти уверен, что красивого ответа, который можно увидеть по маленьким n, не будет.

tanuhka3

у меня есть тупейшая рекуррентная формула но явно из нее ничего не вылазит

starmaster

А это что-то практическое?

Runa

Напиши, какое соотношение?
Бывает, что из очевидных рекуррентных соотношений удаётся получить ценную информацию или вообще ответ.

Runa

Я бы сказал это практическо-теоретическое

starmaster

А область применения?

Runa

криптография
подробнее - без комментариев

antcatt77

Для больших n можно тоже посчитать на компе. Генерируешь рандомные длинные последовательности и смотришь отношение хороших к плохим.

Runa

Это отношение стремится к 0

tanuhka3

c(n)=2^n-c(1)*c(n-2) - c(2)*c(n-4) - c(4)*c(n-6) -...- c([n/2])*c(0 или 1 в зависимости от четности n) обший вид слагаемого c(k)*c(n-2k)
c(1)=0;
c(2)=2;
c(3)=4;
c(4)=6;

Runa

Что-то так сразу не могу понять, что именно такая зависимость получается.

starmaster

Ну вот.
Так сразу - и без коментариев

Timoha

С(5)=12 имхо
кажется, это не соответствует формуле ?
или я ошибаюсь ?

tanuhka3

для которых совпадают
а всего 2^5-12=20

Timoha

есть подозрение (вроде получилось доказать его что если нет совпадающих префиксов и суффиксов длины <= n/2, то тогда не может быть совпадающих префиксов и суффиксов большей длины. Вопрос в том, дает ди это какое-то облегчение...

Timoha

все равно.
ни 12, ни 20 как-то с формулой не увязываются

Runa

Да, похоже, что это верно.
Возможно, теперь будет полегче.

tanuhka3

Походу я немного неправ.Но реальная формула должна быть похожа на эту (понятно откуда она берется (?
Наверное проще посчитать на компе: смотря что требуется ответ или асимптотика

Runa

лучше ответ

Runa

"понятно откуда она берется"?
нет, пока не понятна

tanuhka3

я еще подумаю чуток...

tanuhka3

^n - c(1)*2^(2n-2) - c(2)*2^(2n-4) - c(3)*2^(2n-6)-...
.. -c([n/2])*(2 или 1 в зависимости от четности n)
с(1)=2
c(2)=2
c(3)=4
c(4)=6

tanuhka3

Меня с компа сейчас сгонят...

Diamond7

Ты попробуй туда что-нибудь подставить (2 например короче это не она.

Timoha

>>2^n - c(1)*2^(2n-2) - c(2)*2^(2n-4) - c(3)*2^(2n-6)-...
>>.. -c([n/2])*(2 или 1 в зависимости от четности n)
для n=4:
2^4-2*2^(2*4-2)-2*2^(2*4-4) = 16-128-32=-144 ?!?!?!

Runa

Последнее соотношение точно неправильное, ведь 2^n - ... будет отрицательным числом

tanuhka3

^4-c(1)*2^2-c(2)*2^0=16-2*4-2*1=16-8-2=6

tanuhka3

sorry там степени не 2^(2n-k) а 2^(n-k)

tinka2302

Каждая сложная проблема имеет простое, доступное для понимания неправильное решение. (с)

tanuhka3

^n - c(1)*2^(n-2) - c(2)*2^(n-4) - c(3)*2^(n-6)-...
.. -c([n/2])*(2 или 1 в зависимости от четности n)
с(1)=2
c(2)=2
c(3)=4
c(4)=6

Runa

Поясни немного, пожалуйста, как получилось это соотношение, тогда легче будет понять верно оно или нет.

tanuhka3

Тут ведь был еще топик насчет неправильной формулы для 4х?

tanuhka3

Считаем хорошие посл-ти как разность 2^n и плохие
а плохие получаются так: берем АВА
где А-хорошая посл-ть длины k
В - произвольная длины 2n-k
и суммируем по всем длинам А от 1 до [n/2]
причем с(1)=2

tanuhka3

Меня с матом выгоняют из-за компа..
sorry

Runa

Но тогда среди отнятых вида ABA будут попадаться и хорошие же? Не так ли?

Diamond7

Это я слегка ошибся, такая формула будет неверна, начиная с n=6.

Runa

Т.е. полученное выражение заведомо >= ответа

Diamond7

Если исходить из предположения Alessandro, то рекурентная формула будет такой:
2^n - 2*2^(n-2) - 2*2^(n-4) - 6*2^(n-6)-... -(2^k-2)*2^(n-2k)-
.. -(2^[n/2]-2)*2^(n-2*[n/2])

Runa

Поясни немного, пожалуйста, как получилось это соотношение, тогда легче будет понять верно оно или нет.

Diamond7

Нет, это тоже гонская формула...

Runa

Что, неужели нельзя ничего придумать?

Timoha

есть сомнения...

Li-haya

All: это меня слегка проглючило - у Russoul-а абсолютно правильная формула.

Runa

Вот эта формула верна?!
2^n - c(1)*2^(n-2) - c(2)*2^(n-4) - c(3)*2^(n-6)-...
.. -c([n/2])*(2 или 1 в зависимости от четности n)

Runa

По-моему, то что отнимается от 2^n не есть кол-во "плохих" наборов.

Diamond7

Это именно оно.

Runa

По-моему, в формуле в отнятых слагаемых некоторые "плохие" наборы посчитаны несколько раз. Так как для "плохого" набора искомое свойство может выполнятся не только для какого-то одного k, но и для многих, главное, что не для всех.
А что такое с(i)*2^(n-2i)?- это кол-во наборов, для которых верно свойство для k=i, а на остальных n-2i местах стоят любые элементы. Поэтому от 2^n отнимятся в итоге и все "плохие" наборы, причём не один раз, и все "хорошие", тоже не один раз.
Поэтому данное выражение вообще будет отризательным для n, которые нужно взять побольше, чем 4.

c(1)*2^(n-2) + c(2)*2^(n-4)+ c(3)*2^(n-6)+...>>2*2^(n-2) +2^(n-4) + 2^(n-6)+...>2^(n-1 а ведь это очень грубая оценка, где c(i) я взял =1.
Поэтому в итоге получаем отрицательное число.

Diamond7

>>А что такое с(i)*2^(n-2i)?- это кол-во наборов, для которых верно свойство для k=i, а на остальных n-2i местах стоят любые элементы.
Важная поправка - верно для k=i, но не верно для меньших k.
c(1)*2^(n-2) + c(2)*2^(n-4)+ c(3)*2^(n-6)+...<=2*2^(n-2) +2*2^(n-4) + 4*2^(n-6)+...+ 2^(k-1)*2^(n-2k)+... = 2^(n-1)+2^(n-3)+2^(n-4)...+2^(n-k-1)+...<2^n , по-моему.

Sync755

Вроде вышел на хорошую идею, но еще не проработал до конца.
1) S(k, n) - количество n-ок: префикс длины k не совпадает с постфиксом
S(k+1, n+1) = 2*S(k, n) + (2^n - S(k, n
// если не совпадает k, то можно присобачить и 0, и 1,
если совпадают k - то в конец годится только не (k+1) символ из n-ки.
S(k+1, n+1) = 2^n + S(n, k) =>
S(k, n) = 2^(n-1) + ... + 2^( n-(k-1) ) + S (1, n-(k-1 =
2^(n-(k-1 (2^(k-2) + ... + 1) + 2 * 2^( n-(k-1) -2) = 2^n - (2^(n-k+1) - 2^(n-k) = 2^n - 2^(n-k)
C(k, n) - кол-во наборов, для которых префикс k совпадает с постфиксом
С(k, n) = 2^(n-k).
Можно было бы просуммировать эту фигню от 1 до (k-1) чтобы получить кол-во наборов, для которых совпадение k, но ведь множества этих наборов пересекается, т.е. наборы будут учитываться не один раз.
Непересекающиеся множества: A(k, n) - префикс длины k - cовпадает, совпадений 1..(k-1 (k+1 ..., n нет!
Если получится прилично выписать A(k, n просуммировать его, и отнять все это от 2^n, получим требуемое.
+бонус (похоже верно...) : если есть совпадение k,
совпадение i=1..k-1 в наборе n будут <=> cовпадение i присутствует в самом префиксе длины k.
На данный момент иссяк.
Даня

Runa

То, что С(k, n) = 2^(n-k по-моему понятно без всяких выкладок.
IMHO, числа A(n,k) не покроют всё множество, так как, например, набор 10101010...101010, если я правильно понял, не посчитается ни в одном A(n,k).
Всё равно спасибо.

Sync755

Мда... Идея, конечно хорошая, славная (моя все-таки, родная :- только до этой задачи действительно не дозрела..
Даня
P.S. красивая задача, напоминает теорему Ферма: простенькое условие, а поди - реши!

tanuhka3

)Если плохая посл-ть представляется в виде
АВА причем А - хорошая посл-ть то это представление единственно именно потому что А хорошая
2)Если у последовательности совпадают несколько суффиксов и преффиксов (АВА и СРС ) то меньший из преффиксов является плохим.
Поэтому суммирование идет по хорошим А
3)А если посл-ть представляется в виде АВА то она автоматически плохая.

tanuhka3

Кстати верны такие соотношения:
с(2n+1)=2*c(2n)
c(2n)=2*c(2n-1)-c(n)
Но опять же это ничего не дает для вывода явной формулы. Эти соотношения следуют из формулы для
с(n)
Последовательность такая: 2,2,4,6,12,20,40,76,152,...
Dixi

Runa

Самое интересное, что таких задачек, подобных этой, можно придумать очень много и они естественно возникают в дискретной математике, и их тоже непонятно как решать

tanuhka3

Если бы за это еще и деньги платили..
Оставить комментарий
Имя или ник:
Комментарий: