C7

Part of 2017 IMO Shortlist

Problems(1)

Operation on smallest positive integers not in a set

Source: IMO Shortlist 2017 C7

For any finite sets

X

Y

of positive integers, denote by

f_X(k)

k^{\text{th}}

smallest positive integer not in

X

X*Y=X\cup \{ f_X(y):y\in Y\}.

A

a>0

positive integers and let

B

b>0

positive integers. Prove that if

A*B=B*A

\underbrace{A*(A*\cdots (A*(A*A))\cdots )}_{\text{ A appears $b$ times}}=\underbrace{B*(B*\cdots (B*(B*B))\cdots )}_{\text{ B appears $a$ times}}.

Proposed by Alex Zhai, United States

IMO Shortlistcombinatorics