Author |
Topic: Bogosort (Read 1061 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
A normal pack of 52 playing cards is to be sorted into a particular order using Bogosort. Let S(n) be the probability that Bogosort correctly sorts the deck in n shuffles or less. Seeing as S(n) is a monotonically increasing function which converges to 1, derive an estimate for the smallest value of n for which S(n) exceeds 0.95, say.
|
| « Last Edit: May 30th, 2011, 7:11am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Bogosort
« Reply #1 on: May 30th, 2011, 9:18am » |
 Quote  Modify
|
I'd say n is about 3*52!
because n=52! should give about 1/e probability that it's not been sorted yet.
|
| « Last Edit: May 30th, 2011, 9:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Bogosort
« Reply #2 on: May 30th, 2011, 9:55am » |
Quote Modify
|
To be precise, replace 3 by ln(0.05)/ln(1/e) = 2.9957.
You get n = 2.4163E+68.
Uh... subtract one if you check the order already before the first shuffle. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Bogosort
« Reply #3 on: May 30th, 2011, 10:40am » |
Quote Modify
|
The approximation is already 290525338444092531665930133786805491212286891737748022440* off, so I wouldn't worry about that extra 1 too much.
* which isn't too bad on a number like 241630298485567771500540396514677414298531351035230182511744601484973; it's accurate to about 1 in 1012
|
| « Last Edit: May 30th, 2011, 10:44am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Bogosort
« Reply #4 on: May 31st, 2011, 1:57am » |
Quote Modify
|
Yeah.... That's why I added a "".
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Bogosort
« Reply #5 on: May 31st, 2011, 2:48am » |
Quote Modify
|
Of course, many readers will not understand why your smart asswers are correct (1/e?) and hate maths even more. 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Bogosort
« Reply #6 on: May 31st, 2011, 9:07am » |
Quote Modify
|
If it makes them resentful rather than curious, then, frankly, they're already beyond help.
But if they are curious, then they'd probably be best helped by asking about any parts they don't understand, in as far as the following doesn't cover it.
There are 52! possible permutations of the cards, and only one gives the right order. So with each reshuffle there is a probability of (52!-1)/52! that the cards are still out of order. Since the shuffles are independent, we can multiply them together, which gives us a probability of [(52!-1)/52!]n that after n shuffles the deck has never once been in the right order.
At this point it's helpful to know that if we consider ([k-1]/k)k, then as k grows it's value comes ever closer to 1/e (~= 0.36787944). Because 52! is a very large number, for all practical purposes we can assume that [(52!-1)/52!]52! equals 1/e. This simplifies things, because now we just need to solve 1/er = 0.05, which gives r = ln(0.05)/ln(1/e) = -ln(0.05) ~= 2.9957 and so we can say n~=2.9957*52!
|
| « Last Edit: May 31st, 2011, 9:10am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print