Braingle Lite



Six Villages

Category:Math
Submitted By:javaguru
Fun:*** (2.38)
Difficulty:**** (3.46)



There are six villages along the coast of the only perfectly round island in the known universe. The villages are evenly distributed along the coastline so that the distance between any two neighboring coastal villages is always the same. There is an absolutely straight path through the jungle connecting every pair of villages. These paths create thirteen crossings in the interior of the island, one of which is in the middle of the island where paths from every village meet.

The island has a strange courtship custom. Before a father will give permission for his daughter to marry, her suitor must bring the father a fish each day until he has traveled by every route from his village to the father's village. The young man only travels along routes where he is always getting closer to his destination. The young man may visit other villages along the way.

On April first a father's three sons come to tell him of their intent to woe a bride, each from a different village. The brides' villages are the first three villages encountered when traveling clockwise around the island.

If the sons begin their courtship today and the couples are married on the day following each son's last trip, what are the three wedding dates?

Bonus Question: If the coastline of the island is ten miles long, how long is the longest route that any of the sons takes to reach their betrothed's village?

Answer:

The wedding dates are April 6th, May 12th, and August 1st.
Bonus question: ~ 6.86 miles.


All villages are crossings. Here are the steps to determine the number of routes to reach any point:

1) First set the starting point to one.
2) Select the unvisited crossing that is adjacent to a visited crossing and is closer to the destination, but which is the farthest such unvisited crossing from the destination.
3) Set this crossing to the sum of the values for all of the adjacent visited crossings. (If you do this in the correct order, all the adjacent visited crossings are farther from the destination.)
4) If the last selected crossing is not the destination then continue with step two.

Which points are closer or farther from the destination can be determined using the right triangles formed by the intersecting paths. The shortest path from a point to a line is perpendicular to the line. Moving toward the right angle formed by the path and the line is moving closer to the point; moving away from this right angle is moving farther from the point.

Note that when moving from a village to the opposite village that all of the crossings to the left of the direct path between the villages are symmetrical with the corresponding crossing to the right.


The routes:

This is a little hard to follow without a diagram, so you might want to create one. The diagram is a regular hexagon with lines connecting each pair of vertices. There are three intersections created along each of these connecting lines, with the three lines connecting opposite vertices meeting in the middle. Label one vertex A and moving clockwise, label the remaining vertices B-F. Label the middle intersection M. Label the intersection along the path from A to M (path AM) as Ai; label the similar intersections for the remaining vertices as Bi to Fi. Label the intersection of paths AC and BF as ABi. Label the similar intersections BCi, CDi, DEi, EFi and FAi.


Routes to an adjacent village (A to B):

To determine the routes from A to B first set A to 1.
The farthest point from B that is closer than A and adjacent to A is Ai. Ai can only be reached from A, so set Ai to 1.
The next farthest point is ABi. ABi can be reached from A and Ai so set ABi to 1+1=2.
The next farthest point is Bi. Bi can only be reached from ABi, so set Bi to 2.
The next farthest point is the destination B. B can be reached from A, ABi and Bi, so set B to 1+2+2=5.

There are five routes to an adjacent village, so that son will make his last trip on April 5th and the wedding will be the next day on April 6th.


Routes to the second village along the coast (A to C):

A = 1
AFi = A = 1
Fi = AFi = 1
Ai = A + AFi = 2
ABi = Ai + A = 3
M and B are equidistant from C, so in either order:
M = Ai + Fi = 3
B = A + ABi = 4
Bi and Di are equidistant from C, so in either order:
Bi = B + ABi + M = 10
Di = M = 3
BCi and CDi are equidistant from C, so in either order:
BCi = B + Bi = 14
CDi = Di = 3
Ci = BCi + CDi + M = 20
C = B + BCi + CDi + Ci = 41

There are 41 routes from A to C, so that son will make his last trip on May 11th and the wedding will be the next day on May 12th.


Routes to the opposite village (A to D):

