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.

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

Page

Toolbox

Search

2008 iTest Problems/Problem 72

Problem

Solution

See Also