1
$\begingroup$

Every student has a list of k-many books they need to read, and each book is on the reading list of k-many students. Each day, each student borrows a book, reads it, and returns it that evening (so no other student can read it that day). Assume also that there is only one copy of eachbook. Prove that it is possible for all students to complete their reading list after k-many days.

I do not even know how to decompose this problem. I am first trying to show a relationship between the total number of books and total number of students. It's like let the set of student X and the set of books Y and try to somehow show a matching. But here each book has two copies and we need to have show the scenario of k days. Is it related to permutation matrix? Please help me.

$\endgroup$
0
$\begingroup$

Let $X$ be the set of all students and $Y$ be the set of all books.

We construct a graph $G$ by letting $V(G) = X \cup Y$ and $$E(G) = \{(x,y) \in X \times Y | \textrm{ The student } x \textrm{ needs to read the book } y \}$$ Then $G$ is a $k$-regular bipartite graph. By Kőnig's theorem, there exist a matching with $k$ edges. This matching gives us the scenario.

$\endgroup$
  • $\begingroup$ If I understand you (and the OP) correctly, this is the inductive step, right? I.e. after the $k$-edge matching is removed, you're reduced to the problem with $k-1$, therefore by induction everyone can read all their books after doing this $k$ days in a row. $\endgroup$ – antkam Apr 5 at 19:00
  • $\begingroup$ Yes, you’re right. In fact, this is a corollary of Kőnig's theorem: Every $k$-regular bipartite graph contains $k$ edge-disjoint perfect matching. $\endgroup$ – Jerry Chang Apr 6 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.