In a certain library there are n shelves, each holding at least one book. k new shelves are acquired and the books are rearranged on the n+k shelves, again with at least one book on each shelf.
A book is said to be "privileged" if it is on a shelf with fewer books in the new arrangement than it was in the original arrangement.
Prove that there are at least k+1 privileged books in the rearranged library.
Originally posted by David113 In a certain library there are n shelves, each holding at least one book. k new shelves are acquired and the books are rearranged on the n+k shelves, again with at least one book on each shelf.
A book is said to be "privileged" if it is on a shelf with fewer books in the new arrangement than it was in the original arrangement.
Prove that there are at least k+1 privileged books in the rearranged library.
Well, in the original arrangement, there were at least k extra books besides the one per shelf. You know this because you are able to fill k more shelves without emptying any of the original shelves.
Those k extra books went from shelves with 2+ books to shelves with 1 book. Thus they are privelaged. The shelf they came off of has at least one privelaged book too; the ones that were left.
Originally posted by AThousandYoung Well, in the original arrangement, there were at least k extra books besides the one per shelf. You know this because you are able to fill k more shelves without emptying any of the original shelves.
Those k extra books went from shelves with 2+ books to shelves with 1 book. Thus they are privelaged. The shelf they came off of has at least one privelaged book too; the ones that were left.
Proven! Easier than I thought it would be.
Not proved at all...
You wrote "Those k extra books went from shelves with 2+ books to shelves with 1 book."
Why do you think that each book on the new k shelves is the only book on its shelf? Why do you think that on its original shelf there were at least 2 books?
Originally posted by David113 Not proved at all...
You wrote "Those k extra books went from shelves with 2+ books to shelves with 1 book."
Why do you think that each book on the new k shelves is the only book on its shelf? Why do you think that on its original shelf there were at least 2 books?
Why do you think that each book on the new k shelves is the only book on its shelf?
It doesn't matter whether it is or not, really, as long as each new shelf gets at least one book.
Why do you think that on its original shelf there were at least 2 books?
Because in the end arrangement all shelves have at least one book. You cannot remove books from a shelf with one book and still have at least one book on it.
Originally posted by AThousandYoung [b]Why do you think that each book on the new k shelves is the only book on its shelf?
It doesn't matter whether it is or not, really, as long as each new shelf gets at least one book.
Why do you think that on its original shelf there were at least 2 books?
Because in the end arrangement all shelves have at least one book. You cannot remove books from a shelf with one book and still have at least one book on it.[/b]
"It doesn't matter whether it is or not, really, as long as each new shelf gets at least one book" - prove it.
"Because in the end arrangement all shelves have at least one book. You cannot remove books from a shelf with one book and still have at least one book on it" - I can, because books from other shelves can be moved to that shelf.
Originally posted by David113 "It doesn't matter whether it is or not, really, as long as each new shelf gets at least one book" - prove it.
"Because in the end arrangement all shelves have at least one book. You cannot remove books from a shelf with one book and still have at least one book on it" - I can, because books from other shelves can be moved to that shelf.
I can, because books from other shelves can be moved to that shelf.
Since the books are indistinguishable from one another, and the shelves are indistinguishable from one another, and each shelf has at least one book before and after, any re-arranging of books as you describe is meaningless. You're "removal" of a book is just a re-arrangement, leaving that shelf with one book still.
Originally posted by AThousandYoung Well, in the original arrangement, there were at least k extra books besides the one per shelf. You know this because you are able to fill k more shelves without emptying any of the original shelves.
Those k extra books went from shelves with 2+ books to shelves with 1 book. Thus they are privelaged. The shelf they came off of has at least one privelaged book too; the ones that were left.
Proven! Easier than I thought it would be.
Yes, I also think this is enough. I think David just wants you to be explicit about the possibility of the k+1 priviliged books being the ones in shelfs that existed before. But, as you say, the ordering is irrelevant.
Rearranging is not meaningless. Suppose we have only 2 shelves. in state 1 we have 2 books on shelf A and one book on shelf B. We move some books around, and in state B we again have 2 books on shelf A and one book on shelf B (no new shelves were built). Can you tell the number of privileged books? No: it may be 0 or 1 (you don't know if the single book on shelf B was originally on A, in which case it is privileged, or not). So, rearranging can increase the number of privileged books. Why can't it decrease it, so in the original problem we'll have less than k+1 privileged books?
Originally posted by David113 Rearranging is not meaningless. Suppose we have only 2 shelves. in state 1 we have 2 books on shelf A and one book on shelf B. We move some books around, and in state B we again have 2 books on shelf A and one book on shelf B (no new shelves were built). Can you tell the number of privileged books? No: it may be 0 or 1 (you don't know if the single book on ...[text shortened]... y can't it decrease it, so in the original problem we'll have less than k+1 privileged books?
Because the rearranging that he's talking about is just between 'new' and 'old' shelves. In that case, it must be necessarily so that at least one book is priviliged, regardless of whether it's the one(s) in the new shelf or the one(s) in the old shelf.
The proof here is in the case where the minimum priviliged books are created, so cases where more priviliged books are created by the rearrangements that you describe are not important.
Originally posted by David113 Rearranging is not meaningless. Suppose we have only 2 shelves. in state 1 we have 2 books on shelf A and one book on shelf B. We move some books around, and in state B we again have 2 books on shelf A and one book on shelf B (no new shelves were built). Can you tell the number of privileged books? No: it may be 0 or 1 (you don't know if the single book on ...[text shortened]... y can't it decrease it, so in the original problem we'll have less than k+1 privileged books?
You may have a point, since there's no such thing as a "negatively privelaged book". But then you're not considering a case with NEW shelves. With NEW shelves, instead of moving from say a 2-1 state to a 1-2, with one privelaged and one "negatively privelaged", you're going from 2-1 to 1-1-1. No matter what you do there's no "negatively privelaged" books and therefore the ordering doesn't matter.
Originally posted by David113 Rearranging is not meaningless. Suppose we have only 2 shelves. in state 1 we have 2 books on shelf A and one book on shelf B. We move some books around, and in state B we again have 2 books on shelf A and one book on shelf B (no new shelves were built). Can you tell the number of privileged books? No: it may be 0 or 1 (you don't know if the single book on ...[text shortened]... y can't it decrease it, so in the original problem we'll have less than k+1 privileged books?
Let us call the books 1, 2 and 3.
Before, A had 1 and 2, B had 3.
After, we can have a few things:
A: 1, 2
B: 3
No privelaged books.
A: 1, 3
B: 2
2 is Privelaged, 3 is "negatively privelaged" which is ignored.
But let's add a new shelf: C. Now no matter what you do, you'll get two privelaged books.
In the library
23 Mar '08 19:22
Back to Top