Wikipedia:Reference desk/Archives/Mathematics/2010 December 4

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 4

Card shuffling problem

A deck of cards is numbered 1 through 10 and shuffled. Then, the top card is turned up and inserted into the position that it's numbered. This is repeated until the 1 is drawn, at which point the deck won't change. What's the expected number of draws before the 1 is drawn? I've realized that once the 10 is drawn, the deck effectively becomes a 9-card deck because the 10 won't move anymore, so I was thinking something with recursion might work, but I'm not sure where to go from there. --70.134.49.69 (talk) 02:46, 4 December 2010 (UTC)

If the starting order is 2 3 4 5 6 7 8 9 10 1 then it will take 511 draws before you get the 1. So I'm thinking there may not be a easily computed solution.--RDBury (talk) 09:30, 4 December 2010 (UTC)

With only 10 cards, it's easy to do a brute-force calculation on a computer. If I didn't make a mistake, the average number of draws over all 10! permutations is 108986116/10!, or about 30.03. The 2 3 4 5 6 7 8 9 10 1 order mentioned by the previous respondent seems to take the most draws of all. 86.173.36.60 (talk) 13:42, 4 December 2010 (UTC).

My program said the same when the draw of 1 is not counted. I'm not sure whether the poster intended this with "number of draws before the 1 is drawn". PrimeHunter (talk) 05:06, 5 December 2010 (UTC)

further damaging the worst sort

I heard about a sort of n things like this: Throw them up in the air so they get shuffled, collect them, see if they are in order, and repeat from the start if they are not.

Is there any sort worse than this? (but which still eventually does succeed) 82.98.48.252 (talk) 15:19, 4 December 2010 (UTC)

If you want an algorithm with a running time worse than f(n), you could have the algorithm do f(n) steps of nothing before sorting the n things. Aenar (talk) 17:36, 4 December 2010 (UTC)

The algorithm you're describing is called Bogosort. Take a look at the paper Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. —Bkell (talk) 18:27, 4 December 2010 (UTC)

Abiogenesis must have started with a bogosort - perhaps that explains why only one example of life has been found so far. 92.15.23.156 (talk) 19:41, 4 December 2010 (UTC)

Also, Pessimal Algorithms and Simplexity Analysis. Quote: "Of course, we can get very slow algorithms by adding spurious loops…. However, such easy solutions are unacceptable because any fool can see that the algorithm is just wasting time. Therefore, we must look for an algorithm that does indeed progress steadily towards its stated goal even though it may have very little enthusiasm for (or even a manifest aversion to) actually getting there." —Bkell (talk) 18:29, 4 December 2010 (UTC)

More links: Multiply and Surrender (the "opposite" of Divide and Conquer]; Inefficient sort algorithms. —Bkell (talk) 18:34, 4 December 2010 (UTC)

Do you request an algorithm that is slow for all values of n? The above algorithm is fast for n=0 and n=1. Just sort the file by a fast method and hold the result to ransom. Bo Jacoby (talk) 17:34, 5 December 2010 (UTC).

As a programmer, I once encountered a horrid sort in actual use. This particular program gave the choice of listing the contents of a file either in ascending or descending order. Ascending order was plenty fast, it just read the file in sequential order and displayed it. But descending order was abysmally slow. I eventually figured out that it was reading every line in the file, displaying the last one, then reading every line in the file, displaying the second to last line, etc. The result ? A 10,000 line file, displayed in reverse order, required 100 million reads.

So, excess I/O was the culprit here, in the form of reads, but also I've seen excess print statements, such as debug info for every comparison, in the heart of a sort, taking an otherwise decent sort down.

Another problem could be copying the entire sort array to a new array every time a change is made. This might have a legitimate purpose in that it preserves the history of the sort, again for debugging. Certain implementations of recursive programming can also have this affect, unintentionally. And copying arrays gets far worse once you use up memory and go to paging space, so be sure to reserve huge chunks of memory for each array. Also use dynamic memory allocation, as that, combined with fragmented memory, can result in data being moved all over the place.

One other comment, "random" can be done in a good way or a bad way. Once you randomly select an element, say the 5th one, to put first in the test array, what happens if the next random selection, to go 2nd in the test array, is again the 5th element ? A smart implementation would prevent you from hitting numbers which have already been processed, a moderate one would just try again when this happens, a bad one would toss this trial out and start the whole process over again, and a dismal one would abort the entire program and start over from scratch.

So, if you combined all these strategies, you'd make the bogosort many orders of magnitude worse, but still avoid just wasting time with code that does nothing at all. StuRat (talk) 07:02, 6 December 2010 (UTC)

This challenge reminds me of my high school programming class. We eventually figured out that students with longer programs got better grades, regardless of their efficiency. At that point, the challenge was on to find the most inefficient way to accomplish a given task, without it being so obvious that the teacher would catch on. StuRat (talk) 07:24, 6 December 2010 (UTC)

