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 05:16, 28 January 2019
Problem
On the last afternoon of the Kubik family vacation, Michael puts down a copy of 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 such that
and
. 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 . Find the smallest value of
such that given any subset
of
where
, then there are necessarily distinct
for which
." Find the answer to Michael's generalization.
Solution
The statement is FALSE for . The set
contains
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 . The proof is as follows:
let be the minimum and
be the maximum and
the set is thus missing the terms
and
we have 2 cases:
case 1 : is even
we have the following potential solutions for the statement:
for the set not to contain an solution, it must be missing either the
or
term (or both) in each of the above equations.
The number of equations above is
which must satisfy
.
This implies
.
Thus the total number of missing values from the set S is at least the size of the missing beginning terms
plus the size of the missing ending terms
plus the
terms missing in the above equations.
This simplifies to
.
If the set contains terms, then
and
which implies
(or more) terms are missing which
contradicts the assumption that only
terms are missing.
case 2 : is odd
we have the following potential solutions for the
statement:
for the set not to contain an a+b+c=d solution, it must be missing either the or the
term (or both) in each of the above equations.
The number of equations above is
which must satisfy
.
This implies
.
Thus the total number of missing values from the set S is at least the size of the missing beginning terms
plus the size of the missing ending terms
plus the
terms missing in the above equations.
This simplifies to
.
If the set contains 68 terms, then and
which is possible if
and
For the case we find that the set
has
elements any three of which sum to at least
But for
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 |