wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> NEW PROBLEM: Mean distance
        
(Message started by: Ulkesh on Aug 14^th, 2002, 9:56am)

Title: NEW PROBLEM: Mean distance
Post by Ulkesh on Aug 14^th, 2002, 9:56am

I got this one from one of my maths lecturers. I lack the mathematical tools to solve it unfortunately, but maybe some of you will derive some enjoyment from it...

Problem:

What is the mean distance between two random points on a unit square?

(Basically, the question is asking for the mean distance between all sets of random pairs of points on aforementioned unit square.)

Hmm... I'm sure it could be worded better, if any of you don't understand I'll try to clarify.

If the unit square proves too easy, how about an equilateral triagle of side 1? An arbitrary 2D shape? An arbitrary 3D shape such as a tetrahedron? An arbitrary n-dimensional shape?

Aren't the best problems always the simplest at face value? ;)

Title: Re: NEW PROBLEM: Mean distance
Post by S. Owen on Aug 14^th, 2002, 1:40pm

I wonder if one can solve this by relating it to the Buffon's needle problem (the one where you drop needles of a certain length onto a grid and see how many land across a grid line)?

That is I wonder if we can equate these two things:
* the proportion of randomly selected segments in the unit square that have length <= L, and
* the proportion of segments with randomly chosen endpoint and fixed length L that are contained within the unit square

Thinkin' about it...

Title: Re: NEW PROBLEM: Mean distance
Post by tim on Aug 14^th, 2002, 11:53pm

I can do it by brute-force integration. I'm now looking to see if there's a more elegant way to arrive at the solution. It seems that there should be one.

Ulkesh: Any shape can be integrated, but a more complicated shape might rule an elegant solution :)

Title: Re: NEW PROBLEM: Mean distance
Post by tim on Aug 15^th, 2002, 3:31am

I now doubt that there is any elegant solution.

After actually doing the brute-force integration across 2 sheets of paper, double-checking it in Mathematica, and triple-checking with a numerical simulation, the answer is
(Sqrt[2] + 2)/15 + Log[Sqrt[2] + 1]/3
with a numerical value of about 0.52140543.

I would be fairly surprised if anyone could get this answer via some sort of symmetry considerations.

Title: Re: NEW PROBLEM: Mean distance
Post by Ulkesh on Aug 15^th, 2002, 4:28am

Well done Tim; 0.52 sounds in the right ball park intuitively.

I'm curious though. What exactly are you integrating to begin with, and where do you get this integral from? From a 1st year UG standpoint, a mean distance between 2 random points seems a fairly abstract thing to be able to apply an integral to. Presumably, the 2 pages of brute-forcing involve a lot of substitution... maybe I'll try that myself.

It's also a shame if there is no elegant solution. Perhaps the integration will end up being simpler on different shapes, yielding more of an elegant integation ;)

Title: Re: NEW PROBLEM: Mean distance
Post by Eric Yeh on Aug 15^th, 2002, 5:43am

Just integrate over four variables: sqrt((x1-x2)^2+(y1-y2)^2)dx1dx2dy1dy2 each from 0 to 1. That was my first thought as well but I didn't like the inegration so I skipped it. :D

Title: Re: NEW PROBLEM: Mean distance
Post by S. Owen on Aug 15^th, 2002, 12:34pm

on 08/15/02 at 03:31:03, tim wrote:

After actually doing the brute-force integration across 2 sheets of paper, double-checking it in Mathematica, and triple-checking with a numerical simulation, the answer is
(Sqrt[2] + 2)/15 + Log[Sqrt[2] + 1]/3
with a numerical value of about 0.52140543.

BTW this is consistent with the value I got by running a simulation, excellent work.