Linear Algebra Riddle

I’d like to tell you about a nice riddle, which I heard from Bob Krueger (one of our current REU participants, who already has four papers on arXiv!!). The riddle requires very basic linear algebra and is in the spirit of the previous post.

Riddle. A library has $n$ books and $n+1$ subscribers. Each subscriber read at least one book from the library. Prove that there must exist two disjoint sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

Hint: Very basic linear algebra. Try the first thing that comes to mind.

8 thoughts on “Linear Algebra Riddle”

1. Michele |

Consider this scenario: each subscriber reads only one book, and all books have at least one reader. Thus, because |S| = |B|+1, there must be exactly one book (let us call it b_i) with two readers (let us call them s_j and s_k, j!=k). The two disjoint groups we are looking for are G1 = {s_j} and G2={s_k}.

All other scenarios are simpler than this one, I think. In any case, it is sufficient that at least two subscribers read the same book. And this is always true.

• I’m afraid I don’t follow this argument. Say that every person read exactly 5 books. Then there are clearly many pairs of people who read a common book, but there is no reason for two people to have read the same exact five books. What happens then?

2. Yuzhou Gu |

For each person assign a vector v_i in R^n, where a position is 1 if the person reads the book, and 0 otherwise. Because the vectors are linear dependent, we will have a equation of the form sum a_i v_i = 0. Then {i such that a_i>0} and {i such that a_i<0} are two disjoint sets with same union of read books.

Indeed very basic linear algebra… This is my second thought though. My first thought was working over F_2 but did not quite work.

3. johnny cash |

to make it more fun for everyone, you should have removed all mention of linear algebra from this post, both the title and the hint.

• There is also a simple solution that does not involve Linear Algebra. But that’s not as fun!

• Kenz Kallal |

What’s the non-linear algebra solution that you had in mind?

• When I wrote the previous message, I thought I had a simple proof by induction on n. But now I cannot remember how it worked. Perhaps I was wrong…

4. A mentor at the Mathcamp I went to in high school designed an excellent card game along the same linear algebra principles! In the game, you deal out 7 cards at a time, and search for a set with certain properties, much like the more famous game Set, but unlike Set, this goal is provably always possible (and this proof is very similar to the answer to this riddle).

It’s for sale now, if it’s ok to link to the product, but this link also contains spoilers to the riddle:
https://boardgamegeek.com/boardgame/127112/zero-sumz