Maths Olympiad Prep

Library / /44 of 53

Combinatorics Difficulty 7.0 National olympiad Prove it China

Determine all positive real numbers aa such that there exists a positive integer nn and sets A1,A2,,AnA_1, A_2, \dots, A_n satisfying the following conditions:
(1) every set AiA_i has infinitely many elements;
(2) every pair of distinct sets AiA_i and AjA_j do not share any common element;
(3) the union of sets A1,A2,,AnA_1, A_2, \dots, A_n is the set of all integers;
(4) for every set AiA_i, the positive difference of any pair of elements in AiA_i is at least aia^i. (posed by Yuan Hanhui)

Solution

The answer of the problem is the set of all positive real numbers less than 22. We consider two cases.

Case I We assume that 0<a<20 < a < 2. Then there is a positive nn such that 2n1>an2^{n-1} > a^n. We define An={mm is a multiple of 2n1}A_n = \{m \mid m \text{ is a multiple of } 2^{n-1}\} and
Ai={2i1mm is an odd integer}, A_i = \{2^{i-1}m \mid m \text{ is an odd integer}\},
for 1in11 \le i \le n-1. Then A1,A2,,AnA_1, A_2, \dots, A_n is a partition of the set of positive integers satisfying the conditions of the problem.

Case II We assume that a2a \ge 2. We claim that no such partition exists. To prove by contradiction, we assume on the contrary that A1,A2,,AnA_1, A_2, \dots, A_n is a partition satisfying the conditions of the problem. Let N={1,2,,2n}N = \{1, 2, \dots, 2^n\}. For every ii with 1in1 \le i \le n, let Bi=AiNB_i = A_i \cap N. We assume that Bi={b1,b2,,bm}B_i = \{b_1, b_2, \dots, b_m\} with b1<b2<<bmb_1 < b_2 < \dots < b_m. We have
2n>bmb1=(bmbm1)+(bm1bm2)++(b2b1)(m1)2i, 2^n > b_m - b_1 = (b_m - b_{m-1}) + (b_{m-1} - b_{m-2}) + \dots + (b_2 - b_1) \ge (m-1)2^i,
implying that m1<2nim-1 < 2^{n-i}, or m2nim \le 2^{n-i}. Since A1,A2,,AnA_1, A_2, \dots, A_n is a partition, BiBj=B_i \cap B_j = \emptyset for 1i<jn1 \le i < j \le n and N=B1B2BnN = B_1 \cup B_2 \cup \dots \cup B_n. It follows that
2n=N=B1+B2++Bni=1n2ni=2n1, 2^n = |N| = |B_1| + |B_2| + \dots + |B_n| \le \sum_{i=1}^{n} 2^{n-i} = 2^n - 1,
which is impossible. Hence our assumption was wrong and such a partition does not exist for every positive integer nn.

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 and solution reproduced as published; topic and difficulty added by this site.