Wikipedia:Reference desk/Archives/Mathematics/2008 July 6

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.

July 6

search for the lost treasure

Care for a challenge? Describe the mathematical principles you can use to solve this puzzle. http://members.optusnet.com.au/~ksiew/puzzle01.png

Captain Flint had to hurriedly secrete a treasure on a lonely island. No time for maps. There were 3 trees forming a triangle; a beech nearest the waters edge and an oak on either side. Said the captain to Long John: "Stretch a rope from the beech to this first oak and then pace a distance inland from the oak at right angles (90 degrees) to the rope, and equal to the ropes length. That will be our point No 1. You, Silver, do the same at the other oak. Stretch a rope from beech to oak and walk a distance inland from the oak at right angles (90 degrees) to the rope and equal to its length. Good. That's our point No 2. Now, boys, we will bury the treasure half-way between our two points. Okay, cut away the ropes and off to the boats. Let's go."

Six months later, Long John, accompanied by the cabin boy, stole back to the island to double-cross the gang and swipe the treasure. He knew the scheme but, sad to relate, the beech that had been the reference point had been completely washed away in a storm and only the oaks remained. Long John was crestfallen. But by great good luck the cabin boy was none other than our Euclid smith. "Don't worry John, cried Euclid. "I will find you the treasure without the beech." And, he did in a jiffy. How? 122.107.171.82 (talk) 11:11, 6 July 2008 (UTC)

I'm guessing that the locus of the point produced by randomly guessing where the beech is in invariant with the position of the beech.. It certainly looks like you get the same point no matter where you guess the beech is.. as for a proof (see overleaf).87.102.86.73 (talk) 12:08, 6 July 2008 (UTC)

It's easy enough to demonstrate this with a little vector arithmetic. It helps to choose an appropriate coordinate system of course -- setting the position of one oak at (0,0) and the other at (0,1), and letting the beech be at (-x,y) is a decent choice. From there you just calculate the required vectors to follow the directions (needing little more than "vector between two points" and "vector perpendicular to" as operations) and arrive that the point (in terms of x and y) where the treasure is located. The fact that this point is independent of x and y gives you your answer. -- Leland McInnes (talk) 18:15, 6 July 2008 (UTC)

finding the simplexorate of a function

I need to find the simplexorate of a function but I've forgotten how to do it (is there even a general method?), and Google is not cooperating. Anyone know?

p.s. if you don't know don't feel the need to tell me, this isn't undergrad stuff.

thanks. —Preceding unsigned comment added by 90.44.43.163 (talk) 15:16, 6 July 2008 (UTC)

Maybe people don't want you to know.. I find it unusual to say the least that google simply refuses to even recognse the term ie "http://www.google.com/search?hl=en&q=simplexorate". Watch out!87.102.86.73 (talk) 16:06, 6 July 2008 (UTC)

Google, Yahoo, Wikipedia, and JSTOR don't recognize it. The term doesn't exist, isn't spelled that way, or is so specialized that there aren't any papers on it. Can you describe what it's supposed to do, or at least what field it's in? Black Carrot (talk) 01:23, 7 July 2008 (UTC)

Does it means to carry out a simple XOR operation, presumably on a test string and a key string?…86.132.234.130 (talk) 19:51, 7 July 2008 (UTC)

Homeomorphism

I have a dumb question. Say f: Circle --> segment and segment looks like [a,b) . Now choose a point on the circle, x, and let f(x)=a and then just define f such that as you move around the circle you move towards b. Why does this fail to be a homeomorphism? I know the spaces are not homeomorphic because when you remove a point in the circle it remains connected and the same is not true for the segment. Is the function above not continuous? Why? Thanks, Brusegadi (talk) 16:16, 6 July 2008 (UTC)

I’m not too confident about the following argument, so somebody might want to check me on it. But viewing the segment in the induced topology, the set $[a,\varepsilon )$ is an open set, but it’s image on the circle is not an open set. Thus $f^{-1}$ is not continuous, and so your map is not a homeomorphism. GromXXVII (talk) 16:27, 6 July 2008 (UTC)

