S = { 1 , 7 , 1 3 , 1 9 , 2 5 , … , 1 9 9 } .
Find the least value n such that for any subset T ⊂ S with n elements, we are guaranteed of finding two distinct elements of T that sum to 206.
Clarification: The elements of S are all integers of the form 6 k + 1 for all integers k from 0 to 3 3 inclusive.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Exactly Same Way, I loved this question.
The elements of S are of the form 6 k + 1 for k = 0 , 1 , 2 , 3 , . . . , 3 3 . We are required to find two elements 6 m + 1 and 6 n + 1 , where m , n have the same domain as k with m = n , such that
6 m + 1 + 6 n + 1 = 2 0 6 ⟹ 6 ( m + n ) = 2 0 4 ⟹ m + n = 3 4 .
Since m = n we can't have m = n = 1 7 , and neither of m , n can be 0 as the other element would need to be 3 4 , which is not in the domain of k . The other 3 2 numbers form 1 6 pairs that add to 3 4 , namely ( 1 , 3 3 ) , ( 2 , 3 2 ) , . . . . , ( 1 5 , 1 9 ) , ( 1 6 , 1 8 ) . We can then choose one element from each of these 1 6 pairs, along with 0 and 1 7 , and still not have two distinct elements that add to 3 4 , but by the Pigeonhole Principle, the next element chosen guarantees that we will two distinct elements that do add to 3 4 . So N = 1 6 + 2 + 1 = 1 9 .
Hi Brian,
What if the set S is {1,7,13,19,25,205,193,167,181,199} ?
Then every subset with 6 elements has a pair of elements that sums to 206. That's less than 19 isn't it?
My point is that just giving us a few elements of a set (S in this case) doesn't tell us anything about the other elements of the set!
Log in to reply
Well, with questions on this site I'm used to seeing partial sequences that give enough elements to imply the generating formula for the full sequence, and I believe I've provided enough elements here to do just that, but I will add a note of clarification.
Problem Loading...
Note Loading...
Set Loading...
Group the terms in S as follows: ( 1 , 1 0 3 ) , ( 1 9 9 , 7 ) , … , ( 1 0 9 , 9 7 ) . There are totally 17 groups.
If 2 elements are chosen from the same group other than the first group, then will sum up to 206.
By pigeonhole principle , the minimum number to be chosen to guarantee the sum of 206 is 1 7 + 1 + 1 = 1 9
Note that we added an extra 1 as we can choose both the elements from the first group.