Enigmatic Code

Programming Enigma Puzzles

Enigma 247: Metacrisis

From New Scientist #1394, 26th January 1984 [link]

Professor Plato has been trying to assemble a complete set of the Metacritical Quarterly in the hope of unearthing some fresh dialectical insight in its footnotes. He has a heap of the issues himself and so does each of his eleven colleagues. Frustratingly, however, no single one of them has what he is short of. Indeed no pair of the twelve can muster a full set.

But he need not despair. What no two of them can muster any three can combine to produce. Indeed any and every trio of the scholarly dozen can rustle up a complete set by joining forces. These facts could not be so among a group of such a size, had there been less issues of the journal.

So many issues of the Metacritical Quarterly have there been?

It would annoy fewer pedants if the question had been phrased: “… had there been fewer issues of the journal”.

[enigma247]

Advertisements

One response to “Enigma 247: Metacrisis

  1. Jim Randell 1 January 2015 at 9:42 am

    A bit of analysis gives us the solution straight away. So there’s not much for a program to do.

    If we consider each pair of academics, A and B, then if they combine their collection they have some (non-empty) set of missing issues, m(A, B), and every other academic must have these missing issues in his collection. This implies that all the sets, m(A, B), must be disjoint.

    So to minimise the number of issues of the magazine we make the sets, m(A, B) as small as possible, i.e. each set contains exactly one issue, and as they are disjoint there is exactly one issue for each pairing of the academics.

    Hence the total number of issues is C(12, 2).

    Solution: The number of issues of Metacritical Quarterly is 66.

    There is essentially only one way to achieve the solution. For each issue of the magazine there is exactly one pair of the academics that are both missing that issue and the remaining academics have it. So (modulo renaming) the distribution of magazines looks like this:

    Enigma 247 - Solution

    (The black squares indicate where an academic has the issue and the red squares indicate where they are missing an issue).

    Each academic has 55 issues and is missing 11 issues.

    So I don’t have to add this puzzle to the Unsolved Programatically list, here’s a Python program that demonstrates the distribution of the magazines and verifies that if any any three of the academics pool their collection they have a complete set of journals.

    from collections import defaultdict
    from itertools import combinations
    from enigma import irange, printf
    
    # number of people
    import sys
    N = (12 if len(sys.argv) < 2 else int(sys.argv[1]))
    people = tuple(irange(1, N))
    
    # assign issues to each person
    ms = defaultdict(list)
    n = 0
    for ns in combinations(people, 2):
      n += 1
      # every one except this pair have this issue
      for i in people:
        if i not in ns:
          ms[i].append(n)
    
    printf("{n} issues")
    for k in sorted(ms.keys()):
      v = ms[k]
      printf("{k}: {v}")
    
    # check every triple have a complete set
    assert all(len(set().union(*(ms[i] for i in ns))) == n for ns in combinations(people, 3))
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: