Minor update for an old thread... I ran a search and found that the smallest n for which there exists a set of 9 integers in [1,n] with distinct subset sums is 161. I believe (correct me if I'm wrong) that this was previously conjectured but not known. It was already known that a solution exists for n = 161 ( {161, 160, 159, 157, 154, 148, 137, 117, 77}, constructed from the Conway-Guy sequence). The search took about 30 minutes on an FPGA (I'm pretty sure this could be sped up by at least 10x with some additional work, but 30 minutes was fast enough). J.P. On Thu, Oct 4, 2012 at 7:22 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
This 1988 paper by one W. F. Lunnon shows that 84 is optimal:
Uh-huh ... must have been a clever fellow --- wonder what happened to him? WFL
On 10/4/12, Fred W. Helenius <fredh@ix.netcom.com> wrote:
On 10/3/2012 9:52 PM, Fred lunnon wrote:
Nice problem.
Can't answer 2) at this stage, though strongly suspect yes!
I'd have to agree.
My best so far non-P set of 8 is
{86,85,84,82,79,73,62,42}
Can anyone improve on 86?
This 1988 paper by one W. F. Lunnon shows that 84 is optimal:
http://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917837-5/
(The definition there omits "non-empty" and "disjoint", but that doesn't actually change the property: if two distinct overlapping subsets have the same sum, so do the disjoint subsets produced by removing their intersection.)
On 10/3/12, Victor Miller <victorsmiller@gmail.com> wrote:
Say that a finite set of integers, A, has *property P* is there are two non-empty disjoint subsets S and T of A, such that sum(S) = sum(T) (where sum(X) is the sum of the elements of X).
1) Show that every 10 element subset of {1,...,100} has property P (this is fairly easy). 2) Is it true that every 9 element subset of {1,...,100} has property P?
-- Fred W. Helenius fredh@ix.netcom.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun