Six Villages
Math brain teasers require computations to solve.
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?
HintTo find the number of routes, start from the son's village and move to the farthest away village or crossing from the bride's village he could travel to that hasn't been visited. Record the number of routes to this village or crossing. Keep repeating this, marking the number of routes to each village or crossing along the path until reaching his destination.
Hide
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 BF. 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 leftside 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:
ABABiCCiCDiDiD
and the mirror route
AFFAiEEiDEiDiD
(ABiC is the same as ABiBiBCiC)
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 AB is then 5/Pi miles. The path BD bisects the path CM, so both CCi and DiD are half the radius. AB + CCi + DiD is then equal to the diameter 10/Pi.
The paths BABi, ABiBCi, and BCiC are all sides of equilateral triangles with a height of one half of the radius. The paths CiCDi and CDiDi 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
Hide
Comments
javaguru
Feb 14, 2009
 OK, I made a significant mistake on the answer to the bonus question.
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 
stil
Mar 04, 2009
 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. 
javaguru
Mar 04, 2009
 OK. I was trying to keep the prose consistent with tropicalislandvillagespeak 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" ).
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. 
stil
Mar 06, 2009
 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. 
EntangledQuark
Mar 11, 2009
 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!
Although it's not an easy teaser, I don't think it's as hard as the rating suggests. 
bigpat
May 07, 2009
 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 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 logicgrid 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
BigPat 
morgoth1028
Aug 20, 2009
 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 
TheBrainBender
Sep 04, 2009
 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?? 
weizhong
Sep 13, 2009
 This is one of the hardest brain teasers I've ever seen. I get confused just looking at the explanation. 
kunk
Jun 25, 2010
 Has noone 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 () and used GNumeric. Everything said Jul 31. I am not forgetting anything, am I? The first 2 sons are correct though. 
javaguru
Jul 08, 2010
 @ 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. 
braingle100
Mar 31, 2011
 This is the hardest teaser on Braingle! 
soninlaw
May 01, 2011
 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? 
Alexi
Jun 25, 2012
 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 triplewedding the next day.
BAM 
PositivaPatrik
Sep 10, 2012
 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/myimages/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. 
javaguru
Nov 01, 2012
 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! 
Lord_Hawk
Nov 10, 2012
 Very good teaser =) I thought ABABiBiMCiCDiDiD 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? 
twainsbrain
Aug 06, 2013
 i...didnt even bother to read this one. too long and im tired. ima go sleep! sorry! 
Jatinsharma
Jun 26, 2014
 Nice problem to solve 
njasmus
Jul 08, 2014
 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. 
Back to Top
 