Easy to use time-series or forecasting software

I'm not a mathematician but I would like to 'play' with some time series. I'd like for example to correlate lagged time series. Is there any suitable software that would be quick and easy to learn? I'm aware of R, but that seems to require a lot of study to use. I'd also be thrilled to find something that can do ARIMA forecasts automatically. The commercial software that can do this is very expensive, so I'm looking for something open source, freeware, or similar. I have tried searching on Google in the past but doing that does not tell you what's easy to use or if some new little-known software is available. Thanks. 92.15.23.156 (talk) 19:38, 4 December 2010 (UTC)

Fixed-length rope between two posts

This is not homework but a practical problem with the context re-written to make it easier to explain. There is a wooden post several feet distant from a straight riverbank. About a hundred feet or so further up the river there is another wooden post fixed in the bed of the river, also some feet distance from the bank (not the same distance). I have a rope that is tied at both ends to the two posts. The rope is somewhat longer than the shortest distance between the two posts.

I want to have as little of the rope over the water as possible. How can I calculate where the rope should cross the river bank?

The "one-hundred feet" is just used to give a rough idea of the proportions involved. I can easily measure the perpendicular distances from the the posts to the riverbank, but the distance along the riverbank between the two posts and the length of the rope are much more difficult to measure. The rope will of course be two straight lines between the posts and the point where it crosses the river bank. The rope is not long enough to make the river portion of it perpendicular to the river bank. Thanks 92.15.23.156 (talk) 21:21, 4 December 2010 (UTC)

If the ground post is s (shore) from the bank, the river post is r (river) from the bank, the length of rope is D, and the length of bank between the posts is d: let x and y be the length of bank covered by the two segments and X and Y be the total length of those segments. We have $x+y=d$ and $X+Y=D$, and the Pythagorean theorem gives us $X={\sqrt {r^{2}+x^{2}}}$, $Y={\sqrt {s^{2}+y^{2}}}$, so we have ${\sqrt {r^{2}+x^{2}}}+{\sqrt {s^{2}+(d-x)^{2}}}=D$, thence $r^{2}+x^{2}+s^{2}+(d-x)^{2}+{\sqrt {(r^{2}+x^{2})(s^{2}+(d-x)^{2})}}=D^{2}$, and so $(r^{2}+x^{2})(s^{2}+(d-x)^{2})={\bigl (}D^{2}-r^{2}-x^{2}-s^{2}-(d-x)^{2}{\bigr )}^{2}$. This is a quartic equation in x which can in principle be directly solved by radicals, but that's not terribly practical; I would just plot the function with your values for s, r, d, and D and look for zero crossings. You want the one at smaller x; the other is where you have the most rope over the water. As for knowing d and D only approximately: I'm afraid this problem is pretty sensitive to them when they're much larger than r or s as you said. In the real world, you can always tie it to the posts and then walk along the bank toward the river post (letting it slip through your hands) until both ends go taut. --Tardis (talk) 03:18, 5 December 2010 (UTC)

Thanks, I've got some figures. The first post is 175 perpendicularly in from the river bank. The second post is 90 from the river bank. The distance along the river bank between the two posts is 1360. The rope is 1370 long. I'll come back and try to get Wolfram to plot that. 92.15.31.223 (talk) 18:17, 5 December 2010 (UTC)

In Tardis' notation you have $s=175,\ r=90,\ d=1360,\ D=1370$. Unless I'm missing something, the length of the rope is less than the distance between the posts, which is ${\sqrt {d^{2}+(s+r)^{2}}}\approx 1385.58$, so it cannot connect them. -- Meni Rosenfeld (talk) 18:44, 5 December 2010 (UTC)

Thanks, I have another arrangement. The first post is 175 from the bank. The second post is in the river 775 from the bank. The distance between the posts (I mean the distance between where perpendicular lines from the posts cross the bank) is 670. The rope is 1370 again. I calculate the straight line distance as about 1024, so there is some slack this time. 92.15.31.223 (talk) 19:01, 5 December 2010 (UTC)

Ok, so you can give this to Wolfram Alpha and not only will it plot it, it will give you the solutions and you can click on "approximate form" to get numerical results. You can also substitute other values there. Just make sure to check that the solution makes sense.

By the way, the straight line distance is 1162.5. -- Meni Rosenfeld (talk) 19:20, 5 December 2010 (UTC)

Sorry, I should have typed that the second post is 600 from the riverbank. The graph using that figure gives me a negative figure or 900 - so the rope would cross the riverbank further away than the river post, and then come back? 92.15.31.223 (talk) 19:36, 5 December 2010 (UTC)

If there is a solution for x<0, then the rope is long enough to go straight from the in-river post to the bank (as short as it could ever be) and still have slack between there and the on-shore post. The math doesn't give you x=0 then because it doesn't allow the rope to go slack. --Tardis (talk) 20:03, 5 December 2010 (UTC)