Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

Post a reply

Go back

Write your message and submit
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool: | :dizzy :eek :kiss :roflol :rolleyes :shame :down :up :touched :sleep :wave :swear :tongue :what :faint :dunno
Options

Go back

Topic review (newest first)

gAr
2013-09-04 04:20:13

Another version, slightly faster (8 sec)

Code:

sim=:3 : 0
((>./)-(<./))(?3$0)
)
(+/%#) (%3)>((sim "0) 1000000$0)
gAr
2013-09-04 02:14:51

Hi bobbym,

It was about 8.7 seconds for a million iterations.

bobbym
2013-09-04 01:21:04

Hi gAr;

Very nice. What was the running time?

gAr
2013-09-04 01:03:51

Hi,

J simulation:

Code:

   sim=:monad define
a=. ?3$0
(>./a)-(<./a)
)

(+/%#)(%3)>(sim&+) 1000000$0

≈0.259516

bobbym
2011-12-11 19:23:23

Okay, see you tomorrow.

gAr
2011-12-11 17:15:54

Okay.
But not now, I guess!
So I bookmarked it.

bobbym
2011-12-11 17:08:11

Thanks gAr, I appreciate you saying that. You will understand it or quickly find the hole in it.
One way or another will be good.

Sorry, there was a big typo right on the end that I fixed up. I have pi on the brain.

gAr
2011-12-11 17:02:30

Hi bobbym,

Looks interesting.
I'll try to understand!

bobbym
2011-12-11 15:49:51

Always another way - The Keymaker

Since this is a thread devoted to computer math programs let's see how mathematica can be used to solve the problem experimentally.

Supposing we treat this as a discrete problem rather than a continuous one. If we examine what happens at discrete intervals between 0 and 1 and then subdivide those intervals we could view the process as a limit as the intervals approach zero.

If we start with the set {0,1/3,2/3,1} we see that there is no way to pick 3 from it that the minimum is less than 1/3. The same holds for increments of 1,1/2,1/4 and 1/5.

The first solutions occur when we start with the set {0,1/6,2/6,3/6,4/6,5/6,1}. Using combinatorics or direct count we see that there are 5 solutions, they are:



We can form a table of n subdivisions and solutions:



The table means that if we have the set, {0,1/20,2/20,3/20,...1} there are 245 ways.

A finite set with 21 elements representing points on the number line is a poor substitute for the unit interval with its infinite number of points. We need a relationship between the solutions and n. We ask mathematica to find one. It comes up with the following difference equation:



We run the recurrence in the forward direction to get n = 2 000 000.

The number of ways to pick three from the 2 000 001 points is 345677975308901235.

The probability is:



This only disagrees with 7 / 27  by less than .00000077, so we are on the right track.

Can we do better? We could, if we could solve that recurrence but it will not even fit on a piece of paper.
We need a trick.

Let's study the solutions again starting at 6.



It is well behaved at 7 and 8 and then takes a big jump at 9. Well behaved again at 10 and 11 and then another big jump. This disproportionate jump occurs at every third one. Let's see if we can understand it.

The first tool to understanding any sequence is a difference table. Old timers like Newton,Leibniz, Gauss, Euler, Legendre and Lagrange lived off of them. They are much less used and understood today. Let's form a difference table of every third one.









That is what we want a last line of constant differences. That means there is a
polynomial fit for every third entry in the table. Now we find that polynomial.



So you see hiding inside the major sequence was another smaller pattern. One much easier to deal with. This is sometimes the case with recurrences and you should look for it.

Now to finish up. The more points we use in the interval 0 to 1, the closer we approximate the continuous unit interval. We will use the calculus to get an infinite number of them.

The probability of drawing three numbers from the unit interval with the maximum - minimum < 1/3 is:



And we are done!

bobbym
2011-12-10 18:00:26

bob bundy wrote:

Now I just need a brain transplant, and I might understand what you're doing here.

The only way you will understand what I have done there is if you buy my brain. It is on auction on ebay for 19.95. I had it removed right before I wrote  post #1.

I could have been a contender.

The sad truth about the above tremendous solution is that it is only true for one set of numbers. Any attempt to generalize that method to any other number of points and any other distance fails miserably.

What are the odds of it only working on the one set of numbers that the question contained? Should I feel incredibly lucky or unlucky?

When I found that solution I thought it was my ticket to fame. The IAS here I come. Instead all I got was a one way ticket to Palookaville, to quote Brando.

So I strongly urge you do not try to get a brain transplant and especially not mine.

bob bundy
2011-12-10 06:40:28

hi bobbym,

Arhh, that's better.  I can see it now.

Now I just need a brain transplant, and I might understand what you're doing here.  dunno

Bob

bobbym
2011-12-09 19:36:26

Hi Bob;

It is miniscule, I can not see it at all. I am working on it, please hold on.

Fixed!

Hope that is visible on all browsers.

It is today now and very cold!

bob bundy
2011-12-09 19:32:33

Good morning bobbym,

How are you today?  Or is it still yesterday where you are?

A diagram for this problem would be great.

Unfortunately, my eyesight isn't that good.  Any chance you could make it a bit bigger?

Thanks,

Bob

bobbym
2011-12-09 19:24:24

This question popped up in another thread. The question was well answered by TheDude over there so the only purpose of this post is to show that a nice neat drawing can provide much insight into solving a problem.

Three numbers are chosen at random between 0 and 1. What is the probability that the greatest minus the least is less than 1/3.

The expected value of the maximum point out of 3 points is 3 / 4 but that is not important. I placed the maximum there, just as a start. Figure 2.

The circle that is tangent to that point represents where the other two points must fall. Where the circle intersects the line shows the interval on the line. If the minimum point is in the interval so must the other point be. Refer to figure 2.

It is obvious that there is a



chance of one point getting in the interval. For two points to get in,



For anywhere we place a point, p the probability of the other two getting within the interval is,



When the maximum is at 1 / 3 or less, figure 1, then the probability that both points will be inside it is 1 this can happen 1 / 27 = ( 1/3 *1 / 3 *1/3 )of the time. We hold on to this number.

Since we want the probability for any point p that the two points ( one will be the minimum ) will be inside the interval we just have to sum for all the points p. This is done by integration.



So the answer is 7 / 27 which agrees with simulations.

Drawings done with geogebra and screen captor.

Board footer

Powered by FluxBB