wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Yet Another Spider&Fly Problem II
(Message started by: Barukh on Dec 23rd, 2004, 11:33pm)

Title: Yet Another Spider&Fly Problem II
Post by Barukh on Dec 23rd, 2004, 11:33pm
Continuing the S&F saga...

This is a variation of the problem (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1102868484), started by Jock.

In a room 1 x 1 x 2 meters, the spider is at one of the corners.

Where should the fly position itself to be as far from the spider as possible?

Title: Re: Yet Another Spider&Fly Problem II
Post by JocK on Jan 2nd, 2005, 11:28am

on 12/23/04 at 23:33:32, Barukh wrote:
In a room 1 x 1 x 2 meters, the spider is at one of the corners.

Where should the fly position itself to be as far from the spider as possible?


:: [hide]The fly has to position itself somewhere on the opposite 1x1 wall (corners included), as all positions not on the opposite wall are closer to the spider than the opposite corner.

Furthermore, symmetry tells the fly on the 1x1 wall to restrict itself to the diagonal through the corner opposite the spider.

For positions on this line, the 'helical path' corresponds to a square distance of (2+x)[sup2]+(1+1-x)[sup2], and the 'single kink' path to (2+1-x)[sup2]+(1-x)[sup2]. For 0 < x < 1, both functions are monotonic (one decreasing, the other increasing). A clever fly will therefore seek a position for which the 'helical' distance and the 'single kink' distance coincide. This happens for x = 1/4, halfway between the opposite corner and the centre of the 1x1 wall.[/hide] ::

A follow-up question:

For what room length L (room measures 1 x 1 x L) can the fly choose between more than one maximum distance position? (The spider is still in a corner)

Title: Re: Yet Another Spider&Fly Problem II
Post by Barukh on Jan 3rd, 2005, 2:35am
Nicely done, Jock. The only thing that I am not satisfied with is the following statement:


on 01/02/05 at 11:28:52, JocK wrote:
Furthermore, symmetry tells the fly on the 1x1 wall to restrict itself to the diagonal through the corner opposite the spider.

Don’t you agree that this assumption is valid only in case there is a single maximum point? But this is far from being obvious.

What do we do with this?

Title: Re: Yet Another Spider&Fly Problem II
Post by JocK on Jan 3rd, 2005, 3:05am

on 01/03/05 at 02:35:38, Barukh wrote:
Don’t you agree that this assumption is valid only in case there is a single maximum point? But this is far from being obvious.


You are right:

Consider the 1 x 1 x 2 box with the spider in a corner. The plane through the spider-corner cutting the opposite 1 x 1 plane diagonally is a symmetry plane. Either the maximum distance solution(s) are located on this symmetry plane, or these optimal solution(s) come in pairs that constitute 'mirror images' in the symmetry plane. Intuitively I would not expect the latter to be the case, but can't prove it.

If you want a rigorous mathematical proof I suggest we move this problem to the 'hard' category.. ;D

Title: Re: Yet Another Spider&Fly Problem II
Post by Barukh on Jan 4th, 2005, 9:52am

on 01/03/05 at 03:05:46, JocK wrote:
If you want a rigorous mathematical proof I suggest we move this problem to the 'hard' category.. ;D

Let’s try it here…  ;D

In the attached drawing, S is the spider, and F is the fly. 4 instances of F correspond to 4 different paths from S to F. The drawing also clearly shows why the fly should position itself at the opposite 1x1 face in order to be farther from the spider. In particular, the points satisfying the condition of the problem, are those where all 4 instances of F lie outside the dashed circle.

Let x, y be the distances of the fly from the sides of the face, as depicted. Pick any positive number c [le] 2 and consider all the points on the line x+y = c. We want to show that, among all the points on this line, the point x = y = c/2 is farthest from S.

Refering to the drawing, the squares of the 4 distances from S to F are (from top to bottom):

D1(x) = (2+x)2 + (2-c+x)2,
D2(x) = (3-c+x)2 + (1-x)2,
D3(x) = (3-x)2 + (1-c+x)2,
D4(x) = (2+c-x)2 + (2-x)2,

and we want to maximize D(x) = min(D1(x), …, D4(x)).

Note that D4(c-x) = D1(x), D3(c-x) = D2(x), therefore D(x) = D(c-x). Moreover, D1(x), D2(x) are monotonically increasing, while D3(x), D4(x) are monotonically decreasing, therefore maxx D(x) = D(c/2), which is to be shown.

Does it look OK?  :-/


Title: Re: Yet Another Spider&Fly Problem II
Post by JocK on Jan 4th, 2005, 11:00am

on 01/04/05 at 09:52:40, Barukh wrote:
Does it look OK?  :-/


Nice!

Now you're ready for the above-posed follow-up question...  ;D



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board