[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

816.0. "the many-skilled-committee puzzle" by VIDEO::OSMAN (type video::user$7:[osman]eric.vt240) Thu Jan 14 1988 20:34

A committee is to be formed.  There are 100 candidates for the committee,
ranked from 1 to 100.

The total set of skills a candidate contributes if he joins the committee
is, first of all his rank, and rest of all the sums formed by adding
his rank to each skill already posessed by the committee.

However, no candidate may be elected for the committee if his contribution
of skills at all overlaps those skills already posessed by the committee.

For example, suppose we start out with no one on the committee.  Suppose
we elect candidate 2 to the committee.  Now the committee posesses
the single skill

	2

Now, suppose we elect candidate 3 to the committee.  He contributes skills
3 and 3+2, so the total skills possessed by the committee are

	2,3,5

By the rules, candidate 1 may not now be elected to the committee because
he would contribute skills 1,1+2,1+3,1+5.  But 1+2 is 3 which is already
a posessed skill of the committee, so 1 may not join.

What is the largest possible size of committee that may be elected ?  How many
different committees of this size are possible ?

For starters, it's fairly easy to see that candidates 1,2,4,8,16,32,64
may be elected as a valid committee.  That's a 7-member committee.  Is
there a valid 8-person committee ?  Is 7 the largest?  Are there
significantly different 7-member committees possible than 1,2,4,8,16,32,64?

Sleep well tonight..    .
		        . + )

/Eric
T.RTitleUserPersonal
Name
DateLines
816.1some thoughtsZFC::DERAMODaniel V. D'EramoFri Jan 15 1988 01:039
    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.2CLT::GILBERTBuilderFri Jan 15 1988 13:4511
>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.3Why not go for broke!AKQJ10::YARBROUGHWhy is computing so labor intensive?Fri Jan 15 1988 20:036
    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.4SSDEVO::LARYFri Jan 15 1988 21:183

			185 = 99 + 86 = 19 + 74 + 92
816.5CLT::GILBERTBuilderMon Jan 18 1988 15:5416
    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.6CLT::GILBERTBuilderTue Jan 19 1988 16:1336
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.7SSDEVO::LARYTue Jan 19 1988 22:378
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.8A curious patternSSDEVO::LARYTue Jan 19 1988 22:4419
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.9CLT::GILBERTBuilderWed Jan 20 1988 14:4255
>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.10CLT::GILBERTBuilderWed Feb 03 1988 16:2433
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)?