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

        riddles >> easy >> Snail Trail
        
(Message started by: rloginunix on May 7th, 2015, 7:25pm)
Title: Snail Trail
Post by rloginunix on May 7th, 2015, 7:25pm
Snail Trail

Apologies if my drawing skills are not up to snuff but the sketch below is supposed to depict a right square prism made of glass with its dimensions shown:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_st.png

1). What is the shortest trail the snail can trail from the point A to the point F?

2). To which point on the surface of the prism will the snail trail the longest?
Title: Re: Snail Trail
Post by alien2 on May 8th, 2015, 2:00am
1. The shortest trail is [hide]a straight line if the snail moves on my LCD screen.[/hide]
Title: Re: Snail Trail
Post by SMQ on May 8th, 2015, 5:53am
1) There are essentially two possible path to consider for the shortest route: [hide]from point A, cross edge BC at its midpoint then continue to point F[/hide] or [hide]from point A, cross edge CD 1/3 of the way from point C then continue to point F[/hide].  All other potentially-shortest paths are reflections or reversals of these two. By looking at the [hide]mesh of the prism[/hide], we find that the first way has length [hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(202 + (10 + 10)2) = 20http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2[/hide], while the second way has length [hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(102 + (10 + 20)2) = 10http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif10[/hide] which is slightly longer, thus the first route is the shortest possible.

--SMQ
Title: Re: Snail Trail
Post by rloginunix on May 8th, 2015, 7:53am
Alien's statement contains a key to solving this problem but before it can be employed a certain [hide]transformation[/hide] must be applied to the prism - an observation picked up by SMQ - you are correct on number one, [hide]20http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2[/hide] is it.


A hint for number two: [hide]SMQ's analysis of number one[/hide].
Title: Re: Snail Trail
Post by SMQ on May 8th, 2015, 8:50am
2) First, a sanity check: by [hide]arranging meshes on top of one another and plotting the arcs at 20http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 from each point A ([/hide][hide]http://dwarfrune.com/smq/wu/SnailTrailMesh1.png[/hide] (http://dwarfrune.com/smq/wu/SnailTrailMesh1.png)[hide])[/hide], we see that there is indeed a small area of points (a dart-shaped region to near point F) farther away from point A than point F is, no matter the chosen path.

Next, to find the furthest path, we assign a coordinate system: let point F be at (0,0).  From symmetry we know that the furthest point must lie [hide]on segment FD[/hide] and be equidistant from [hide]all projections of point A ([/hide][hide]http://dwarfrune.com/smq/wu/SnailTrailMesh2.png[/hide] (http://dwarfrune.com/smq/wu/SnailTrailMesh2.png)[hide])[/hide].  Thus we're searching for a point [hide](x,x)[/hide] such that [hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif((20 + x)2 + (20 - x)2)[/hide] = [hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif((10 - x)2 + (30 - x)2)[/hide]. Squaring both sides, and simplifying gives [hide]80x = 200 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bigleftrightarrow.gifx = 5/2 = 2.5[/hide].

Thus the point on the prism farthest from point A is [hide]1/4 of the way along segment FD from point F[/hide].

--SMQ

edit: fixed bad image URL
Title: Re: Snail Trail
Post by rloginunix on May 8th, 2015, 6:43pm
A beautiful solution beautifully arranged. Nothing to add, nothing to take away.


One thing if you do not mind - I use GeoGebra for the geometric constructions. What is your choice? Thanks in advance.
Title: Re: Snail Trail
Post by pex on May 8th, 2015, 8:40pm
If I may add:
3). Which two points are furthest from each other using this metric?
Title: Re: Snail Trail
Post by SMQ on May 9th, 2015, 3:45am
@rloginunix: I've never gotten around to installing dedicated geometry software, so I generally use whatever is handy. Usually either MS Word, as above, or if programming is already involved, FreeBasic which is still my goto language for get-pixels-on-the-screen type problems. :)

@pex: my first hypothesis is [hide]the centers of the square faces which are 30 units apart[/hide], but I haven't attempted a formal analysis yet.

--SMQ
Title: Re: Snail Trail
Post by pex on May 9th, 2015, 4:14am

on 05/09/15 at 03:45:58, SMQ wrote:
my first hypothesis is [hide]the centers of the square faces which are 30 units apart[/hide], but I haven't attempted a formal analysis yet.

That was what my intuition told me too - but it appears that this is not the case!

I haven't attempted a complete formal analysis either, but I have found two points that are slightly further apart, satisfy a similar sort of optimality condition as in your analysis of problem 2, and are not improved upon by some quick numerical optimization attempts.
Title: Re: Snail Trail
Post by rloginunix on May 9th, 2015, 11:26am
Awesome minimax idea, pex - two snails! At which points on the surface of the prism must two snails be placed so that they trail towards each other the longest? Let's do it.

There are two basically different paths from A to F: via one or two faces. A path via one face was tested and eliminated in 1) but here in 3) we have to consider it:

A bird's eye view of all the one-face trails (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_general;action=display;num=1396709569;start=125#138)

(the drawing came out too big so I truncated its top portion but you get the idea)

The analysis of 1) and 2) tells us that the two points sought-after should be placed somewhere on the bottom and top faces of the prism. Let us assume that a point on the ABEH (bottom) face is X with coordinates (a, b) counting from A (a along AB, b along AH) and that a point on the DCFG (top) face is Y with coordinates (c, d) counting from F (c along FG, d along FC). Let us then put down the lengths of all the possible paths:

[hide]P21 = (10 - a - c)2 + (30 + b - d)2
P22 = (10 - b - d)2 + (30 - a + c)2
P23 = (10 - a - c)2 + (30 - b + d)2
P24 = (10 - b - d)2 + (30 - a + c)2[/hide]

We see that the paths P1 and P3 have the first terms identical. Omitting the squares, their second terms however differ by 2*(b - d). Therefore the lengths of these two paths differ the more b and d differ where one variable grows while the other one diminishes. However, we want to find such values of these variables when all the paths are long enough. So if we assume that b and d are different we can replace them with their half-sum (b + d)/2 in which case the smaller of P1 and P3 will grow and the larger will diminish but P2 and P4 will remain the same - their terms that depend on b and d are the same. Therefore we can take it that b == d and P1 == P3.

By similar reasoning we can take it that a == c and P2 == P4.

Now let us compare P1 and P2. For which b and a, say, P1 < P2:

[hide]P21,3(b=d, a=c) = (10 - 2a)2 + 302
P22,4(b=d, a=c) = (10 - 2b)2 + 302
(10 - 2a)2 + 302 < (10 - 2b)2 + 302
a > b[/hide]

Therefore it is equally long to trail from X to Y if a == b which means that X and Y should be placed on the diagonals of their faces. In that case the length of the path via one face is:

[hide]P2(one-face) = (10 - 2a)2 + 302 = 4a2 - 40a + 1000[/hide]

a horns up parabola. Its first derivative is 8a - 40 so its minimum is at a = 5. Which means that the farther X an Y from the centers of their faces or the closer X and Y to A and F respectively - the longer the corresponding trail.

What remains to do next is to analyze the two-face trail. Derive the length of its path and compare it to the one above.
Title: Re: Snail Trail
Post by rloginunix on May 9th, 2015, 11:51am
Since SMQ did all this nice work let me shamelessly, khm, borrow it - from SMQ's last drawing we quickly conclude that the length of the two-face diagonal to diagonal path is:

[hide]P2(two-face) = (20 - 2x)2 + (20 + 2x)2[/hide]

Equating the lengths of two paths we get (setting a = x in my one-face formula):

[hide]8x2 + 800 = 4x2 - 40x + 1000[/hide]
[hide]4x2 + 40x - 200 = 0[/hide]
[hide]x2 + 10x - 50 = 0[/hide]
[hide]x = 5(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(3) - 1)[/hide]

Therefore the square of the length of this path is:

[hide]400(4 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(3))[/hide]

I went a bit too fast, may be I erred somewhere but that's the number I get.
Title: Re: Snail Trail
Post by pex on May 9th, 2015, 6:02pm

on 05/09/15 at 11:51:06, rloginunix wrote:
Therefore the square of the length of this path is [hide]400(4 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(3))[/hide]
I went a bit too fast, may be I erred somewhere but that's the number I get.

Well done - at least, I get the same number. Please see the attachment for a drawing of all six paths of equal length.
Title: Re: Snail Trail
Post by rloginunix on May 10th, 2015, 9:30am
Then I think it must be it. On their respective faces the two points sought-after are situated on the [hide]diagonals and are symmetrical about the center of the cuboid[/hide]. They are offset from the corresponding vertexes by [hide]3.66[/hide] units along the edges and the actual length of the path is [hide]30.1194[/hide] units - just a smidgen north of the first hunch 30-unit center to center length. But I guess for a snail even that counts ...

Nice visualization of the trails.


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