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.

Inside the library of the university of Leuven, Belgium

Advertisements

8 thoughts on “Linear Algebra Riddle

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

  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

Leave a Reply

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