23 Mar 08
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.
23 Mar 08
Originally posted by David113Well, 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.
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.
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.
23 Mar 08
1 edit
Originally posted by AThousandYoungNot proved at all...
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.
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?
24 Mar 08
Originally posted by David113Why do you think that each book on the new k shelves is the only book on its shelf?
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?
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.
24 Mar 08
Originally posted by AThousandYoung"It doesn't matter whether it is or not, really, as long as each new shelf gets at least one book" - prove it.
[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]
"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.
26 Mar 08
2 edits
Originally posted by David113I can, because books from other shelves can be moved to that shelf.
"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.
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.
26 Mar 08
Originally posted by AThousandYoungYes, 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.
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.
26 Mar 08
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?
26 Mar 08
2 edits
Originally posted by David113Because 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.
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?
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.
05 Apr 08
1 edit
Originally posted by David113You 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.
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?
05 Apr 08
Originally posted by David113Let us call the books 1, 2 and 3.
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?
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.