[math-fun] A problem about finite sets
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? Victor
Nice problem. Can't answer 2) at this stage, though strongly suspect yes! My best so far non-P set of 8 is {86,85,84,82,79,73,62,42} Can anyone improve on 86? WFL 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?
Victor _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
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
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
Can you say more about how the FPGA is used? If I'm remembering the details correctly, Beeler & Ankeny used the DARPA "guest chip" facility in the early 80's to create a custom chip for solving a particular Ramsey-number-ish problem. I expected this area to grow, especially as FPGAs eliminated the DARPA dependency. But I haven't seen any more results using this idea. My own (very brief) experience is that FPGAs are hard to program. Rich ---------- Quoting "J.P. Grossman" <jpg@alum.mit.edu>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sure thing. This problem happens to map to an FPGA really well because it can be expressed as shifts and masks. Here's pseudocode for a software implementation: search (mask, upper_int, num_ints_remaining) if num_ints_remaining == 0 then success! mask = mask | (mask << upper_int) | (mask >> upper_int) foreach i in [1,upper_int-1] such that mask[i] == 0 search(mask, i, num_ints_remaining - 1) find_best () foreach i in [1, infinity) search(1, i, 8) mask is conceptually an infinite bitmask where the kth bit is mask[k] for k in (-inf,inf); of course it's not too hard to bound the actual number of bits required. The hardware implementation is nearly identical, with the depth-8 recursion replaced by eight copies of a search module connected in a row. FPGAs are definitely harder to program than CPUs. These days you're generally better off using GPUs to accelerate whatever problem you're working on, although Microsoft is doing some *very* interesting work on integrating FPGAs into their data centers ( https://www.microsoft.com/en-us/research/project/project-catapult/). I just happened to have a Stratix IV GX development board sitting on my desk, and when you have a hammer... J.P. On Fri, Sep 9, 2016 at 1:24 PM, <rcs@xmission.com> wrote:
Can you say more about how the FPGA is used? If I'm remembering the details correctly, Beeler & Ankeny used the DARPA "guest chip" facility in the early 80's to create a custom chip for solving a particular Ramsey-number-ish problem. I expected this area to grow, especially as FPGAs eliminated the DARPA dependency. But I haven't seen any more results using this idea. My own (very brief) experience is that FPGAs are hard to program.
Rich
---------- Quoting "J.P. Grossman" <jpg@alum.mit.edu>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You should add this as a sequence in the OEIS! (Let me know if you need a hand.) The Conway-Guy sequence (A005318) is already in, but as I understand the Lunnon paper shows that this is not optimal by the 67th term at the latest. Charles Greathouse Case Western Reserve University On Fri, Sep 9, 2016 at 7:38 AM, J.P. Grossman <jpg@alum.mit.edu> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let P be a real, symmetric, positive-definite matrix. Is there a fast way to determine the diagonal elements of P inverse without having to find the entire inverse? -- Gene
On Wed, 3 Oct 2012, Victor Miller 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?
I saw this several years ago and came up with a cute solution to part 2. First, part 1: There are 1024 subsets of A, each of which has sum in the range from 0 to 1000, so by the pigeon-hole principle, two of the sums must be equal. Remove their intersection from each to get two disjoint subsets with the same sum. Now part 2: We restrict to a certain collection of sums, namely those of at most 6 numbers, but including at least 2 of the 6 largest ones. There are 2^9 = 512 total sums. There are 1 + 9 + 36 sums of 9, 8, or 7 numbers. There are 2^3 = 8 subsets of the smallest three numbers, so there are 8*(1 + 6) subsets containing at most 1 of the 6 largest numbers. So there are 512 - 46 - 56 = 410 sums in our collection. The largest sum in our collection is the sum of the 6 largest numbers, while the smallest is the sum of the 5th and 6th largest numbers. The difference between these is the sum of the 4 largest numbers, so all of our sums are in a range of size at most 100*4 + 1 = 401 < 410. Thus two sums are equal, and we are done, as above. In fact, if you just know that the numbers are at most 103, then 103 + 102 + 101 + 100 + 1 < 410 still tells you that two disjoint sums are equal. In other words, if you have 9 natural numbers with distinct sums, the largest is at least 104. More complicated arguments can get you the exact bound, but it's interesting that this argument gets you this far, so it might have been the intent of the original poser. David P. Moulton
participants (8)
-
Charles Greathouse -
David P. Moulton -
Eugene Salamin -
Fred lunnon -
Fred W. Helenius -
J.P. Grossman -
rcs＠xmission.com -
Victor Miller