T For Two

S = { 1 , 7 , 13 , 19 , 25 , , 199 } . S = \{1, 7, 13, 19, 25, \ldots , 199\}.

Find the least value n n such that for any subset T S T \subset S with n n elements, we are guaranteed of finding two distinct elements of T T that sum to 206.

Clarification: The elements of S S are all integers of the form 6 k + 1 6k + 1 for all integers k k from 0 0 to 33 33 inclusive.


The answer is 19.

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.

2 solutions

Group the terms in S S as follows: ( 1 , 103 ) , ( 199 , 7 ) , , ( 109 , 97 ) (1,103),(199,7),\ldots,(109,97) . 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 17 + 1 + 1 = 19 17+1+1=19

Note that we added an extra 1 as we can choose both the elements from the first group.

Exactly Same Way, I loved this question.

Kushagra Sahni - 5 years, 3 months ago

The elements of S S are of the form 6 k + 1 6k + 1 for k = 0 , 1 , 2 , 3 , . . . , 33 k = 0,1,2,3, ..., 33 . We are required to find two elements 6 m + 1 6m + 1 and 6 n + 1 6n + 1 , where m , n m, n have the same domain as k k with m n m \ne n , such that

6 m + 1 + 6 n + 1 = 206 6 ( m + n ) = 204 m + n = 34 6m + 1 + 6n + 1 = 206 \Longrightarrow 6(m + n) = 204 \Longrightarrow m + n = 34 .

Since m n m \ne n we can't have m = n = 17 m = n = 17 , and neither of m , n m,n can be 0 0 as the other element would need to be 34 34 , which is not in the domain of k k . The other 32 32 numbers form 16 16 pairs that add to 34 34 , namely ( 1 , 33 ) , ( 2 , 32 ) , . . . . , ( 15 , 19 ) , ( 16 , 18 ) (1,33), (2,32), .... , (15,19), (16,18) . We can then choose one element from each of these 16 16 pairs, along with 0 0 and 17 17 , and still not have two distinct elements that add to 34 34 , but by the Pigeonhole Principle, the next element chosen guarantees that we will two distinct elements that do add to 34 34 . So N = 16 + 2 + 1 = 19 N = 16 + 2 + 1 = \boxed{19} .

Hi Brian,

What if the set S is {1,7,13,19,25,205,193,167,181,199} ?

Then every subset with 6 \boxed{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!

Peter Macgregor - 2 years, 3 months ago

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.

Brian Charlesworth - 2 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...