## One of My Favorite Problems

Here is one of my favorite problems. This problem was part of problem set for IMC Simulation last year, prepared by Kak Ajat. So, here it is.

Problem 3. Let $a$ and $b$ be positive integers. Let $A$ and $B$ be non-empty, finite, and disjoint sets of integers such that for each $i \in A \cup B$, then $i+a \in A$ or $i-b \in B$ (can be both). Show that $a |A| = b|B|$.

In the test, I was done with problem one and problem two. I skipped this problem because this problem looked boring, and problem 4 looked so “attackable”. I felt so confident doing functional equation problems. But that one problem was quite annoying; I knew that my solution was very close, but hell yeah, I failed.

So, let us go back to the problem written above. If I’m not mistaken, this problem is taken from American Mathematical Monthly (cmiiw). In the test, it took almost an hour for me  to find a perfect solution for this problem. This is my solution to the problem. 🙂

Solution.

Consider all integers in $A \cup B$, let us consider them as vertices of a directional graph. The edges are set by the following rule: for $x,y \in A \cup B$, there is an edge from $x$ to $y$ if and only if $x+a=y$ or $x-b = y$. Since $A$ and $B$ are disjoint, then we must that for each $x \in A \cup B$, then it is either $x \in A$ or $x \in B$.

Let $i \in A \cup B$.

We claim that the in-degree of $i$ is at most $1$. Assume that there exists $x \ne y$ as elements of $A \cup B$ such that there is an edge from $x$ to $i$ and also an edge from $y$ to $i$. But we know that $i \in A$ or $i \in B$. If $i \in A$, then it must be the case that $x+a=i$ and $y+a=i$. This shows that $x=y$, so the in-degree of $i$ is at most $1$.

We know that the out-degree of $i$ is at least $1$, clearly stated in the problem.

Let us denote $\delta_{-}(i)$ as the in-degree of $i$ and $\delta_{+}(i)$ as the out-degree of $i$. But, then, we arrive at the conclusion that

$\displaystyle |A \cup B| \le \sum_{i \in A \cup B} \delta_{+}(i) = \sum_{i \in A \cup B} \delta_{-}(i) \le |A \cup B|$,

so in each inequality, the equality must occur.

So, we know that each vertex must have in-degree $1$ and out-degree $1$. This implies that our graph is a collection of disjoint cycles. So let $C_1,C_2,\dots,C_k$ be the cycles of our graph. Consider one cycle only.

Let $c_1 \to c_2 \to \dots \to c_j \to c_1$ be the vertices of this cycle (so, the length of cycle is $j$. We begin with, say $c_1$. We know that from $c_i$ to $c_{i+1}$ we must increase the value of $c_i$ by $a$ if $c_{i+1} \in A$ or decrease it by $b$ if $c_{i+1} \in B$. Let $m$ be the number of elements of $A$ in this cycle and also let $n$ be the number of elements of $B$ in this cycle. Note that $m+n=j$ is the number of steps we have to take to go back to $c_1$. In these steps, we know that we have to increase the value of $c_1$ by $a$, in $m$ steps, and decrease it by $b$, in $n$ steps, then it will go back to $c_1$. This implies that $c_1 + m a - n b = c_1$ so we conclude that $ma = nb$.

It’s now clearly that in each cycle, the ratio number of elements of elements of $A$ and $B$ in the cycle is $b:a$. In conclusion, we can say that the ratio of number of elements of $A$ and the number of elements of $B$ is $b:a$, or formally $a|A| = b|B|$.

$\blacksquare$

How was that? It’s a pretty neat problem, isn’t it? But, the bad news was Kak Ajat lost our exam papers!  It’s a break already, but I still don’t know whether I’m going to go back home (to Pekanbaru) or not yet. Now, I think I have to go to some place where I can buy joystick and stuffs. I’m so into posting stuffs right now. Watch out. 😛

This entry was posted in Uncategorized. Bookmark the permalink.

### 3 Responses to One of My Favorite Problems

1. johan says:

keren gan! 😀

2. I even lost the problem sets T_T , sorry…
This was taken from Math Magazine, author of the problem is Constantin Gonciuela, Trainan College.
Solution (By Bjorn Poonen):
Let $S_A=\{n-a | n \in \mathbb{N}\}$ and $S_B=\{n+b | \mathbb{N}\}$ and $S=S_A \cup S_B$ then $A \cup B \subseteq S$, but $|S|\leq |A \cup B|$ so we have $S=A \cup B$, and $S_A \cap S_B =\emptyset$. Also $\sum_{x \in S} x = -a|A|+b|B|+\sum_{x\in A\cup B} x$, the conclusion follows.

3. I even lost the problem sets T_T , sorry…
This was taken from Math Magazine, author of the problem is Constantin Gonciuela, Trainan College.
Solution (By Bjorn Poonen):
Let $S_A=\{n-a | n \in \mathbb{N}\}$ and $S_B=\{n+b | \mathbb{N}\}$ and $S=S_A \cup S_B$ then $A \cup B \subseteq S$, but $S|\leq |A \cup B|$ so we have $S=A \cup B$, and $S_A \cap S_B =\emptyset$. Also $\sum_{x \in S} x = -a|A|+b|B|+\sum_{x\in A\cup B} x$, the conclusion follows.