### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,314)
- misc (3)
- project euler (2)
- puzzle (78)
- puzzle# (21)
- site news (54)
- tantalizer (80)
- teaser (7)

### Site Stats

- 217,164 hits

Programming Enigma Puzzles

6 March 2019

Posted by on **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]

%d bloggers like this:

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

nbooks isC(n, 2), so:If there were 9 books, then there would be

C(9, 2) = 36different 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 chapterx, and all the other books must contain it.So if we had 8 books, then there would be

C(8, 2) = 28different pairings, and each of these corresponds to a different chapter. Leaving36 – 28 = 8chapters 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) = 21pairings, each corresponding to a chapter, leaving36 – 21 = 15chapters 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 ]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:

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.