Periodic words: why longest high-multiplicity factors are two-sided branching

tiny_tonk·Jun 28, 2025(edited)

I can find a factor with both right extensions, but the problem requires both left extensions too, and it wants n different factors. What choice of extremal factor gives both properties at once? Problem: Let

n

be a positive integer and let

W = \ldots x_{-1} x_{0} x_{1} x_{2} \ldots

be an infinite periodic word consisting of the letters

a

and

b

. Suppose that the minimal period

N

W

is greater than

2^{n}

. A finite nonempty word

U

is said to appear in

W

if there exist indices

k \leq \ell

such that

U = x_{k} x_{k+1} \ldots x_{\ell}

. A finite word

U

is called ubiquitous if the four words

U a

U b

a U

, and

b U

all appear in

W

. Prove that there are at least

n

ubiquitous finite nonempty words. Source: IMO 2011 Shortlist · MNET-06RG

Open MNET-06RG in the question bank →

5 replies

thecakewaslag·Jun 28, 2025(edited)

Count occurrences modulo the minimal period N. For every word U,

\mu(U)=\mu(Ua)+\mu(Ub)=\mu(aU)+\mu(bU)

. Minimality implies that every factor of length N occurs at most once per period.

tiny_tonk·Jun 30, 2025(edited)

So for a fixed threshold

2^k

, there is a longest factor U with multiplicity above it. Existence comes from one letter having multiplicity >N/2.

thecakewaslag·Jun 30, 2025(edited)

For k=0,…,n−1 that works. Each one-letter extension has multiplicity ≤

2^k

by maximality. Since their sum is >

2^k

, neither can vanish, on either side.

shieldonbreak·Jun 30, 2025(edited)

Also

\mu(U)\le2^{k+1}

; otherwise one right extension would still exceed the threshold. Thus the chosen multiplicities lie in the disjoint intervals

(2^k,2^{k+1}]

, proving the factors are distinct.

tiny_tonk·Jun 30, 2025

That interval argument is much cleaner than trying to show their lengths are different. It also explains why minimal period, rather than any period, is needed.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…