MathDB

IMC 1999 Problem 11

Source: IMC 1999 Day 2 Problem 5

October 27, 2020

combinatorics

Problem Statement

Let

S

be the set of words made from the letters

a,b

and

c

. The equivalence relation

\sim

on

S

satisfies

uu \sim u

u \sim v \Rightarrow uw \sim vw \; \text{and} \; wu \sim wv

for all words

u, v

and

w

. Prove that every word in

S

is equivalent to a word of length

\leq 8

.

Back to Problems View on AoPS