2
$\begingroup$

Fix two positive integers $N$ and $M$ and assume $n:=\frac{N}{M}\in\mathbb{N}$. Consider a fixed binary sequence $Y=Y_1,\ldots,Y_M\in\{0,1\}^M$. The goal is to find an optimizing length-$N$ ($N\geq M$) binary sequence $X^*\in\{0,1\}^N$ such that the number of occurences $T$ of $Y$ in $X^*$ is maximized (compared with all other length-$N$ sequences).

The number of occurrences $T$ counts the total number of possible ways that $Y$ is contained in some binary sequence $X$. For instance, if $Y=011$ and $X=001101$, then $T=6$.

Conjecture

The maximizing sequence $X^*$ is always formed by duplicating each bit in $Y$, i.e., $X^*=\underbrace{Y_1,Y_1,\ldots,Y_1}_{n \text{ many}}, \ldots, \underbrace{Y_M,Y_M,\ldots,Y_M}_{n \text{ many}}$.

I am able to prove this conjecture by induction, but it turns out to be quite messy (including many case studies). It'd be nice if some expert in combinatorics could share intuition for a more concise proof or guide me to the right place. Thanks!

EDIT:

Sorry, the claim turns out to be wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.