Almost. It's *pre*image on the circle is not open, so *f* (not f inverse) is not continuous. --Tango (talk) 17:38, 6 July 2008 (UTC)

Just to make this a bit more concrete: we can look at the function $f$ that assigns to a point $z$ on the unit circle in the plane the angle $\theta =f(z)$ that the line segment $[0,z]$ makes with the $x$ axis. In other words, $\theta$ is the number in $[0,2\pi )$ such that $z=(\cos \theta ,\sin \theta )$. Now, this $f$ is not continous at the point $f^{-1}(0)=(1,0)$ for the reason GromXXVII indicated, and so $f$ is not a homeomorphism. (However, $f^{-1}$ is continuous.) Oded (talk) 17:13, 6 July 2008 (UTC)

Thank you all. I get it now. Brusegadi (talk) 07:51, 7 July 2008 (UTC)

Actually, you don't need to go into much complication; the circle is compact whereas the interval [a,b) is not. If you want to see a proof of why the circle is not homeomorphic to [a,b] for a < b, then please see my next post.

Topology Expert (talk) 01:48, 9 July 2008 (UTC)

You may find the following result interesting (which shows that the circle in the plane is not homeomorphic to an open interval in R):

If f is a continuous map from the circle to the set of all real numbers, then f(x) = f(-x) for some x on the circle (-x is an antipodal point of x)

Proof

Let g(x) = f(x) - f(-x) which is continuous since f(x) is continuous. Note that g(x) > 0 for all x is impossible for otherwise:

f(x) > f(-x)

f(-x) > f(x)

which is absurd. Similarly, g(x) < 0 for all x is impossible. Therefore, by the intermediate value theorem and the connectedness of the circle, g(x) = 0 for some x. It follows that f(x) = f(-x) for some x.

Corollary

The set of all real numbers is not homeomorphic to the circle.

By a similar proof, you can show that the circle is not homeomorphic to any closed interval in the set of all real numbers.

I hope this helps.

Topology Expert (talk) 01:48, 9 July 2008 (UTC)

md5

Does anyone know of a discovered string such that it is its own md5 hash? —Preceding unsigned comment added by Froth (talk • contribs) 17:45, 6 July 2008

I seriously doubt it. While there's better than a 60% chance that such a thing exists (see derangement), it should be almost impossible to find; if it's not, then that represents a flaw in MD5's cryptographic security. --Trovatore (talk) 19:01, 6 July 2008 (UTC)

Is anything known about the cycle structure of md5? I mean, take a random string a0, and set a(n+1)=md5(a(n)). If for some N, some k, and all n > N, a(n+k)=a(n), then call k a period of md5 starting at a0, and let the order of md5 on a0 be the smallest period k. Is k usually absurdly large? Are examples known with k fairly small? JackSchmidt (talk) 20:22, 7 July 2008 (UTC)

So for the actual MD5, I'm not aware of any work that's been done along these lines (not to say that I necessarily would be aware of it). But we can easily do a rough order-of-magnitude probabilistic analysis of what the answers should be, if MD5 has the properties that it "ought" to have as a good cryptographic hash.

Basically the sequence of iterated MD5 values ought to look, for most purposes, like a random sequence of 128-bit strings. Of course we know that once the sequence repeats, then it has to continue repeating with the same period, but I think that will have at most a minor influence on the probabilities.

So by reasoning along the lines of the birthday paradox, the chance that there will be a repetition starts to become significant once the length of the sequence gets to be a significant fraction of the square root of the number of possible strings, so around 2⁶⁴ in terms of order of magnitude. Of course the first repetition may not repeat the first string of the sequence, it could be any string along the way, but that just diminishes what you expect k to be by a factor of 2 or so, so it's still that order of magnitude, around 10¹⁹ or so as a conservative estimate.

So while it's not impossible that the NSA has machines that could grind this out, at least if they happened to get very lucky and hit a repetition a bit earlier than one would expect, I kind of doubt that they would use them for this, as there's no clear benefit from getting a hit. Of course if you hit a repetition much earlier than expected, say after only a million iterations or something, that would have disturbing implications for the security of MD5, but it's not immediately clear what you would do with that information. --Trovatore (talk) 08:35, 8 July 2008 (UTC)