Maths Olympiad Prep

Library / /26 of 115

Combinatorics Difficulty 6.9 National olympiad Find the answer

Let nn be a positive integer. Determine the size of the largest subset of {n,n+1,,n1,n}\{ - n, - n + 1, \ldots , n - 1, n\} which does not contain three elements a,b,ca, b, c (not necessarily distinct) satisfying a+b+c=0a + b + c = 0 .

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

Solution

Let SS be a subset of {n,n+1,,n1,n}\{-n,-n+1,\dots,n-1,n\} of largest size satisfying a+b+c0a+b+c\neq 0 for all a,b,cSa,b,c\in S . First, observe that 0S0\notin S . Next note that Sn/2|S|\geq \lceil n/2\rceil , by observing that the set of all the odd numbers in {n,n+1,,n1,n}\{-n,-n+1,\dots,n-1,n\} works. To prove that Sn/2|S|\leq \lceil n/2\rceil , it suffices to only consider even nn , because the statement for 2k2k implies the statement for 2k12k-1 as well. So from here forth, assume nn is even.
For any two sets AA and BB , denote by A+BA+B the set {a+baA,bB}\{a+b\mid a\in A,b\in B\} , and by A-A the set {aaA}\{-a\mid a\in A\} . Also, let A+A_+ denote A{1,2,}A\cap\{1,2,\dots\} and AA_- denote A{1,2,}A\cap\{-1,-2,\dots\} . First, we present a lemma:
Lemma 1 : Let AA and BB be two sets of integers. Then A+BA+B1|A+B|\geq|A|+|B|-1 .
Proof : Write A={a1,,an}A=\{a_1,\dots,a_n\} and B={b1,,bm}B=\{b_1,\dots,b_m\} where a1<<ana_1<\dots<a_n and b1<<bmb_1<\dots<b_m . Then a1+b1,a1+b2,,a1+bm,a2+bm,,an+bma_1+b_1,a_1+b_2,\dots,a_1+b_m,a_2+b_m,\dots,a_n+b_m is a strictly increasing sequence of n+m1n+m-1 integers in A+BA+B .
Now, we consider two cases:
Case 1 : One of n,nn,-n is not in SS . Without loss of generality, suppose nS-n\notin S . Let U={n+1,n+2,,n2,n1,n}U=\{-n+1,-n+2,\dots,n-2,n-1,n\} (a set with 2n2n elements), so that SUS\subseteq U by our assumption. Now, the condition that a+b+c0a+b+c\neq 0 for all a,b,cSa,b,c\in S implies that S(S++S)=-S\cap(S_++S_-)=\emptyset . Since any element of S++SS_++S_- has absolute value at most n1n-1 , we have S++S{n+1,n+2,,n2,n1}US_++S_-\subseteq \{-n+1,-n+2,\dots,n-2,n-1\}\subseteq U . It follows that S++SUSS_++S_-\subseteq U\setminus -S , so S++S2nS|S_++S_-|\leq 2n-|S| . However, by Lemma 1, we also have S++SS++S1=S1|S_++S_-|\geq |S_+|+|S_-|-1=|S|-1 . Therefore, we must have S12nS|S|-1\leq 2n-|S| , or 2S2n+12|S|\leq 2n+1 , or Sn|S|\leq n .
Case 2 : Both nn and n-n are in SS . Then n/2n/2 and n/2-n/2 are not in SS , and at most one of each of the pairs {1,n1},{2,n2},,{n21,n2+1}\{1,n-1\},\{2,n-2\},\ldots,\{\frac n2-1,\frac n2+1\} and their negatives are in SS . This means SS contains at most 2+(n2)=n2+(n-2)=n elements.
Thus we have proved that Sn=n/2|S|\leq n=\lceil n/2\rceil for even nn , and we are done.

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