Maths Olympiad Prep

Library / China Girls' Mathematical Olympiad /41 of 51

China Girls' Mathematical Olympiad

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 2n−1>an2^{n-1} > a^n. We define An={m∣m is a multiple of 2n−1}A_n = \{m \mid m \text{ is a multiple of } 2^{n-1}\} and
Ai={2i−1m∣m is an odd integer}, A_i = \{2^{i-1}m \mid m \text{ is an odd integer}\},
for 1≤i≤n−11 \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 a≥2a \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 1≤i≤n1 \le i \le n, let Bi=Ai∩NB_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>bm−b1=(bm−bm−1)+(bm−1−bm−2)+⋯+(b2−b1)≥(m−1)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 m−1<2n−im-1 < 2^{n-i}, or m≤2n−im \le 2^{n-i}. Since A1,A2,…,AnA_1, A_2, \dots, A_n is a partition, Bi∩Bj=∅B_i \cap B_j = \emptyset for 1≤i<j≤n1 \le i < j \le n and N=B1∪B2∪⋯∪BnN = B_1 \cup B_2 \cup \dots \cup B_n. It follows that
2n=∣N∣=∣B1∣+∣B2∣+⋯+∣Bn∣≤∑i=1n2n−i=2n−1, 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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