Enigmatic Code

Programming Enigma Puzzles

Tantalizer 434: Limited editions

From New Scientist #985, 29th January 1976 [link]

Boremaster’s commentary on Hegel being a basic book, our library has several copies. It is not exactly a jolly read, as you will know if you have ever waded through its 36 chapters, but is much in demand on the ground that it is less painful than Hegel himself. Even so I was surprised to meet my friend Jones leaving the library with three copies under his arm.

“Steady on, old bean!” I exclaimed, “there are other readers to think of.”

“The other copies are all on the shelf”, he replied airily, “but I had to take three to get a complete text. Some rotter has snipped whole chapters out of every copy.”

“Well, surely two copies would have done?”

“No. No two copies would yield a full text.”

“Do you mean that I shall have to check every copy, if I want to be sure of a full text?”

“Oh no. Just take any three at random, as I did. You are bound to get a full text, even through no chapter is present in all copies. For each pair of chapters there is at least one copy with only one of them.”

For this to be true, how few copies need the library have in total?

[tantalizer434]

One response to “Tantalizer 434: Limited editions

  1. Jim Randell 6 March 2019 at 7:35 am

    I’ve marked the puzzle as flawed because the answer given in the magazine does not seem to be correct. Nevertheless I found this quite an interesting puzzle to solve.

    If we take any pair of books, then together they are missing at least one chapter (otherwise they would have the complete text). And the set of chapters that are missing must be present in all the remaining books (as any third book can be used to complete the text).

    If this set of missing chapters has two (or more) elements we can select a pair of chapters from it. Then both of those chapters are missing from each of the selected pair of books, but both must be present in all the other remaining books. So we cannot find a book that contains one of the chapters, but not the other. Contrary to the problem statement.

    So every pair of books must correspond to exactly one of the chapters (the chapter that missing from both books).

    But no pair can correspond to the same chapter, as then we could take one of the pairs, and add another book from the other pair, to get three books that were missing a single chapter. But any three books give the complete text, so this is not possible.

    Hence every pair of books must correspond to a different, unique chapter. There are 36 chapters, so there must be at most 36 different pairings of the books. The number of pairings of n books is C(n, 2), so:

    C(n, 2) ≤ 36
    ⇒ n ≤ 9

    If there were 9 books, then there would be C(9, 2) = 36 different pairings, and each of these corresponds to a different chapter.

    But can we manage with fewer than 9 books?

    Suppose there is a chapter that doesn’t correspond to one of the pairs. Let’s say chapter x.

    No chapter is present in every book. So there must be at least one book that is missing chapter x, so we select one of those books.

    Now we take any other book to form a pair with the first book. Together this pair of books must be missing only a single chapter. That chapter can’t be x, so there can only be a single book that is missing chapter x, and all the other books must contain it.

    So if we had 8 books, then there would be C(8, 2) = 28 different pairings, and each of these corresponds to a different chapter. Leaving 36 – 28 = 8 chapters that don’t correspond to a pair of books. Each of these chapters must be missing from a single book, and we have 8 books so we can manage it.

    With 7 books there would be C(7, 2) = 21 pairings, each corresponding to a chapter, leaving 36 – 21 = 15 chapters that don’t correspond to a pair of books. We can remove the first 7 of these, one from each of the books, but that still leaves 8 chapters, each of which needs to be removed from exactly one of the books. But we can’t remove more than one unique chapter from any book, because then that pair of chapters would be both present or both absent from any given book.

    So the described situation is only possible for 8 or 9 books.

    The following Python code constructs sets of 8 and 9 books and verifies they each meet the required conditions. It runs in 80ms.

    Run: [ @repl.it ]

    from itertools import combinations
    from enigma import irange, C, printf
    
    # all chapters
    chapters = set(irange(1, 36))
    
    # construct a set of k books
    def construct(k):
      # the number of pairs of books
      n = C(k, 2)
      assert not(n > len(chapters))
      books = irange(1, k)
      # map each pair of books to a unique chapter
      m = dict((k, v) for (k, v) in zip(combinations(books, 2), chapters))
      # each book is missing the chapters identified
      xs = list((set(v for (k, v) in m.items() if i in k) for i in books))
      # remaining chapters
      rs = chapters.difference(irange(1, n))
      assert not(len(rs) > k)
      # distribute the remaining chapters
      for (x, r) in zip(xs, rs): x.add(r)
      # now remove the identified chapters
      return list(chapters.difference(x) for x in xs)
    
    # verify the conditions of the problem
    def check(copies):
    
      # (1) "no two copies contain all chapters"
      for (a, b) in combinations(copies, 2):
        if a.union(b) == chapters:
          printf("-> (1) a={a} b={b}")
          return False
    
      # (2) "any three copies contain all chapters"
      for (a, b, c) in combinations(copies, 3):
        if a.union(b, c) != chapters:
          printf("-> (2) a={a} b={b} c={c}")
          return False
    
      # (3) "no chapter is present in all copies"
      if chapters.intersection(*copies):
        printf("-> (3) {x}", x=chapters.intersection(*copies))
        return False
    
      # (4) "for any pair of chapters there is at least one copy with only one of them"
      for x in combinations(chapters, 2):
        if not any(len(copy.intersection(x)) == 1 for copy in copies):
          printf("-> (4) {x}")
          return False
    
      return True
    
    # try with sets of 8 and 9 books
    for k in (8, 9):
      books = construct(k)
      r = check(books)
      printf("{k} copies = {r}")
      for (i, b) in enumerate(books, start=1):
        printf("  copy {i}: {b}", b=sorted(b))
      printf()
    

    Solution: The library must have at least 8 copies.

    But it must have no more than 9 copies of the book. The puzzle asked for the smallest possible number of copies.

    In each of the solutions, each of the books has 28 chapters (so is missing 8 chapters).


    The published answer is:

    Nine. Every pair of copies must lack at least one chapter present in all other copies. No pair can lack only the same chapters. There must be enough copies to make 36 pairs.

    Which implies that it would be possible with more than 9 copies, and not possible with fewer than 9. But as we have shown neither of these statements is true.

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: