Maths Olympiad Prep

Library / /35 of 70

Number theory Difficulty 8.2 Shortlist Prove it Romania

Let nn be an integer greater than 11 and let SS be the set of nn-element subsets of the set {1,2,…,2n}\{1, 2, \dots, 2n\}. Determine
max⁡S∈Smin⁡x,y∈S,x≠y[x,y], \max_{S \in \mathcal{S}} \min_{x, y \in S, x \neq y} [x, y],
where [x,y][x, y] denotes the least common multiple of the integers xx and yy.

Solution

The required value is 6(⌊n/2⌋+1)6(\lfloor n/2 \rfloor + 1), unless n=4n=4 in which case it is 2424. Let SS be a member of S\mathcal{S}. We first show that
min⁡x,y∈S,x≠y[x,y]≤6(⌊n/2⌋+1),(∗) \min_{x, y \in S, x \neq y} [x, y] \le 6(\lfloor n/2 \rfloor + 1), \quad (*)
unless n=4n = 4. To this end, for each xx in SS, choose a positive integer mxm_x such that n<mxx≤2nn < m_x x \le 2n and consider the set S′={mxx:x∈S}S' = \{m_x x : x \in S\}.
If ∣S′∣<n|S'| < n, then mxx=myym_x x = m_y y for some distinct elements xx and yy in SS, so [x,y]≤2n[x, y] \le 2n.
If ∣S′∣=n|S'| = n, then S′={n+1,n+2,…,2n}S' = \{n+1, n+2, \dots, 2n\}. The first even number in S′S' is 2(⌊n/2⌋+1)2(\lfloor n/2 \rfloor + 1), and the number 3(⌊n/2⌋+1)3(\lfloor n/2 \rfloor + 1) is also in S′S' if n=3n=3 or n≥5n \ge 5. Consequently, (∗)(*) holds for n=3n=3 or n≥5n \ge 5, and it clearly holds for n=2n=2.
If n=4n=4, then
min⁡{[x,y]:x,y∈{5,6,7,8},x≠y}=24, \min \{[x, y] : x, y \in \{5, 6, 7, 8\}, x \neq y\} = 24,
which is the required value by the preceding.
Finally, we show that, if 1≤i<j≤n1 \le i < j \le n, then [n+i,n+j]≥6(⌊n/2⌋+1)[n+i, n+j] \ge 6(\lfloor n/2 \rfloor + 1). Suppose, if possible, that [n+i,n+j]<6(⌊n/2⌋+1)[n+i, n+j] < 6(\lfloor n/2 \rfloor + 1). Since [n+1,n+2]=(n+1)(n+2)≥6(⌊n/2⌋+1)[n+1, n+2] = (n+1)(n+2) \ge 6(\lfloor n/2 \rfloor + 1), it follows that j≥3j \ge 3, so n+j≥2(⌊n/2⌋+1)n+j \ge 2(\lfloor n/2 \rfloor + 1). Hence [n+i,n+j]=2(n+j)=m(n+i)[n+i, n+j] = 2(n+j) = m(n+i), where mm is an integer greater than 22. If m=3m=3, then n+in+i must be an even number less than 2(⌊n/2⌋+1)2(\lfloor n/2 \rfloor + 1) which is impossible. If m≥4m \ge 4, then n+i<3(⌊n/2⌋+1)/2≤n+1n+i < 3(\lfloor n/2 \rfloor + 1)/2 \le n+1 which is again impossible. This ends the proof.

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.