# 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.

## 11 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.

• Eggue |

Could you explain why {i such that a_i>0} and {i such that a_i<0} are disjoint? I was thinking of the case where for n = 2 books, you could assign vectors v_1 = (1, 0), v_2 = (1, 0) and v_3 = (1, 0) to 3 people. In this case the sum is 2v_1 – v_2 – v_3 = 0. But the sets are {(1, 0)} and {(1, 0)} which are not disjoint.

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

5. Bill Sere |

I found this riddle as an exercise in a linear algebra book and tried to solve it. If I understand correctly, what the riddle says is there must be a group of book (say, 3) that two disjoint (non-intersected) groups of subscribers read and ONLY these 3 books do these subscribers read – correct me if I’m wrong. If there are n subscriber (s_1 to s_n) and n+1 book (b_1 to b_n+1), s_1 reads b_1 and s_i reads b_i and b_i+1, where i = 2 to n (that is, s_2 reads b_2 and b_3; s_3 reads b_3 and b_4, …, s_n reads b_n and b_n+1), then there won’t be two subscribers who read the same set of book. I kinda don’t get the premise of this question.

• Hi Bill,

You assume that there are n subscribers and n+1 books, in which case the claim is indeed wrong. In the problem there are n books and n+1 subscribers.