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
maxSSminx,yS,xy[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
minx,yS,xy[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<mxx2nn < m_x x \le 2n and consider the set S={mxx:xS}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 SS' 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 SS' if n=3n=3 or n5n \ge 5. Consequently, ()(*) holds for n=3n=3 or n5n \ge 5, and it clearly holds for n=2n=2.
If n=4n=4, then
min{[x,y]:x,y{5,6,7,8},xy}=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 1i<jn1 \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 j3j \ge 3, so n+j2(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 m4m \ge 4, then n+i<3(n/2+1)/2n+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.