Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Can you find the largest integer N with the following property?
Let S consist of any set of 10 distinct positive integers that are all less or equal than N. Prove that there will always exist at least two subsets of S whose elements sum to the same number.
Inspired by
http://answers.yahoo.com/question/index;%E2%80%A6
where it is shown that N is at least 100.
@Michael. Your upper bound is indeed correct but it's not the final answer. If you look at 4 numbers instead of 10 then {3,5,6,7} provides a "bad set" and yet 7 plays for 4 the role of 511 for 10.
@ Vikram; I looked at your answer, your previous answer and your references. I have 2 q's..
First line of your previous answer: "For 8 numbers less than 100 I have 1, 2, 4, 7, 13, 24, 44, 84"
What do you mean?
The Conway-Guy sequence does not claim to be sharp. So your special set with distinct subsums, shows that N < 309 but not that N = 308. Right?
@ Vikram, I went to the comment section. It is clear that singletons were always permitted. Otherwise {1,2,3} would be fine and there would be no need to go to {2,3,4}. Moreover there would not be 2^n subsets.
I stand by what I said before. I buy N < 309 but there is no evidence whatsoever that
N = 308.
@Vikram, to show that N = 106, you need to prove that 107 fails, namely you must find a set of 10 integers less or equal than 107 such that all subsets have distinct sums. The fact that a direct application of the pigeon hole principle fails to work does not prove anything.
@Vikram, well they just say that their "309" set is the best to date and that one would need to try 305 or below to improve on it. But indeed 110 days would be well beyond expiration date!
3 réponses
- Vikram PLv 5il y a 8 ansRéponse favorite
If I am not wrong the N = 308.
About a year ago I had answered a similar question asked by ben on this topic
http://answers.yahoo.com/question/index?qid=201204...
and amazingly enough my answer was part of http://oeis.org/A096858
As you can see the set {148, 225, 265, 285, 296, 302, 305, 307, 308, 309} is the one where sum of all subsets have distinct sums. Hence it can be said that when N is 308 any set of 10 distinct positive integers that are all less or equal than N will have at least two subsets of S whose elements sum to the same number.
=============
Since the question asked by ben was closed before i can update my answer more details are part of the comments section. The answer given in the main section is irrelevant.
Moreover as we need largest N i think N should equal 308.
============
Thanks to gianlino for explanation and Pauley Morph for providing further intuitions to the question via email.
Since The possible sums range from Σ{1} = 1 to Σ{N, N-1, ..., N-9} = 10N - 45.
A set containing 10 elements has 1023 non empty subsets.
So, for the pigeon hole principle to work, we need to find the largest N such that
10N - 45 < 1023
10N < 1068
N < 106.8
N = 106.
===============
Gianlino: Refer to last part of page 2 in this paper http://fks.sk/~kubus/doc/201012ssd.pdf
Where they have conclusively checked what we are seeking. I am astonished at time it took to verify this completely.
===========
Oh I see they have completely tested for 306, 307, 308, 309
- ?Lv 4il y a 8 ans
You can up lower bound for N to 106 with the pigeonhowl principle.
An Upper bound is 511 because the set {1,2,4,8,...,512} does not consist of two subsets with the same sum.
I don't have much time right now, but i guess it could be possible that 511 is indeed the largest N and it can probably be proven by induction on the number of elements of S.
Edit: Ah yes you are right of course, I jumped the gun on that one. Perhaps if I had had a bigger margin I would have noticed that my proofidea is wrong :P
- Anonymeil y a 5 ans
no longer extremely, If I comprehend you properly. anticipate that p1, p2, ........., pn are the sole primes the place p1 < p2 < .... < pn assume Q = p1 * p2 * ..... * pn +a million considering not one of the pk (a million<= i <= n) can divide Q (pk divides Q - a million => pk can't divide Q), we end that the two Q is a wonderful greater advantageous than pn or Q is a composite integer divisible via a wonderful greater advantageous than pn the two end means that the unique assumption that there are a finite variety of primes is fake
