Olympiad problems

1977 IMO Longlists, 14

There are $2^n$ words of length $n$ over the alphabet $\{0, 1\}$. Prove that the following algorithm generates the sequence $w_0, w_1, \ldots, w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit. (1) $w_0 = 00 \ldots 0$ ($n$ zeros). (2) Suppose $w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j = 1 + e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1 - a_j$. The obtained word is $w_m$.

1966 IMO Longlists, 45

Tags: extremal combinatorics , combinatorics of words , maximization , combinatorics

An alphabet consists of $n$ letters. What is the maximal length of a word if we know that any two consecutive letters $a,b$ of the word are different and that the word cannot be reduced to a word of the kind $abab$ with $a\neq b$ by removing letters.

1966 IMO Shortlist, 45

Tags: extremal combinatorics , combinatorics of words , maximization , combinatorics

An alphabet consists of $n$ letters. What is the maximal length of a word if we know that any two consecutive letters $a,b$ of the word are different and that the word cannot be reduced to a word of the kind $abab$ with $a\neq b$ by removing letters.

1974 IMO Longlists, 42

Tags: combinatorics of words , combinatorics

In a certain language words are formed using an alphabet of three letters. Some words of two or more letters are not allowed, and any two such distinct words are of different lengths. Prove that one can form a word of arbitrary length that does not contain any non-allowed word.

2018 Silk Road, 3

Tags: combinatorics of words , combinatorics

Given the natural $n$. We shall call [i]word [/i] sequence from $n$ letters of the alphabet, and [i]distance [/i] $\rho(A, B)$ between [i]words [/i] $A=a_1a_2\dots a_n$ and $B=b_1b_2\dots b_n$ , the number of digits in which they differ (that is, the number of such $i$, for which $a_i\ne b_i$). We will say that the [i]word [/i] $C$ [i]lies [/i] between words $A$ and $B$ , if $\rho (A,B)=\rho(A,C)+\rho(C,B)$. What is the largest number of [i]words [/i] you can choose so that among any three, there is a [i]word lying[/i] between the other two?

1992 IMO Longlists, 18

Tags: fibonacci , fibonacci sequence , combinatorics of words , sequence , combinatorics

Fibonacci numbers are defined as follows: $F_0 = F_1 = 1, F_{n+2} = F_{n+1}+F_n, n \geq 0$. Let $a_n$ be the number of words that consist of $n$ letters $0$ or $1$ and contain no two letters $1$ at distance two from each other. Express $a_n$ in terms of Fibonacci numbers.

2007 Korea Junior Math Olympiad, 3

Tags: counting , permutation , combinatorics of words , combinatorics

Consider the string of length $6$ composed of three characters $a, b, c$. For each string, if two $a$s are next to each other, or two $b$s are next to each other, then replace $aa$ by $b$, and replace $bb$ by $a$. Also, if $a$ and $b$ are next to each other, or two $c$s are next to each other, remove all two of them (i.e. delete $ab, ba, cc$). Determine the number of strings that can be reduced to $c$, the string of length $1$, by the reducing processes mentioned above.

1977 IMO Shortlist, 5

Tags: graph theory , combinatorics of words , algorithm , combinatorics

There are $2^n$ words of length $n$ over the alphabet $\{0, 1\}$. Prove that the following algorithm generates the sequence $w_0, w_1, \ldots, w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit. (1) $w_0 = 00 \ldots 0$ ($n$ zeros). (2) Suppose $w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j = 1 + e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1 - a_j$. The obtained word is $w_m$.

2012 Ukraine Team Selection Test, 5

Tags: combinatorics of words , combinatorics

There are only two letters in the Mumu tribe alphabet: M and $U$. The word in the Mumu language is any sequence of letters $M$ and $U$, in which next to each letter $M$ there is a letter $U$ (for example, $UUU$ and $UMMUM$ are words and $MMU$ is not). Let $f(m,u)$ denote the number of words in the Mumu language which have $m$ times the letter $M$ and $u$ times the letter $U$. Prove that $f (m, u) - f (2u - m + 1, u) = f (m, u - 1) - f (2u - m + 1, u - 1)$ for any $u \ge 2,3 \le m \le 2u$.

