Maths Olympiad Prep

Track / Stage 8 / 27 of 180 #1727 of 1964

Problem 1727

IMO Shortlist mid-range; USAMO P2/P5
Geometry Difficulty 8.1 Prove it

5. Prove that neither the closed nor the open interval can be decomposed into finitely many mutually disjoint proper subsets which are all congruent by translation. (St. 2)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Assume the opposite: Suppose that the interval I I can be decomposed into finitely many mutually disjoint proper subsets which are all congruent by translation. That is, I=i=1mAi I = \bigcup_{i=1}^m A_i , where AiAj= A_i \cap A_j = \varnothing for ij i \neq j and Ai=A1+ti A_i = A_1 + t_i for i>1 i > 1 . Since the subsets are proper, m>1 m > 1 . Without loss of generality (WLOG), assume that the left endpoint of I I is 0 0 and 1=t2<t3<<tm 1 = t_2 < t_3 < \dots < t_m .

2. Closed Interval Case: Let I I be a closed interval. For any nN n \in \mathbb{N} , denote Pn={iAi[0,n)} P_n = \{i \mid A_i \cap [0, n) \neq \varnothing\} . For example, P1={1} P_1 = \{1\} because A1 A_1 is the "leftmost" of all sets and 0 0 may belong only to it, like any other point before the closest "translation", which is t2=1 t_2 = 1 belonging to A2 A_2 . It is also clear that [1,2)A2 [1, 2) \subseteq A_2 as a translation of [0,1)A1 [0, 1) \subseteq A_1 . Thus, P2={1,2} P_2 = \{1, 2\} .

3. Induction Hypothesis: We prove by induction the following statements simultaneously:
- (1) For any nN n \in \mathbb{N} , [0,n)I [0, n) \subseteq I .
- (2) Given any i=1,2,,n i = 1, 2, \dots, n , all points in [i1,i) [i-1, i) belong to the same set.
- (3) If iPn i \in P_n for i>1 i > 1 , then tiN t_i \in \mathbb{N} .

4. Base Case: The induction base and the case n=2 n = 2 have already been proven.

5. Induction Step: Let the statements be true for some n2 n \geq 2 . Since I I is a closed set, (1) implies nI n \in I . Let nAj n \in A_j and consider three possible cases:
- Case 1: jPn j \notin P_n . Then tj=n t_j = n and [n,n+1)Aj [n, n+1) \subseteq A_j as a translation of [0,1)A1 [0, 1) \subseteq A_1 .
- Case 2: jPn j \in P_n and j>1 j > 1 . Then tjN t_j \in \mathbb{N} , as follows from (3) and, like in the previous case, [n,n+1)Aj [n, n+1) \subseteq A_j as a translation of [ntj,n+1tj)A1 [n-t_j, n+1-t_j) \subseteq A_1 .
- Case 3: j=1 j = 1 . Then n+1A2 n+1 \in A_2 . To prove that [n,n+1)A1 [n, n+1) \subset A_1 , take any point x x from (n,n+1) (n, n+1) and let xAk x \in A_k . The case kPn k \notin P_n is impossible because Ak A_k would contain some interval of length 1 1 (namely [tk,tk+1) [t_k, t_k+1) ) embracing n+1 n+1 along with x x . The case kPn,k1 k \in P_n, k \ne 1 is also impossible because in this case the whole [n,n+1) [n, n+1) would belong to Ak A_k (see Case 2), which contradicts nA1 n \in A_1 . Thus, k=1 k = 1 .

6. Conclusion for Closed Interval: We've just proved the three statements. From the first statement, it follows that I=[0,+) I = [0, +\infty) , which is a contradiction.

7. Open Interval Case: Let I I be an open interval. For any nN n \in \mathbb{N} , denote Pn={iAi(0,n]} P_n = \{i \mid A_i \cap (0, n] \neq \varnothing\} . Note that no point x(0,1] x \in (0, 1] may belong to Ai A_i other than A1 A_1 because in that case y=xti y = x - t_i must belong to A1I A_1 \subseteq I , but y0 y \leq 0 so yI y \notin I . On the other hand, at least some right neighborhood (0,ε)I (0, \varepsilon) \subseteq I , so there is a point x(0,1) x \in (0, 1) belonging to A1 A_1 . This implies x+1A2    (0,1]I    (0,1]A1 x + 1 \in A_2 \implies (0, 1] \subset I \implies (0, 1] \subseteq A_1 . Thus, P1={1} P_1 = \{1\} . It is also clear that (1,2]=(0+t1,1+t1]A2 (1, 2] = (0 + t_1, 1 + t_1] \subseteq A_2 and P2={1,2} P_2 = \{1, 2\} .

8. Induction Hypothesis for Open Interval: We prove by induction the following statements simultaneously:
- (1) For any nN n \in \mathbb{N} , (0,n]I (0, n] \subseteq I .
- (2) Given any i=1,2,,n i = 1, 2, \dots, n , all points in (i1,i] (i-1, i] belong to the same set.
- (3) If iPn i \in P_n for i>1 i > 1 , then tiN t_i \in \mathbb{N} .

9. Base Case for Open Interval: The induction base and the case n=2 n = 2 have already been proven.

10. Induction Step for Open Interval: Let the statements be true for some n2 n \geq 2 . Since I I is an open set, (1) implies that at least some right neighborhood (n,n+ε)I (n, n + \varepsilon) \subseteq I . Consider three possible cases:
- Case 1: There is x(n,n+1] x \in (n, n+1] belonging to some Aj A_j such that jPn j \in P_n and j>1 j > 1 . Then xtjA1 x - t_j \in A_1 . (3) says that tjN t_j \in \mathbb{N} , while (2) implies (ntj,n+1tj]A1 (n - t_j, n + 1 - t_j] \subseteq A_1 , thus (n,n+1]Aj (n, n + 1] \subseteq A_j .
- Case 2: There is ε>0 \varepsilon > 0 such that (n,n+ε)A1 (n, n + \varepsilon) \subset A_1 . Then (n+1,n+1+ε)A2 (n + 1, n + 1 + \varepsilon) \subset A_2 . It entails two things: (a) (n,n+1]I (n, n + 1] \subset I ; (b) none of x(n,n+1] x \in (n, n + 1] belong to Aj A_j with jPn j \notin P_n because the latter would mean n+εtj<xn+1 n + \varepsilon \leq t_j < x \leq n + 1 and Aj A_j contained some interval of length 1 1 (namely (tj,tj+1] (t_j, t_j + 1] ) embracing (n+1,n+1+ε) (n + 1, n + 1 + \varepsilon) along with x x . From (a) and (b) it follows that (n,n+1]A1 (n, n + 1] \subset A_1 .
- Case 3: For any ε>0 \varepsilon > 0 , there is x(n,n+ε) x \in (n, n + \varepsilon) such that xA1 x \notin A_1 . It means that there is jPn j \notin P_n such that for any ε>0 \varepsilon > 0 , (n,n+ε)Aj (n, n + \varepsilon) \cap A_j \neq \varnothing . But then tj=n t_j = n and (n,n+1]Aj (n, n + 1] \subseteq A_j .

11. Conclusion for Open Interval: We've just proved the three statements. From the first statement, it follows that I=(0,+) I = (0, +\infty) , which is a contradiction.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.