Maths Olympiad Prep

Library / /44 of 520

Combinatorics Difficulty 4.9 AIME Find the answer

5. Given the set S={1,2,3,,2n,2n+1}S=\{1,2,3, \cdots, 2 n, 2 n+1\}, a subset TT of which has the property that for any three elements x,y,zx, y, z, x+yzx+y \neq z, then the maximum number of elements in TT is \qquad.

A number or a short expression. Spacing and $ signs are ignored.

Solution

5. n+1n+1.

Solution: Let TT contain a total of kk elements. Subtracting the other elements from the largest element in TT, the differences obtained are not in TT. Therefore, we have
k+(k1)2n+1k+(k-1) \leqslant 2 n+1, which means kn+1k \leqslant n+1. Additionally, the subset {n+1,n+1,,2n+1}\{n+1, n+1, \cdots, 2 n+1\} of SS contains n+1n+1 elements, which clearly meets the requirements of the problem. Hence, the maximum value of kk is n+1n+1.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.