Maths Olympiad Prep

Library / /37 of 397

, 2021

Combinatorics Difficulty 4.9 AIME Prove it Taiwan

Find the largest positive integer KK satisfying the following condition:

Given any finitely many closed intervals A1,A2,,ANA_1, A_2, \dots, A_N (NN being an arbitrary positive integer), each of length 1. If their union is [0,2021][0, 2021], then we can always find KK pairwise disjoint intervals among A1,,ANA_1, \dots, A_N.

Solution

最大的 KK 為 1011。

首先證明 K1011K \ge 1011。令 ϵ(0,11009)\epsilon \in (0, \frac{1}{1009}), 並考慮集合 A={0,2+ϵ,4+2ϵ,,2018+1009ϵ}\mathcal{A} = \{0, 2 + \epsilon, 4 + 2\epsilon, \dots, 2018 + 1009\epsilon\}。顯然 A\mathcal{A} 的每個點都必須存在一個 AiA_i 包含之, 且這些 AiA_i 兩兩互斥 (因為 AiA_i 的長度皆為 1), 故這邊共選到 1010 個 AiA_i。又基於 Ai=[0,2021]\cup A_i = [0, 2021], 我們必須有一個 AjA_j[2020,2021][2020, 2021], 而這與前述的 1010 個 AiA_i 都不相同 (基於 2018+1009ϵ+1<20202018 + 1009\epsilon + 1 < 2020), 故我們得到 1011 個兩兩互斥的 AiA_i

接著我們證明 K1011K \le 1011。考慮 Ai=[i1,i]A_i = [i - 1, i], i=1,2,,2021i = 1, 2, \dots, 2021。易知我們最多僅能找到 1011 個兩兩互斥的空集合 [0,1],[2,3],,[2020,2021][0, 1], [2, 3], \dots, [2020, 2021], 故 K1011K \le 1011

[The largest KK is 1011.

First we prove K1011K \ge 1011. Let ϵ(0,11009)\epsilon \in (0, \frac{1}{1009}), and consider the set A={0,2+ϵ,4+2ϵ,,2018+1009ϵ}\mathcal{A} = \{0, 2 + \epsilon, 4 + 2\epsilon, \dots, 2018 + 1009\epsilon\}. Clearly, for each point of A\mathcal{A} there must exist some AiA_i containing it, and these AiA_i are pairwise disjoint (since the AiA_i all have length 1), so here we obtain a total of 1010 such AiA_i. Also, since Ai=[0,2021]\cup A_i = [0, 2021], there must be some AjA_j equal to [2020,2021][2020, 2021], and this is different from all the aforementioned 1010 AiA_i (since 2018+1009ϵ+1<20202018 + 1009\epsilon + 1 < 2020), so we obtain 1011 pairwise disjoint AiA_i.

Next we prove K1011K \le 1011. Consider Ai=[i1,i]A_i = [i - 1, i], i=1,2,,2021i = 1, 2, \dots, 2021. It is easy to see that we can find at most 1011 pairwise disjoint intervals, namely [0,1],[2,3],,[2020,2021][0, 1], [2, 3], \dots, [2020, 2021], so K1011K \le 1011.]

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 translated into English from zh; metadata (topic, difficulty) added by this project.