Page 1 of 1

### APMO 2013 Problem 4

Posted: Thu May 09, 2013 11:15 am
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$.)

### Re: APMO 2013 Problem 4

Posted: Sun May 19, 2013 11:53 pm
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.

### Re: APMO 2013 Problem 4

Posted: Mon May 20, 2013 12:30 pm
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!