|
|
Go to page 1~2 [Next] | ||||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Ok, Stan solved the last puzzle in a blink of an eye. I guess I gotta give him a bigger challenge...
so here goes: a drunken librarian (named Conan) had really too much alcohol one night. he really would like to order the shelf holding the encyclopedia in the library. - the encyclopedia has n volumes numbered 1..n - the shelf has n places numbered 1..n - after the busy day all readers left all volumes on the shelf in a totally random order - the drunken librarian takes a book which is not in place (choice is random since he is drunk) from the shelf and places it in its correct place (i.e. book k goes to place k)- shoving all the books to its left or right to make room the question is, using this algorithm, will the drunken librarian ever finish his task or can he stay there forever. give an example if this doesn't work. please help Conan the Librarian... N.D. p.s. hope this keeps some of you busy through the holiday... |
|||||||||
stanalger Special user St. Louis, MO 998 Posts |
Anyone get anywhere with this one?
The problem is easy to understand...and I'm guessing that there's an elegant way of showing that Conan will always eventually be successful. But I dunno.... |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I'm still pondering it every now and then. It's a great puzzle so I hope Nir don't think that he needs to post the solution.
/Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Thanks for bumping this puzzle...
this is to subside the future bashing - I am sure that my "solution" will not stand a mathematical rigorous analysis, but I am convinced it is correct. I will post it when the guys here give up. hints can be given via PM N |
|||||||||
The Mighty Fool Inner circle I feel like a big-top tent having 2140 Posts |
CROM!!!!
Everybody wants to beleive.....we just help them along.
|
|||||||||
TomasB Inner circle Sweden 1144 Posts |
BUMP!!!!
|
|||||||||
leonard Regular user North Carolina 148 Posts |
I may be missing something, but here goes. Exhaustive analysis of the 3 (or 4) volume cases shows that the task always finishes.
Using this fact, and simple induction on the number of volumes, seems to solve the general case. If Conan ever selects volume 1 or n, that volume: 1. goes into its correct position, 2. never moves again, and 3. reduces the remaining problem by 1. What did I miss? leonard |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Since it's random, you can't assume that he ever picks any of the end books.
The "simple induction" you need to show. If it works for N books, why is it so certain that it works for N+1 books? It probably is, but why? /Tomas |
|||||||||
leonard Regular user North Carolina 148 Posts |
Tomas,
If it's random, can't I assume that he "eventually" picks every book? And eventually finishes the task? leonard |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Nope. You have to prove that he can't get stuck in a loop, if he happens to pick the same books over and over and they just keep shifting back and forth. In fact, if you can show a single loop like that, you have proven that it's not certain he ever finishes.
/Tomas |
|||||||||
C.J. Inner circle There's a lotta rambling in my 2366 Posts |
The system cannot get caught in an infinite loop because:
a) A book that sits in the correct position will no longer move (eg Book k is in position K. Conan randomly grabs book k, but has to put it back exactly where it was. None of the other books are moved left or right). AND b) With totally random selection, Conan will eventually select either/both book 1 and book n. Therefore, wouldn't it make sense that as he selects books that sit at the extremes, the order will eventually sort itself from the edges to the middle? Even if we just considered working left-to-right, wouldn't it be a matter of waiting for book 1 to be picked, then since it can never move, waiting for book 2 to be picked, then 3, then...n? As far as I can tell, this is what Leonard said above. What is missing?
Connor Jacobs - The Thought Sculptor
Mundus vult decipi, ergo decipiatur Be fondly remembered. |
|||||||||
leonard Regular user North Carolina 148 Posts |
C.J.
I am with you, but am now stuck on what I can assume about the randomness of the selection. If book #1 is in position #1, and Conan constantly selects it, he will make no progress. That seems like a one book "loop" to me. I terms of our common thinking about a solution, I believe you have to work from either one or both ends. I don't think having a random book #k in (non-end) position #k insures it will stay in that position. A book from its right could be put in correct position to its left, moving book #k to position #k+1. Other than this, I am still trying to decide what I am missing in the problem statement. leonard |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
C.J. your a) statement is not true. Imagine that you have picked book 45, then you pick 85 (which was to the right of it) to place that into position. Then you happen to pick book 23 which unfortunately is to the right of 85. Now there is a vacancy there so when you put 23 in the correct place, 45 moves to position 46 and 85 moves to position 86. So you have corrected one, but lost at least two.
/Tomas |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I just saw that you had missed one instruction: "the drunken librarian takes a book which is not in place" so he can't pick the same book immediately, but if the next move moves this correctly positioned book out of position it can be picked again.
/Tomas |
|||||||||
C.J. Inner circle There's a lotta rambling in my 2366 Posts |
Quote:
On 2013-05-25 14:10, TomasB wrote: Ah, this is true. So what I posted was poorly worded, but my solution works, because in time, Conan will move book #1, and then that book cannot ever move again to the right. Then, in time with random selections, he will pick book #2, which (because #1 cannot move out of place according to the rules of not picking correctly-placed books) will never move out of place. Then book #3... up to book #n.
Connor Jacobs - The Thought Sculptor
Mundus vult decipi, ergo decipiatur Be fondly remembered. |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Can he stay there forever? I think that implies that you can not assume he ever picks a certain book. Especially since I think there is a solution not demanding that.
/Tomas |
|||||||||
owen.daniel Inner circle England 1048 Posts |
Quote:
On 2013-05-24 16:17, leonard wrote: Quote:
On 2013-05-25 03:09, TomasB wrote: Just my two cents on this. There is some truth in both of these claims (i.e. that the book will definitely be selected eventually / it could never be selected). According to a result in probability, Kolmogorov's Zero-One Law, if we assume that in each step the book he chooses is independent of all the previous choices, then almost surely (i.e. with probability 1) he will eventually choose any given book. Note that this does not depend on the actual way he chooses the books... i.e. the distribution. By this I mean that he may have a bias to choose books with his right hand, and so tend to take more of the high numbers... but so long as he sometimes chooses low numbers, he'll eventually choose any number. It is, however, clear that we are to suppose that he is choosing the books uniformly. Here is the rub, whilst we know that he'll eventually pick book N (which then allows us to use Leonard's inductive strategy), we do not know how long it'll take before that happens... And in fact the time could be unboundedly far away... but it still happens! And then we have to wait an unbounded amount of time till he picks book N-1 (or 1), etc. Ultimately, so long as the encyclopedia is finite, he will eventually order it, but we cannot bound the amount of time that it will take before this happens... So ultimately the question needs some clarification as to what is meant by doing it in finite time. As a side note, Kolmogorov's Zero-One law enables a non-inductive proof as well. Suppose that Conan is so drunk that even once all of the books are in order, he still keeps ordering them (which equates to picking a random book, and putting it back in its same place). Now consider the probability that at some point he picks book N, then book N-1, then book N-2,... down to book 1. Clearly if he does this sequence the books are in order. Kolmogorov's Zero-One law asserts that he will in fact eventually pick the books in exactly that sequence, and so we are done. Owen PS. For those who know something about random walks and more generally Markov chains, the original question is somewhat similar to asking whether a random walk is transient or recurrent. And my additional question about bounded/unbounded times is analogous to positive recurrence or null recurrence. To make Tomas (and the librarian) happy it would be necessary for this process to be positive recurrent, to make Leonard happy null recurrence suffices. |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Maybe it's clearer if it's rephrased: Given n, is there an upper limit to the number of moves it takes to sort the books?
I've always thought of that as the question, to make it non-trivial. I'm pretty sure there is such a limit, but I have not been able to prove it. /Tomas |
|||||||||
owen.daniel Inner circle England 1048 Posts |
Hi Tomas,
This is really the question of null vs positive recurrence. As we have established, he will eventually manage to order them. There is no 'deterministic' bound on the length of time that it takes him, since as you've already noted, he could cycle between certain choices which don't lead him to the original order, by which I mean for any number M > 0, I can come up with a sequence of M book choices such that after those choices, they are still not in order. Therefore the sensible measure of whether it happens in finite time is whether or not the expected number of choices is finite or infinite. If it is finite we say that the process is positive recurrent, if it is infinite the process is null recurrent. In fact, it occurred to me after my post that the question is completely solved by Markov process analysis. This question is an example of a finite state space, irreducible Markov chain, and as such is known from general theory to be positive recurrent... so this then answers your question: yes, he almost surely rearranges them in finite time. A much harder question is, how long on average will it take him. This is an interesting problem, and again a solution can be obtained from solving a system of simultaneous equations... This is fine for small values of n, however actually setting up the system of equations for large n is very difficult (at least the way I have approached it), and in particular the number of possible configurations grows like n!, so calculations explode easily. On a side note, calculating the expected time till he reorders the books has a curious relationship with a seemingly unrelated problem: the heat equation! The heat equation describes how heat dissipates through a material, and is (somewhat unsurprisingly) one of the most studied problems in mathematics. It turns out that the type of functions that satisfy the heat equation are also the kind of functions that describe the expected time for a Markov chain to hit a certain value... which is the problem addressed in this puzzle. Regards Owen |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
"since as you've already noted, he could cycle between certain choices which don't lead him to the original order"
I just noted that _if_ we can find such a sequence there can be no upper bound. I'm pretty sure there are _no_ such sequences. Can you show one? I've been trying to find one. /Tomas |
|||||||||
The Magic Cafe Forum Index » » Puzzle me this... » » Conan the (drunken) librarian (0 Likes) | ||||||||||
Go to page 1~2 [Next] |
[ Top of Page ] |
All content & postings Copyright © 2001-2024 Steve Brooks. All Rights Reserved. This page was created in 0.04 seconds requiring 5 database queries. |
The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement < |