MathDB

Operation on smallest positive integers not in a set

Source: IMO Shortlist 2017 C7

July 10, 2018

IMO Shortlistcombinatorics

Problem Statement

For any finite sets

X

and

Y

of positive integers, denote by

f_X(k)

the

k^{\text{th}}

smallest positive integer not in

X

, and let

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

Let

A

be a set of

a>0

positive integers and let

B

be a set of

b>0

positive integers. Prove that if

A*B=B*A

, then

\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

Back to Problems View on AoPS