Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 iTest Problems/Problem 72"

(Created page with "== Problem == On the last afternoon of the Kubik family vacation, Michael puts down a copy of <math>\textit{Mathematical Olympiad Challenges}</math> and goes out to play tenni...")
 
m
 
Line 56: Line 56:
 
For the case <math>n=2007</math> we find that the set <math>\{669,670,\ldots ,2006,2007\}</math> has <math>2007-669+1=1336</math> elements any three of which sum to at least <math>669+670+671=2010</math>
 
For the case <math>n=2007</math> we find that the set <math>\{669,670,\ldots ,2006,2007\}</math> has <math>2007-669+1=1336</math> elements any three of which sum to at least <math>669+670+671=2010</math>
 
But for <math>668</math> missing terms, we see from the argument above that the assumption of no solutions leads to at least 669 missing terms - a contradiction.
 
But for <math>668</math> 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 box|num-b=71|num-a=73}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 04:16, 28 January 2019

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_iTest_Problems/Problem_72&oldid=101040"