Здравствуйте, DjAndy, Вы писали:

DA>M = log2(N)

DA>Конечно логично, тогда информация о местоположении последовательности будет занимать как раз M бит. Но откуда следует эта формула?

Прошу прощения. Эта формула — ответ на другой вопрос, а именно: — какова максимальная длина N последовательности, в которой любая подпоследовательность длиной М встречается ровно один раз?
И ответ: N = 2^M.

А вот на исходный вопрос:

"Существует ли такая последовательность из 0 и 1 длиной N, такая, что в ней не существует 2 равных непересекающихся подпоследовательностей длиной M? Очевидно, что при M = 1 и длине N > 2 это уже не верно, но гораздо интереснее выяснить максимально возможное M для любого N."

ответ гораздо проще: максимально возможное M для любого N — это когда M = N.

Но тем не менее, вопрос о генерации таких последовательностей может оказаться интересным. Выделим его в отдельную задачку.