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. 😛

 

 

Advertisements