2011 IMO Shortlist, 6

Tags: combinatorics of words , combinatorics

Let $n$ be a positive integer, and let $W = \ldots x_{-1}x_0x_1x_2 \ldots$ be an infinite periodic word, consisting of just letters $a$ and/or $b$. Suppose that the minimal period $N$ of $W$ is greater than $2^n$. A finite nonempty word $U$ is said to [i]appear[/i] 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 [i]ubiquitous[/i] if the four words $Ua$, $Ub$, $aU$, and $bU$ all appear in $W$. Prove that there are at least $n$ ubiquitous finite nonempty words. [i]Proposed by Grigory Chelnokov, Russia[/i]

1974 IMO Shortlist, 12

Tags: combinatorics , combinatorics of words

In a certain language words are formed using an alphabet of three letters. Some words of two or more letters are not allowed, and any two such distinct words are of different lengths. Prove that one can form a word of arbitrary length that does not contain any non-allowed word.

2021 Brazil Undergrad MO, Problem 6

Tags: combinatorics of words , combinatorics

We recursively define a set of [i]goody pairs[/i] of words on the alphabet $\{a,b\}$ as follows: - $(a,b)$ is a goody pair; - $(\alpha, \beta) \not= (a,b)$ is a goody pair if and only if there is a goody pair $(u,v)$ such that $(\alpha, \beta) = (uv,v)$ or $(\alpha, \beta) = (u,uv)$ Show that if $(\alpha, \beta)$ is a good pair then there exists a palindrome $\gamma$ (possibly empty) such that $\alpha\beta = a \gamma b$

2014 IFYM, Sozopol, 3

Tags: combinatorics , combinatorics of words

Let each sequence of capital Bulgarian letters be a word (Note that the Bulgarian alphabet consists of 30 letters). We say that a word is [i]calm[/i], if there is no sequence of the letter $P$ in it (two letters $P$ next to each other). Find a clear expression for $f(n)$ (closed formula), which represents the number of calm words with length $n$. Example: [i]РНТ[/i] and [i]ТТРВ[/i] are calm, but [i]ЖГРР[/i] and [i]ЖРРРП[/i] aren’t.

2024 IMC, 4

Tags: abstract algebra , group theory , sequence , combinatorics of words , subgroup

Let $g$ and $h$ be two distinct elements of a group $G$, and let $n$ be a positive integer. Consider a sequence $w=(w_1,w_2,\dots)$ which is not eventually periodic and where each $w_i$ is either $g$ or $h$. Denote by $H$ the subgroup of $G$ generated by all elements of the form $w_kw_{k+1}\dotsc w_{k+n-1}$ with $k \ge 1$. Prove that $H$ does not depend on the choice of the sequence $w$ (but may depend on $n$).

2017 Brazil Undergrad MO, 6

Tags: combinatorics , combinatorics of words

Let's consider words over the alphabet $\{a,b\}$ to be sequences of $a$ and $b$ with finite length. We say $u \leq v$ if $u$ is a subword of $v$ if we can get $u$ erasing some letter of $v$ (for example $aba \leq abbab$). We say that $u$ differentiates the words $x$ and $y$ if $u \leq x$ but $u \not\leq y$ or vice versa. Let $m$ and $l$ be positive integers. We say that two words are $m-$equivalents if there does not exist some $u$ with length smaller than $m$ that differentiates $x$ and $y$. a) Show that, if $2m \leq l$, there exists two distinct words with length $l$ \ $m-$equivalents. b) Show that, if $2m > l$, any two distinct words with length $l$ aren't $m-$equivalent.

1987 IMO Longlists, 19

Tags: combinatorics , recurrence relation , symmetry , counting , combinatorics of words , digit

How many words with $n$ digits can be formed from the alphabet $\{0, 1, 2, 3, 4\}$, if neighboring digits must differ by exactly one? [i]Proposed by Germany, FR.[/i]

1987 IMO Shortlist, 14

Tags: combinatorics , symmetry , combinatorics of words , counting , digit , recurrence relation

How many words with $n$ digits can be formed from the alphabet $\{0, 1, 2, 3, 4\}$, if neighboring digits must differ by exactly one? [i]Proposed by Germany, FR.[/i]