Maths Olympiad Prep

Library / /13 of 16

Number theory Difficulty 7.4 National Olympiad, round 2 Prove it Romania

Let nn be a positive integer and M={1,2,,2n+1}M = \{1, 2, \dots, 2n + 1\}. Find out in how many ways we can split the set MM into three mutually disjoint nonempty sets A,B,CA, B, C so that both the following are true:
(i) for each aAa \in A and bBb \in B, the remainder of the division of aa by bb belongs to CC,
(ii) for each cCc \in C there exists aAa \in A and bBb \in B such that cc is the remainder of the division of aa by bb.
Mircea Fianu

Solution

We notice that a>ba > b, for all aAa \in A and bBb \in B. Indeed, the contrary would imply that a<ba < b, so the remainder of the division of aa by bb is aa and aa belongs to both BB and CC. This shows that AA is made by consecutive numbers and 2n+1A2n+1 \in A.

Take cCc \in C. From the assumption there exists aAa \in A and bBb \in B so that a=bq+ca = bq+c. Then a(c+1)1+c=2c+1a \ge (c+1) \cdot 1 + c = 2c + 1, hence 2n+12c+12n+1 \ge 2c+1, therefore ncn \ge c. If we suppose that n+1Bn+1 \notin B, then n+1An+1 \in A, whence {n+1,n+2,,2n+1}A\{n+1, n+2, \dots, 2n+1\} \subset A. So, if bBb \in B, then bnb \le n and, since AA contains n+1n+1 consecutive numbers, AA must contain at least one multiple of bb – false.

Henceforth n+1Bn+1 \in B, so there exists k{n+1,n+2,,2n}k \in \{n+1, n+2, \dots, 2n\} so that A={2n+1,2n,,k+1}A = \{2n+1, 2n, \dots, k+1\}. From cnc \le n for all cCc \in C follows {n+1,n+2,,k}B\{n+1, n+2, \dots, k\} \subset B.

The remainders of the divisions of the elements of AA to the elements of {n+1,n+2,,k}\{n+1, n+2, \dots, k\} are the numbers {1,2,,n}\{1, 2, \dots, n\}. This shows that B={n+1,n+2,,k}B = \{n+1, n+2, \dots, k\} and C={1,2,,n}C = \{1, 2, \dots, n\}. The number kk can be every element of the set {n+1,n+2,,2n}\{n+1, n+2, \dots, 2n\}, so there are nn possible splits.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.