MathDB

Problem 6

Part of 2021 Brazil Undergrad MO

Problems(1)

Pairs whose concatenation form and almost-palindrome

Source: Brazilian Undergrad MO Problem 6

5/12/2022
We recursively define a set of goody pairs of words on the alphabet {a,b}\{a,b\} as follows:
- (a,b)(a,b) is a goody pair; - (α,β)≠(a,b)(\alpha, \beta) \not= (a,b) is a goody pair if and only if there is a goody pair (u,v)(u,v) such that (α,β)=(uv,v)(\alpha, \beta) = (uv,v) or (α,β)=(u,uv)(\alpha, \beta) = (u,uv)
Show that if (α,β)(\alpha, \beta) is a good pair then there exists a palindrome γ\gamma (possibly empty) such that αβ=aγb\alpha\beta = a \gamma b
combinatoricsCombinatorics of wordscollege contestsBrazilian Undergrad MO 2021