2008 iTest Problems/Problem 72

Problem

On the last afternoon of the Kubik family vacation, Michael puts down a copy of $\textit{Mathematical Olympiad Challenges}$ and goes out to play tennis. Wendy notices the book and decides to see if there are a few problems in it that she can solve. She decides to focus her energy on one problem in particular:

Given 69 distinct positive integers not exceeding 100, prove that one can choose four of them $a,b,c,d$ such that $a<b<c$ and $a+b+c=d$. Is this statement true for 68 numbers?

After some time working on the problem, Wendy finally feels like she has a grip on the solution. When Michael returns, she explains her solutions to him. "Well done!" he tells her. "Now, see if you can solve this generalization. Consider the set $S=\{1,2,3,\ldots,2007,2008\}$. Find the smallest value of $t$ such that given any subset $T$ of $S$ where $|T|=t$, then there are necessarily distinct $a,b,c,d\in T$ for which $a+b+c=d$." Find the answer to Michael's generalization.

Solution

The statement is FALSE for $n=68$. The set $\{33,34,35,\ldots,99,100\}$ contains $68$ positive integers and the sum of any three is at least 33+34+35=102>100. So given any four, the sum of a subset of three exceeds the possible value for the fourth.

The assertion is TRUE for $n=69$. The proof is as follows:

let $lo$ be the minimum and $hi$ be the maximum and $z=\frac{hi-lo}{2}$ the set is thus missing the terms $\{1,\ldots,lo-1\}$ and $\{hi+1,\ldots,100\}$ we have 2 cases:

case 1 :$(hi-lo)$ is even

we have the following potential solutions for the $a+b+c=d$ statement: \[1)lo+(z-1)+(z+1)=hi\] \[2)lo+(z-2)+(z+2)=hi\] \[...................\] \[q)lo+(z-q)+(z+q)=hi\]

for the set not to contain an $a+b+c=d$ solution, it must be missing either the $z-n$ or $z+n$ term (or both) in each of the above equations. The number of equations above is $q$ which must satisfy $(lo+1)<=z-q<z+q<=(hi-1)$ . This implies $1<=q<=(z-lo-1)=\frac{(hi-lo)}{2}-lo-1=\frac{hi}{2}-3\frac{lo}{2}-1$.

Thus the total number of missing values from the set S is at least the size of the missing beginning terms $\vert \{1,\ldots,lo-1\}\vert$ plus the size of the missing ending terms $\vert\{hi+1,\ldots,100\}\vert$ plus the $q$ terms missing in the above equations. This simplifies to $\vert missing\vert>=lo+(hi/2-3lo/2-1)+(100-hi)=(100-1)-(hi+lo)/2$.

If the set contains $69$ terms, then $132>=hi+lo>=70$ and $33<=99-(hi+lo)/2<=64$ which implies $33$ (or more) terms are missing which contradicts the assumption that only $100-69=31$ terms are missing.


case 2 :$(hi-lo)$ is odd we have the following potential solutions for the $a+b+c=d$ statement: \[1)lo+(z-\frac{1}{2})+(z+\frac{1}{2})=hi\] \[2)lo+(z-\frac{3}{2})+(z+\frac{3}{2})=hi\] \[...................\] \[q)lo+(z-\frac{2q-1}{2})+(z+\frac{2q-1}{2})=hi\]

for the set not to contain an a+b+c=d solution, it must be missing either the $z-\frac{2n-1}{2}$ or the $z+\frac{2n-1}{2}$ term (or both) in each of the above equations. The number of equations above is $q$ which must satisfy $(lo+1)<=z-\frac{2q-1}{2}<z+\frac{2q-1}{2}<=(hi-1)$ . This implies $1<=q<=(z-lo-1)+\frac{1}{2}=\frac{(hi-lo)}{2}-lo-\frac{1}{2}=\frac{hi}{2}-3\frac{lo}{2}-\frac{1}{2}$.

Thus the total number of missing values from the set S is at least the size of the missing beginning terms $\vert \{1,\ldots,lo-1\}\vert$ plus the size of the missing ending terms $\vert\{hi+1,\ldots,100\}\vert$ plus the $q$ terms missing in the above equations. This simplifies to $\vert missing\vert >=lo+(hi/2-3lo/2-\frac{1}{2})+(100-hi)=(100-\frac{1}{2})-(hi+lo)/2$.

If the set contains 68 terms, then $133>=hi+lo>=69$ and $32.5<=99.5-(hi+lo)/2<=64.5$ which is possible if $hi=100$ and $lo=33$


For the case $n=2007$ we find that the set $\{669,670,\ldots ,2006,2007\}$ has $2007-669+1=1336$ elements any three of which sum to at least $669+670+671=2010$ But for $668$ missing terms, we see from the argument above that the assumption of no solutions leads to at least 669 missing terms - a contradiction.


See Also

2008 iTest (Problems)
Preceded by:
Problem 71
Followed by:
Problem 73
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100