Maths Olympiad Prep

Library / /247 of 520

Combinatorics Difficulty 5.2 AIME, harder Find the answer

1. Given the set S={1,2,,3n},nS=\{1,2, \cdots, 3 n\}, n is a positive integer, TT is a subset of SS, satisfying: for any x,y,zTx, y, z \in T (where x,y,zx, y, z can be the same), we have x+y+zTx+y+z \notin T. Find the maximum number of elements in all such sets TT.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. If we take T0={n+1,n+2,,3n}T_{0}=\{n+1, n+2, \cdots, 3 n\}, then T0=2n\left|T_{0}\right|=2 n, and the sum of any three numbers in T0T_{0} is greater than 3n3 n, i.e., not in T0T_{0}. Therefore, maxT2n\max |T| \geqslant 2 n.
On the other hand, consider the sequence of three-element subsets
A0={n,2n,3n}A_{0}=\{n, 2 n, 3 n\},
Ak={k,2nk,2n+k}(k=1,2,,n1)A_{k}=\{k, 2 n-k, 2 n+k\}(k=1,2, \cdots, n-1).
Then S=k=0n1AkS=\bigcup_{k=0}^{n-1} A_{k}.
For any (2n+1)(2 n+1)-element subset TT^{\prime} of SS, it must contain some AkA_{k}.
If A0TA_{0} \subset T, then it contains the element 3n=n+n+n3 n=n+n+n;
If some AkT(k{1,2,,n1})A_{k} \subset T^{\prime}(k \in\{1,2, \cdots, n-1\}), then it contains the element 2n+k=k+k+(2nk)2 n+k=k+k+(2 n-k).
Thus, maxT<2n+1\max |T|<2 n+1.
Therefore, maxT=2n\max |T|=2 n.

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.