IMC 2003, Day 1, Problem 4
Determine the set of all pairs of positive integers for which the set of positive integers can be decomposed into two sets and such that .
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution. Clearly and must be different since and are disjoint.
Let be a solution and consider the sets such that . Denoting the greatest common divisor of and , we have , , and . Thus is a solution and it is enough to determine the solutions with .
If then , thus must be a divisor of . Similarly, if , then is a divisor of . Therefore, in all solutions, one of numbers is a divisor of the other one.
Now we prove that if , then is a solution. For each positive integer , let be the largest non-negative integer for which . Then let and . This is a decomposition of all positive integers such that .
Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.