| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 816.1 | some thoughts | ZFC::DERAMO | Daniel V. D'Eramo | Thu Jan 14 1988 22:03 | 9 |
| This reminded me of the trap-door knapsack cryptographic technique.
Pick a sequence a1 < a2 < a3 ... such that each a_n exceeds the sum
of all of the previous a_i. Multiply mod 100 by a number (such
as 17) that has a multiplicative inverse mod 100. Then check very
carefully to see if this gives a valid committee.
Will the order of selection ever affect the final outcome?
Dan
|
| 816.2 | | CLT::GILBERT | Builder | Fri Jan 15 1988 10:45 | 11 |
| >What is the largest possible size of committee that may be elected ?
Suppose that there are M members in a valid committee. There are
2**M different subsets of these members. The sums of the members
in each set are unique. If a valid committe of 10 members exists,
then there must be at least 2**10 numbers in the range 0 to 1000
(which is absurd). Thus, a valid committee must contain fewer than
10 members. The following appears to be a valid committe of eight
members.
50,74,86,92,96,98,99,100
|
| 816.3 | Why not go for broke! | AKQJ10::YARBROUGH | Why is computing so labor intensive? | Fri Jan 15 1988 17:03 | 6 |
| The following appears to be a valid committee of nine members. Or am I
missing something?
19,50,74,86,92,96,98,99,100
Lynn Yarbrough
|
| 816.4 | | SSDEVO::LARY | | Fri Jan 15 1988 18:18 | 3 |
|
185 = 99 + 86 = 19 + 74 + 92
|
| 816.5 | | CLT::GILBERT | Builder | Mon Jan 18 1988 12:54 | 16 |
| Does anyone mind if we generalize this slightly?
Define the power-set of a set S to be the set of all subsets of S.
Let S(m) be an m-member subset of {1..N}, and let P(S(m)) be the
power-set of S(m), and let Q(P(S(m))) be the set of sums of the
elements in P(S(m)). We want |Q(P(S(m)))| = |P(S(m))|.
Let F(m) be the smallest N such that there exists an S(m) with
|Q(P(S(m)))| = |P(S(m))|. For example,
F(1) = 1, ex: S(1) = {1}
F(2) = 2, ex: S(2) = {1,2}
F(3) = 4, ex: S(3) = {1,2,4}, or S(3) = {2,3,4}
F(4) = 7, ex: S(4) = {3,5,6,7}
F(5) = 13, ex: S(5) = {3,6,11,12,13}
|
| 816.6 | | CLT::GILBERT | Builder | Tue Jan 19 1988 13:13 | 36 |
| The following lists F(1) through F(7), and shows all the S(m) for these
F(1) = 1, S(1) = {1}
F(2) = 2, S(2) = {2,1}
F(3) = 4, S(3) = {4,3,2} or {4,2,1}
F(4) = 7, S(4) = {7,6,5,3}
F(5) = 13, S(5) = {13,12,11,9,6} or {13,12,11,6,3}
F(6) = 24, S(6) = {24,23,22,20,17,11}
F(7) = 44, S(7) = {44,43,42,40,37,31,20}
I'll conjecture that
F(8) = 84
F(9) = 161
F(10) = 309
F(11) = 594
and that, in general, F(m) is the smallest N such that the set
{ N-F(i) | 0 <= i < m } satisfies the uniqueness constraint
(here F(0) is taken as 0).
A different conjecture may be related to the following:
F(2) = 2*F(1) - 0
F(3) = 2*F(2) - 0
F(4) = 2*F(3) - 1
F(5) = 2*F(4) - 1
F(6) = 2*F(5) - 2
F(7) = 2*F(6) - 4
F(8) = 2*F(7) - 4
F(9) = 2*F(8) - 7
F(10) = 2*F(9) - 13
F(11) = 2*F(10) - 24
Note that the subtrahends are all F numbers.
|
| 816.7 | | SSDEVO::LARY | | Tue Jan 19 1988 19:37 | 8 |
|
Seven numbers is kinda small for a sweeping generalization, but it sure
looks like:
F(n) = F(n-1) + F(n-2) + F(n-3) for n > 3
In which case F(8) = 81, F(9) = 149, F(10) = 274, .....
|
| 816.8 | A curious pattern | SSDEVO::LARY | | Tue Jan 19 1988 19:44 | 19 |
| From the given list:
F(1) = 1, S(1) = {1}
F(2) = 2, S(2) = {2,1}
F(3) = 4, S(3) = {4,3,2} or {4,2,1}
F(4) = 7, S(4) = {7,6,5,3}
F(5) = 13, S(5) = {13,12,11,9,6} or {13,12,11,6,3}
F(6) = 24, S(6) = {24,23,22,20,17,11}
F(7) = 44, S(7) = {44,43,42,40,37,31,20}
Note that S(n) = {F(n)-F(i), -1 < i < n} where F(0) is defined to be 0.
It should be easy to verify that:
F(8) = 81, S(8) = {81,80,79,77,74,68,57,37}
F(9) = 149, S(9) = {149,128,147,145,142,136,125,105,68}
etc....
|
| 816.9 | | CLT::GILBERT | Builder | Wed Jan 20 1988 11:42 | 55 |
| >It should be easy to verify that:
>
> F(8) = 81, S(8) = {81,80,79,77,74,68,57,37}
> F(9) = 149, S(9) = {149,148,147,145,142,136,125,105,68}
^ (I fixed an apparent typo)
But 80+79+77 = 236 = 74+68+57+37,
And 147+145+142 = 434 = 136+125+105+68.
I had also made a conjecture along the following lines:
Suppose S(m) = { N-F(0), N-F(1), N-F(2), N-F(3), ..., N-F(m-1) },
where we take F(0) = 0.
Then the sums of subsets of these numbers fall into the ranges:
0*N
1*N - F(m-1) .. 1*N - F(0)
2*N - F(m-1) - F(m-2) .. 2*N - F(0) - F(1)
...
p p-1
p*N - Sum F(m-j) .. p*N - Sum F(j)
j=1 j=0
...
m-1
m*N - Sum F(j)
j=0
I conjectured that F(m) is the smallest N such that these ranges
don't overlap. This gives: F(1) = 1, F(2) = 2, ..., F(6) = 24,
but incorrectly gives F(7) = 46, F(8) = 88, .... To see why
this approach fails for F(7), we have the ranges:
0*N
1*N - z, z in {24,13,7,4,2,1,0}
2*N - z, z in {37,31,28,26..24,20,17,15..13,11,9..1}
3*N - z, z in {44,41,39..37,35,33..24,22..8,6,5,3}
4*N - z, z in {48,46,45,43..29,27..18,16,14..12,10,7}
5*N - z, z in {50..42,40,38..36,34,31,27..25,23,20,14}
6*N - z, z in {51,50,49,47,44,38,27}
7*N - 51
Treating these as ranges, we'd like the smallest N such that:
0 < N-24, N-1 < 2*N-37, 2*N-1 < 3*N-44, 3*N-3 < 4*N-48,
4*N-7 < 5*N-50, 5*N-14 < 6*N-51, and 6*N-27 < 7*N-51.
and we find N = 46 (due to the inequality 3*N-3 < 4*N-48).
However, we see that one set is able to overlap the other slightly:
..., 3*N-6,3*N-5, 3*N-3 }
{ 4*N-48, 4*N-46,4*N-45, 4*N-43,...
This manages to reduce N by 2, so that F(7) = 44.
|
| 816.10 | | CLT::GILBERT | Builder | Wed Feb 03 1988 13:24 | 33 |
| re .9:
For F(7), notice how densely packed are the 3*N-z and 4*N-z ranges:
density
-------
0*N
7/25 1*N - z, z in {24,13,7,4,2,1,0}
21/37 2*N - z, z in {37,31,28,26..24,20,17,15..13,11,9..1}
34/42 3*N - z, z in {44,41,39..37,35,33..24,22..8,6,5,3}
34/42 4*N - z, z in {48,46,45,43..29,27..18,16,14..12,10,7}
21/37 5*N - z, z in {50..42,40,38..36,34,31,27..25,23,20,14}
7/25 6*N - z, z in {51,50,49,47,44,38,27}
7*N - 51
Notice that in general the density is roughly:
"m choose p" - "sum of the p smallest elements"
----------------------------------------------------------
"sum of p largest elements" - "sum of p smallest elements"
Can the fact that these are so densely packed be used to give a
lower bound on F(8)? Can this in turn be used for a good lower
bound on F(9), F(10), ...? It certainly explains why F(m+1) is
roughly twice F(m).
Does the distribution of 'holes' at the ends of the ranges
(particularly the two 'center' ranges -- 3*N-z and 4*N-z in the
case of m=7) explain why
S(m) = { N-F(0), N-F(1), N-F(2), N-F(3), ..., N-F(m-1) }
always seems to provide the lowest F(m)?
|