1
$\begingroup$

Let $\Sigma$ be an alphabet of size $|\Sigma|=k$. Let $w\in\Sigma^*$ be a word over $\Sigma$. If $|w| > 2^k$, then $w$ contains an infix $y$ with $|y|\ge 2$, such that every letter occurring in y occurs an even number of times in $y$.

Seems it's obvious but I can't prove it.

$\endgroup$
0

2 Answers 2

4
$\begingroup$

By the pigeonhole principle, there must be two different prefixes of $w$ that contain the same number of each letter modulo 2. Their difference is your $y$.

$\endgroup$
1
  • $\begingroup$ Oh yes thanks :) $\endgroup$
    – Saeed
    Mar 1, 2012 at 21:07
2
$\begingroup$

Maybe this should be a comment to Henning's answer, but I think there is still a crucial point of the reasoning to be explained, namely...

For each prefix of x associate a k-tuple over {0,1} that represents the parity of each of the k letters in that prefix. Obviously, there are only $2^k$ such binary k-tuples possible, so if there are $2^k+1$ letters in x, one of the k-tuples must repeat at two different prefixes -- there's the pigeonhole principle. The points at which they repeat give Henning's two prefixes in which the parity of each letter is the same.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .