### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,270)
- misc (3)
- project euler (2)
- puzzle (67)
- site news (50)
- tantalizer (69)
- teaser (7)

### Site Stats

- 206,371 hits

Programming Enigma Puzzles

16 April 2018

Posted by on **From New Scientist #2222, 22nd January 2000** [link]

There are only 10 people on Small Island. However, there are many clubs, each consisting of the people with a particular interest. The island’s government will give a grant to any club with more than half the population as members. There are 12 such clubs.

The government wants to set up a committee of two so that every one of the 12 clubs has at least one member on the committee. This afternoon, the government is to look at the 12 membership lists and try to find 2 people to form the committee.

(1) This morning, before it sees the membership lists, can the government be certain that it will be able to find 2 people this afternoon?

There are 1000 people on Larger Island. The situation is similar to Small Island, except that there are 50 clubs that each have more than half the population as members. Also, the government wants to set up a committee of five so that every one of the 50 clubs has at least one member on the committee.

(2) Before the government sees the 50 membership lists, can it be certain that it will be able to find 5 people to form the committee?

The situation on Largest Island is similar to that on Larger Island, except that there are 1 million people.

(3) Before the government of Largest Island sees its 50 membership lists, can it be certain that it will be able to find five people to form its committee?

[enigma1066]

%d bloggers like this:

If you want to try this problem without any additional hints I suggest you stop reading this comment now.

For the first part there are 10 people in the population, so there are C(10, 2) = 45 possible committees of two people, and there are C(10, 6) = 210 possible clubs involving 6 people. Considering all collections of 12 clubs involving 6 people would mean considering C(210, 12) = 11149106984707682900 collections of clubs, but we can use a “greedy” algorithm to see if we can find a collection that cannot be represented by any committee of 2 people without having to consider all of them.

If we start with a list of the 45 possible committees of two people.

Each possible club partitions this list into a list of committees that can represent the club (i.e. at least one committee member is in the club) and a list of committees that cannot represent the club (if there are no committee members that are in the club).

So, when we are looking for counterexample, we can choose a club that eliminates the most remaining committees from consideration. Once we’ve found the club we add it to the collection of clubs, and remove the committees that cannot represent that club from consideration.

We then repeat the process with the remaining clubs and the remaining possible committees, until we have either eliminated all possible committees (in which case we have found our counterexample) or we have had made a collection of 12 clubs without eliminating all possible committees (in which case we have failed to find a counterexample).

For the first part of this puzzle a Python program finds a counterexample in 94ms.

Note that this is not necessarily a minimum sized counterexample. When we find the subset that eliminates the most potential committees there may be multiple possibilities. The Python code will choose one of maximal subsets arbitrarily, and running this program under Python 2.7 it finds a collection of 11 subsets that form a counterexample. With Python 3.6 and PyPy 5.10 it finds a collection of 10 subsets.

Either of these collections can be turned into a 12 subset counterexample (for instance, by simply duplicating some of the subsets – there is nothing in the puzzle to say that different clubs cannot have the same members).

Here is a 10 subset counterexample for the first part:

If the 10 inhabitants of the island are labelled A – J, the diagram shows the membership lists for 10 clubs each consisting of 6 of the inhabitants, where any possible 2 person committee will fail to represent at least one of the clubs. For example, a committee consisting of C and J would not represent club 5. Similarly, for any pair of inhabitants, you can find a club that is not represented by that pair.

For the second part, there is a population of 1000, so there are C(1000, 5) = 8250291250200 possible committees of 5 people. So just to make the list of possible committees is going to require more storage than my computer has, and even if I could store the list, the time taken to run the algorithm would be enormous, so this approach clearly isn’t going to fly for part (2) of the puzzle, and part (3) is even worse.

Fortunately, we can show that for the second and third parts of the puzzle it will always be possible to construct a committee consisting of 5 people that can represent all 50 clubs, regardless of the size of the population of the island.

Suppose there are

npeople on the island, and there arekclubs that include more than half the population.Then if we label the people from 1 to

nand the clubs from 1 tok, we can make a list of the cartesian product of the clubs and the members:Each of the

kclubs has more thann/2members so the number of entries inPsatisfies:_{1}So there must be a person who appears more than

k/2times on the list (as if everyone on the list appearsk/2times or less we have:which directly contradicts the previous statement).

In this instance

k = 50, so there is someone on the list (p) who appears more than 25 times on the list, i.e. is a member of at least 26 clubs. We appoint_{1}pas the first member of the committee, and remove 26 of the clubs from the list that can be represented on the committee by_{1}p._{1}So, we are left with

k=24clubs. We can proceed in the same way:By similar reasoning to that above we deduce that there is someone on this list (

p) who is a member of at least 13 clubs. We add_{2}pto the committee, and remove 13 of the clubs from the list that can be represented by_{2}p._{2}This leaves 11 clubs, and we can find a

pwho belongs to at least 6 of these clubs. So we add_{3}pto the committee, and remove the 6 clubs they represent from the list._{3}Leaving 5 clubs. We can find a

pwho belongs to at least 3 of these clubs. So we add_{4}pto the committee, and remove the 3 clubs they represent from the list._{4}Leaving 2 clubs. We can find a

pwho belongs to at least 2 of these clubs (i.e. belongs to all of the remaining clubs). So we add_{5}pto the committee, and we are done._{5}It doesn’t matter how large

nis, so we can say for parts (2) and (3) that we will always be able to find a committee with 5 members (or fewer, the individual members of committee found at each stage are not necessarily distinct) to represent all 50 clubs.In fact, a committee of 5 would work for any

kbetween 31 and 62 clubs. (Which is 32 (= 2^5) different values ofk, the next 64 (2^6) values would need a committee of 6, and the next 128 (2^7) a committee of 7, and so on).In general, a committee of size

q, will work forkin the range2^q – 1 ≤ k < 2^(q + 1) – 1.In the following Python program, the function [[

Q(k)]] calculates the correspondingqfor a given value ofk(using the mechanism described above). For each part, it first looks at theQvalue for the required number of clubs, and if this is more than the required committee size it proceeds to look for a counterexample (which it does in “greedy” order, so if there is a counterexample it shouldeventuallyfind it – however, if there is no counterexample it will take a long time to exhaust the possibilities even for relatively modest sized parameters).The program solves all three parts of the puzzle in 144ms.

Run:[ @repl.it ]Solution:(1) No, we cannot be certain of finding a representative 2 person committee; (2) & (3) Yes, we can be certain of finding a representative 5 person committee.In the first part we have

Q(12) = 3, so we can be certain that a committee of 3 or more can be found to represent 12 clubs. But for a committee of 2 the program quickly finds a counterexample for a population of 10 people.In the second and third parts we have

Q(50) = 5, so we can be certain that a committee of 5 or more can be found to represent 50 clubs.