Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Buried treasure

Ryan McGuire
Ranch Hand
Posts: 1085
4
A man with two sons knew he was dying. He also knew that his sons, George and Dick, didn't get along with each other and hadn't talked to each other in years. He devised a plan that would force the boys to work together if they wanted any of his money once he was gone.

He wrote a set of instructions:

He included a map with those seven landmarks highlighted.

Then what he did was cut the column (in italics in the instructions) out of the instructions and left it to Dick, and cut the column with the landmarks (in bold) and left it to George. (Both sons could see the rest of the instructions: "Start at ___, Go ___ of the way from there to ___, Go ___ of the way from there to ___, etc.")

He knew (and knew Dick knew) that there are 7! or over 5000 ways the seven landmarks could be ordered, and digging an average of 2500 holes to find the "treasure" would be unfeasible. He also knew (and knew George knew) that without the fractions, George would just be wondering around aimlessly.

He figured his sons HAD to work together if they wanted the money. He was wrong. Which one of the sons was able to dig a single hole and get the money for himself without the help of his brother? How/why?

Ranch Hand
Posts: 245
Originally posted by Ryan McGuire:

He knew (and knew Dick knew) that there are 7! or over 5000 ways the seven landmarks could be ordered, and digging an average of 2500 holes to find the "treasure" would be unfeasible.

Not true.

Reordering of the landmarks will not change the final location so Dick can get it without knowing the order of landmarks.

Ryan McGuire
Ranch Hand
Posts: 1085
4
Ok, apparently this this was a little too easy.

Stefan Wagner
Ranch Hand
Posts: 1923
I am surprised, and wouldn't found it out by myself.

Ryan McGuire
Ranch Hand
Posts: 1085
4
Originally posted by Stefan Wagner:
I am surprised, and wouldn't found it out by myself.

Let me pose this followup:

WHERE is the treasure? What's the easiest way to locate it, given the map of landmarks?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
The term "centroid" comes to mind...

Ryan McGuire
Ranch Hand
Posts: 1085
4
Originally posted by Jim Yingst:
The term "centroid" comes to mind...

Are you just guessing or are you trying to convince us you arrived at that logically/mathematically?

Besides, (now that I've looked it up, I see) there are a couple different "centroids" you could use. Which one is best here?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I was trying to post an indication that I'd arrived at the correct answer already - not by guessing. It was intended to be a hint which was obvious in retrospect without completely giving the game away to those who hadn't gotten there yet. Much as you'd requested that Vlado avoid giving an answer immediately.

(Σx / N, Σy / N ), if you prefer.
[ May 02, 2006: Message edited by: Jim Yingst ]

Myke Enriq
Ranch Hand
Posts: 115
Centroids have nothing to do with it.

It does not work, and for some guy to read on wikipedia abotu centroids and to claim here that he is samrt and that this problem is easy , whithout ever giving any proof to his centroid ideea - is just plain imature.

Question 1: I took a piece of paper and drew 3 dots and tried to see if walking like in the problem gives the same result no matter what the order of the 3 dots is: IT DID NOT WORK.

Question 2: the guy that claimed any centroid is the solution (place to digg) to this problem: WHERE IS YOUR PROOF ? I mean , the greeks figured out 3000 years ago that you cannot simply state the answer to a question , you must prove it meaning give arguments on why it is so. Yet you come here writing a few words and claiming this is an easy problem.
Please prove that "any" (or at least one type of your choosing) centroid is the place to digg to get the money in this problem.

Matthew Brown
Bartender
Posts: 4568
9
Question (3) Why get so confrontational about a 6 year-old thread? Especially when the poster explained why he hadn't given a proof.

However, since you want a proof, try this. Using vectors, let's say the landmarks are at b, t, m, d, g, w, n:

Start at b.
Step 1: x1 = b + (t - b)/2
Step 2: x2 = x1 + (m - x1)/3
Step 3: x3 = x2 + (d - x2)/4
Step 4: x4 = x3 + (g - x3)/5
Step 5: x5 = x4 + (w - x4)/6
Step 6: x6 = x5 + (n - x5)/7

So the final location is:
n/7 + 6/7(w/6 + 5/6(g/5 + 4/5(d/4 + 3/4(m/3 + 2/3(t/2 + b/2)))))

Reduces (because lots of the fractions cancel) to:
(n + w + g + d + m + t + b)/7,

which is the centroid. And it's symmetric, so the ordering of the landmarks has no effect. And typing that up was much slower than solving it!

Matthew Brown
Bartender
Posts: 4568
9
Or, if you prefer proof by induction...(and here I really wish the formatting abilities of the forum were greater )

Given a sequence of points x_1, x_2, ...

Let's say we are at the centroid of the first n points: C_n = 1/n . SUM{i = 1, n}[x_i]
We then move 1/(n + 1) of the distance towards x_(n+1)

New position = C_n + 1/(n+1) . [x_(n+1) - C_n]
= n/(n+1) . C_n + 1/(n+1) . x_(n+1)
= 1/(n+1) . SUM{i = 1, n}[x_i] + 1/(n+1) . x_(n+1)
= 1/(n+1) . SUM{i = 1, n+1}[x_i]
= C_(n+1)

The case n = 1 is trivial - the centroid of one point is that point. After that, each step takes us to the centroid of all points considered so far.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
But Matthew, didn't you hear? Centroids have nothing to do with it. IT DID NOT WORK!

Based on Myke's obvious respect for the traditions of Plato and Pythagoras, I'm sure a detailed proof of this will be forthcoming. It was probably just overlooked in the rush.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Oh, and Matthew, thanks for showing the proof.

Ryan McGuire
Ranch Hand
Posts: 1085
4
• 1
Myke Enriq wrote:Centroids have nothing to do with it.

It does not work, and for some guy to read on wikipedia abotu centroids and to claim here that he is samrt and that this problem is easy , whithout ever giving any proof to his centroid ideea - is just plain imature.

Question 1: I took a piece of paper and drew 3 dots and tried to see if walking like in the problem gives the same result no matter what the order of the 3 dots is: IT DID NOT WORK.

Question 2: the guy that claimed any centroid is the solution (place to digg) to this problem: WHERE IS YOUR PROOF ? I mean , the greeks figured out 3000 years ago that you cannot simply state the answer to a question , you must prove it meaning give arguments on why it is so. Yet you come here writing a few words and claiming this is an easy problem.
Please prove that "any" (or at least one type of your choosing) centroid is the place to digg to get the money in this problem.

Myke,
You were able to disprove the "centroid" answer with a three-location counter-example? Can you provide a drawing of your example or at least a description of it? It seems to work just fine for the handful of triangle I tried. For instance...

With these three points, we end up at the same place regardless of whether the points are ordered A-B-C or C-A-B in the instructions. I worked out the other four possibilities for these three points as well and came up with the same final destination each time.

For the case of three points, the picture should like something like what's producible with the Java applet located here. The points that are labelled D,E and F on that page are the intermediate locations after the "Go half way from the first point to the second" step in the original instructions. If then go one third of the way from one of those side bisectors to the other triangle vertex, you should always end up at the point that's labelled centroid.

However, if you have a diagram that illustrates a different result I'd be interested in seeing it.

Myke Enriq
Ranch Hand
Posts: 115
sorry guys , I misunderstood the question. I assumed that given 3 points A, B and C you go from A to B , then B to C then again from C to A.

Anyways , nice demonstration with the vectors Mathew.