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 and be positive integers. Let and be non-empty, finite, and disjoint sets of integers such that for each , then or (can be both). Show that .
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. 🙂
Consider all integers in , let us consider them as vertices of a directional graph. The edges are set by the following rule: for , there is an edge from to if and only if or . Since and are disjoint, then we must that for each , then it is either or .
We claim that the in-degree of is at most . Assume that there exists as elements of such that there is an edge from to and also an edge from to . But we know that or . If , then it must be the case that and . This shows that , so the in-degree of is at most .
We know that the out-degree of is at least , clearly stated in the problem.
Let us denote as the in-degree of and as the out-degree of . But, then, we arrive at the conclusion that
so in each inequality, the equality must occur.
So, we know that each vertex must have in-degree and out-degree . This implies that our graph is a collection of disjoint cycles. So let be the cycles of our graph. Consider one cycle only.
Let be the vertices of this cycle (so, the length of cycle is . We begin with, say . We know that from to we must increase the value of by if or decrease it by if . Let be the number of elements of in this cycle and also let be the number of elements of in this cycle. Note that is the number of steps we have to take to go back to . In these steps, we know that we have to increase the value of by $a$, in steps, and decrease it by , in steps, then it will go back to . This implies that so we conclude that .
It’s now clearly that in each cycle, the ratio number of elements of elements of and in the cycle is . In conclusion, we can say that the ratio of number of elements of and the number of elements of is , or formally .
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. 😛