APMO 2013 Problem 4

Discussion on Asian Pacific Mathematical Olympiad (APMO)
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

APMO 2013 Problem 4

Let $a$ and $b$ be positive integers, and let $A$ and $B$ be finite sets of integers satisfying
(i) $A$ and $B$ are disjoint;
(ii) if an integer $i$ belongs to either to $A$ or to $B$, then either $i+a$ belongs to $A$ or $i-b$ belongs to $B$.
Prove that $a\left\lvert A \right\rvert = b \left\lvert B \right\rvert$. (Here $\left\lvert X \right\rvert$ denotes the number of elements in the set $X$.)
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: APMO 2013 Problem 4

Let $i\in A\cup B$. Make sense of the following diagram:
\begin{align}&\downarrow A\cup B\\ &i\\ A\swarrow&\ \searrow B\\ i+a\quad &\quad i-b\\ A\swarrow\ \searrow B&A\swarrow\ \searrow B\\ i+2a\qquad i+a&-b\qquad i-2b\\ A\swarrow\ \searrow B\ A\swarrow\ &\searrow B\ A\swarrow\ \searrow B\\ i+3a\quad i+2a-b\ \ &\ \ i+a-2b\quad i-3b\\ A\swarrow\ \searrow B\ A\swarrow\ \searrow B\ &A\swarrow\ \searrow B\ A\swarrow\ \searrow B\\ i+4a\quad i+3a-b\quad i+2a&-2b\quad i+a-3b\quad i-4b\\ \dots \qquad&\qquad\dots \end{align}
Since $A$ and $B$ are finite, we must have $i+xa-yb=i+x'a-y'b$ for some $x,y,x',y'$ with say $x+y>x'+y'$, such that there is a sequence of arrows from $i+x'a-y'b$ to $i+xa-yb$. Take the parallelogram with vertices at $i+xa-yb$, $i+x'a-y'b$ and $i$. The number at the fourth vertex must be equal to $i$. Therefore WLOG $x'=y'=0$, i.e. $xa=yb$. Then $x$ is the number of $\swarrow$ arrows, i.e. the number of elements in $A$ in the path from $i$ to $i+xa-yb=i$. Similarly $y$ is the number of elements in $B$ in this path.

If all elements in $A\cup B$ haven't been covered, take any element not in the first path. Repeat the above procedure. Eventually all elements will be covered. Then summing $xa=yb$ over all the paths gives $|A|a=|B|b$, as desired.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm

Re: APMO 2013 Problem 4

Consider these bijections of $A$ and $B$.
$A_a=\{i-a:i \in A\},B_b=\{i+b:i \in B\}$. Note that $|A|=|A_a|,|B|=|B_b|$
Now choose any $i \in A \cup B$.
Then $i+a \in A$ or $i-b \in B$.
If $i+a \in A$, then $i \in A_a$; else if $i-b \in A$, then $i \in B_b$.
So every $i \in A \cup B$ maps to either $A_a$ or $B_b$.
Hence $A \cup B \subseteq A_a \cup B_b$.
So $|A \cup B| \le |A_a \cup B_b| \le |A_a|+|B_b|[\text{PIE}]$
$=|A|+|B|$[Since $A_a,B_b$ are bijections of $A,B$ respectively].
$=|A \cup B|$[Since $A,B$ are disjoint.]
Thus $|A \cup B| \le |A_a \cup B_b| \le |A \cup B|$.
Hence $A \cup B=A_a \cup B_b$
So we have $|A \cup B|=|A_a \cup B_b| \Rightarrow |A|+|B|=|A_a|+|B_b|-|A_a \cap B_b| \Rightarrow |A_a \cap B_b|=0$.
Hence $A_a,B_b$ are disjoint.
now let us denote the sum of elements of a set $S$ as $\sum S$.
Now $\sum A+\sum B=\sum (A \cup B)=\sum (A_a \cup B_b)=\sum A_a+\sum B_b=\sum A-a|A|+\sum B+b|B|$ $\Rightarrow a|A|=b|B|$, done!
বড় ভালবাসি তোমায়,মা