Book Arrangement Problem
There are ten books, each with fewer than 100 pages. Show that it is possible to arrange some or all of the ten books into two piles, with at least one book in each pile, so that the number of pages in each pile is the same.
Does anyone know how to go about doing this problem?? I am so stuck!!
I have 9 books with 10 pages each, and 1 book with 11 pages.
I am not able to divide 101 pages into two equal piles.
Is there something missing?
The problem says "some or all" of the books, so you could just put one book with 10 pages in one pile and another book with 10 pages in the other pile. Then declare success.
Originally Posted by aidan
There are 2^10 - 1 = 1023 non-empty subsets of the books. The maximum number of total pages in any subset is 10 x 99 = 990. Since this is less than the number of subsets, some two subsets must have the same number of total pages. These two subsets are not necessarily disjoint, but after we remove any books they have in common we are left with two disjoint subsets with the same number of total pages.
Originally Posted by kapowiee
Note that these two disjoint subsets must both be non-empty. Do you see why?