Since the intersections to the left and right of the direct path are mirrors, the left-side calculation is assigned to both.
A = 1
F, B = A = 1
FAi, ABi = A + B = 2
Ai = A + ABi + FAi = 5
Fi, Bi = ABi + B = 3
EFi, BCi = B + Bi = 4
M, C and E are equidistant from D, so in any order:
M = Ai + Fi + Bi = 11
E, C = B + BCi = 5
Ei, Ci = BCi + M + C = 20
DEi, CDi = C + Ci = 25
Di = M + CDi + DEi = 61
D = C + E + CDi + DEi + Di = 121

There are 121 routes from A to D, so that son will make his last trip on July 31st and the wedding will be the next day on August 1st.


Bonus Question:

The longest route is a route to the opposite village. Given the above diagram, the longest routes the son will have to travel from A to D is:

A-B-ABi-C-Ci-CDi-Di-D

and the mirror route

A-F-FAi-E-Ei-DEi-Di-D

(ABi-C is the same as ABi-Bi-BCi-C)

If the circumference is 10 miles then the diameter is 10/Pi miles and the radius is 5/Pi miles. Since a regular hexagon is formed from six equilateral triangles, the length of a side of the hexagon is equal to its radius.

The path A-B is then 5/Pi miles. The path B-D bisects the path C-M, so both C-Ci and Di-D are half the radius. A-B + C-Ci + Di-D is then equal to the diameter 10/Pi.

The paths B-ABi, ABi-BCi, and BCi-C are all sides of equilateral triangles with a height of one half of the radius. The paths Ci-CDi and CDi-Di are each half of the side of one of these same triangles. The side of one of these equilateral triangles is

5/(sqrt(3)*Pi)

So the total distance traveled is

10/Pi + 4*(5/(sqrt(3)*Pi)) = 10/Pi + 20/(sqrt(3)*Pi) ~ 6.86 miles

Show Hint Hide Answer



Comments on this teaser


Posted by javaguru02/14/09
OK, I made a significant mistake on the answer to the bonus question. :oops: A side of the smaller equilateral triangle is not 5*sqrt(5)/2Pi. It is 5/(sqrt(3)*Pi). This makes the longest path 10/Pi + 20/(sqrt(3)*Pi) ~ 6.86 miles

Posted by stil03/04/09
Dear javaguru- You've mixed your use of route and path. The puzzle is a confusion until one realizes the boy is travelling all routes which with every step take him closer to the girl's village. I initially figured the boy would take just enough routes to use every acceptable path or path fragment at least once.

Posted by javaguru03/04/09
OK. I was trying to keep the prose consistent with tropical-island-village-speak and "route" didn't seem like the term they'd use, but I can see how "path" can be misinterpreted. When I saw you had posted a message here I was assuming it was to point out the error in the answer. There is a mistake in the assignment of values in the longest path (sorry, "route" :wink: ). M = Ai + EFi + BCi = 13 There is no path from EFi or BCi to M. The value for M should instead be: M = Ai + Fi + Bi = 11 Once you propagate the correct value for M through the rest of the routes you end up with 121 routes, not 131. This gives a wedding date of August 1st. At the speed that teaser corrections get approved, the fix for this and the error in the bonus question and the wording change for "route" should make it into the teaser by Christmas. :-?

Posted by stil03/06/09
The hint and the solution have us record, mark, or set a number by villages and crossings. This charts the number of ways a point can be reached. The number of ways to reach a point is equal to the sum of the numbers of ways in which adjacent points which are visitable but more distant (and hence already scored) can be reached. The only way to be at the first village, the point most distant from the goal, is to live there; score 1. There is only way to reach the second most distant village or intersection, so it always scores 1. The sum/score grows when more than one of a point's immediate neighbors has a score to contribute to the sum. The number of permissible routes is the sum at the goal.

Posted by EntangledQuark03/11/09
I really liked this teaser. At first it seemed difficult, then it seemed tedious, but once I figured out the pattern to solving it, it was just plain fun! :D Although it's not an easy teaser, I don't think it's as hard as the rating suggests.

Posted by bigpat05/07/09
javaguru, thank you for taking the time to come up with and post these amazing teasers. I was one of the few people that actually liked math in school :P and I'm very glad to have a place where I can maintain (and possibly increase) my math skills. I havn't been on braingle long, but so far the best workout my brain has gotten, and therefore the most fun I've had, is working on your math teasers. I currently have a logic-grid teaser pending and one more to be submitted soon, but I want to try my hand at making a good math puzzle. So be on the lookout for one from me 8) -BigPat

Posted by morgoth102808/20/09
Ok after reading the teaser I decided it was way above my head, but who in their right mind has time to come up with this and write it all out!? I mean Come on! get a life! lol great job tho

Posted by TheBrainBender09/04/09
Isn't there anyone her who isn't completely stufedd from the first paragraph of the answer??? How bothered must you be to make that teaser??

Posted by weizhong09/13/09
This is one of the hardest brain teasers I've ever seen. I get confused just looking at the explanation. :D

Posted by kunk06/25/10
Has no-one else noticed? I think there is a mistake in the answer for the third son (the one whose bride is in the third village along the coastline (directly across) from his home village). I first only looked at the date in the answer which says Aug 1. I was getting Jul 31 and could not figure out where my mistake was. Then I checked further down the number of days - 121. I have that too so the problem must be incorrect adding of 121 days to Apr 1 either in the answer or on my side. I tried various ways, asked my mother (:D) and used GNumeric. Everything said Jul 31. I am not forgetting anything, am I? The first 2 sons are correct though.

Posted by javaguru07/08/10
@ kunk: You are correct, the answer should be July 31. If you want to submit the correction you may. If you don't in the next week or so I will.

Posted by braingle10003/31/11
This is the hardest teaser on Braingle! :o

Posted by soninlaw05/01/11
hi there, just to clarify, so travelling from A to B, one wouldn't head towards B in the opposite direction along the coast? ie.leave A towards F, then to village E, to D, to C, then to B? Or,from A, walk towards FAi, then turn towards F at the intersection, then back towards Fi, then, EFi, etc. and so on and so forth?

Posted by Alexi06/25/12
By my Logic, the weddings can all be 'tomorrow' (April 2) if the sons take a very fast mode of transport. - it says they must 'travel' doesn't specify on foot, or how long travelling any specific route takes. each son completes all the possible path's to the village (heading directly back to home village between each) in one day and chucks the old man a Fish then heads home for their triple-wedding the next day. BAM

Posted by PositivaPatrik09/10/12
Interesting problem. Some programmers will recognize this as dynamic programming. I also wanted to add that you can also do the computation in reverse. Meaning that you begin with the village you are traveling to. The rule for choosing the next vertex (crossing) will then be to choose the one closest to any of the one already calculated. The reason this makes more sense in a way is that you will get all three answers at ones. An image of what I mean http://imageshack.us /photo/my-images/854 /6villages.jpg/ (For some reason you cant have words longer than 50 letters so the link has got two spaces in it) Note that in this image. You are traveling towards A and the numbers at the crossings denote how many ways this can be done in from that point.

Posted by javaguru11/01/12
Excellent observation Patrick! That's exactly what I like to do when solving puzzles: find a simpler or more elegant means of solving it. Good job! :D

Posted by Lord_Hawk11/10/12
Very good teaser =) I thought A-B-ABi-Bi-M-Ci-CDi-Di-D was the longest path, but on calculating the length of your path, I found mine lacked by ((2/sqrt(3)) - 1)r... Do you have a proof to show that your path is indeed the longest?

Posted by twainsbrain08/06/13
i...didnt even bother to read this one. too long and im tired. ima go sleep! sorry! :oops: :( :o :roll: :-? :oops:

Posted by Jatinsharma06/26/14
Nice problem to solve

Posted by njasmus07/08/14
I used the same approach as PositivaPatrik. The only difference is that I considered D to be my farthest destination rather than A. I will admit that I'm concerned that a father would have three sons that would want to cause woe to their intended brides, rather than woo their brides.

Posted by xdbtcp12/02/14
There are no weddings, they were all playing April Fools jokes (you did say April 1, right?) :roll:




Search:
Browse:

Most Popular | Hardest | Easiest




Privacy | Terms
Copyright © 2003