Enigmatic Code

Programming Enigma Puzzles

Enigma 1066: Members of the clubs

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]

One response to “Enigma 1066: Members of the clubs

  1. Jim Randell 16 April 2018 at 8:29 am

    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.

    from itertools import combinations
    from enigma import irange, unpack, printf
    
    def counterexample(n, m, k):
    
      # the population
      p = set(irange(1, n))
    
      # the number of k-sized committees
      cs = set(combinations(p, k))
    
      # for each m-sized subset s, map m to the committees that don't represent it
      d = dict()
      for s in combinations(p, m):
        d[s] = set(c for c in cs if not set(s).intersection(c))
    
      # try to find a collection of subsets that eliminates all committees
      ss = set()
      while cs:
        # find a subset that eliminates the most potential committees
        (s, x) = max(d.items(), key=unpack(lambda s, x: len(x)))
        if not x: return
        # add it to the collection
        ss.add(s)
        # remove the eliminated committees
        d.pop(s)
        for (k, v) in d.items():
          v.difference_update(x)
        cs.difference_update(x)
    
      # return the collection
      return ss
    
    # try to find a counterexample for part 1 of the puzzle
    (n, m, k) = (10, 6, 2)
    s = counterexample(n, m, k)
    if s:
      printf("[n={n} m={m} k={k}] counterexample: size={x} {s}", x=len(s), s=sorted(s))
    

    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 n people on the island, and there are k clubs that include more than half the population.

    Then if we label the people from 1 to n and the clubs from 1 to k, we can make a list of the cartesian product of the clubs and the members:

    P1 = [ (i, x) : i = 1 to k, x is in club i ]

    Each of the k clubs has more than n/2 members so the number of entries in P1 satisfies:

    |P1| > k(n/2)

    So there must be a person who appears more than k/2 times on the list (as if everyone on the list appears k/2 times or less we have:

    |P1| ≤ n(k/2)

    which directly contradicts the previous statement).

    In this instance k = 50, so there is someone on the list (p1) who appears more than 25 times on the list, i.e. is a member of at least 26 clubs. We appoint p1 as the first member of the committee, and remove 26 of the clubs from the list that can be represented on the committee by p1.

    So, we are left with k=24 clubs. We can proceed in the same way:

    P2 = [ (i, x) : i=1 to k, x in is club i ]

    By similar reasoning to that above we deduce that there is someone on this list (p2) who is a member of at least 13 clubs. We add p2 to the committee, and remove 13 of the clubs from the list that can be represented by p2.

    This leaves 11 clubs, and we can find a p3 who belongs to at least 6 of these clubs. So we add p3 to the committee, and remove the 6 clubs they represent from the list.

    Leaving 5 clubs. We can find a p4 who belongs to at least 3 of these clubs. So we add p4 to the committee, and remove the 3 clubs they represent from the list.

    Leaving 2 clubs. We can find a p5 who belongs to at least 2 of these clubs (i.e. belongs to all of the remaining clubs). So we add p5 to the committee, and we are done.

    It doesn’t matter how large n is, 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 k between 31 and 62 clubs. (Which is 32 (= 2^5) different values of k, 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 for k in the range 2^q – 1 ≤ k < 2^(q + 1) – 1.

    In the following Python program, the function [[ Q(k) ]] calculates the corresponding q for a given value of k (using the mechanism described above). For each part, it first looks at the Q value 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 should eventually find 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 ]

    from itertools import combinations
    from enigma import irange, unpack, divc, printf
    
    # find the size of a committee for k clubs
    def Q(k):
      q = 0
      while k > 0:
        q += 1
        k -= (k + 2) // 2
      return q
    
    # find collections of <k> clubs, that cannot be represented by a committe of size <h>
    def counterexample(n, k, h):
    
      # the population
      p = set(irange(1, n))
    
      # find counterexamples in "greedy" order
      def fn(k, n, cs, ss):
        # while there are committees and space left in the collection
        if cs and k:
          # make a list of each possible subset, and the committees that can represent it
          xs = list((s, set(c for c in cs if set(c).intersection(s))) for s in combinations(p, n) if s not in ss)
          # sort the list according to the fewest remaining candidate committees
          xs.sort(key=unpack(lambda s, x: len(x)))
          for (s, x) in xs:
            yield from fn(k - 1, n, x, ss + [s])
        elif not cs:
          # the are no potential committees remaining, so we are done
          yield ss
    
      # possible h-sized committees
      cs = set(combinations(p, h))
    
      # look for counterexamples that eliminate all possible committees
      yield from fn(k, divc(n + 1, 2), cs, [])
    
    
    parts = [
      (10, 12, 2), # (1)
      (1000, 50, 5), # (2)
      (1000000, 50, 5), # (3)
    ]
    
    # consider each part of the question
    for (i, (n, k, h)) in enumerate(parts, start=1):
      q = Q(k)
      if not(q > h):
        # we can find a committee of size h 
        printf("({i}) Yes [Q({k}) = {q} <= {h}]")
      else:
        # look for a counterexample
        for s in counterexample(n, k, h):
          printf("({i}) No [Q({k}) = {q} > {h}]")
          printf("counterexample: size={x} {s}", x=len(s), s=sorted(s))
          break # we only need one counterexample
        else:
          # failed to find a counterexample
          printf("({i}) Yes [Q({k}) = {q} > {h}]")
    

    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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: