CL. Some Number of Numbers Sum
Niclas Hedell gives his solution to the third tree puzzle he posed last week, and we ask a puzzle about sums of numbers.
Here is the diagram we promised showing how Niclas’ solution works.
First off is my solution: one can easily use the rope to find the midpoint between the two trees, then use one end of the rope as a compass to trace out a circle as shown. Any tree on this circle will form a right triangle with the two original trees
Niclas kindly pointed out there may not be any such tree!
The Swedish military intended this solution, which may be quite an ancient trick: fold the rope into eighths and form a 3:4:5 triangle as shown. Sighting down the leg of length 3, we can find a third tree.
As elegant as this is, we have not accounted for the width of the trees, which may be substantial in a real forest. Niclas’ solution is to construct, with a little effort, an isoceles triangle as shown at left below…
… and, after marking the apex of the triangle, untie one end of the rope and pull it straight out. Voila! A right triangle!
(But what geometrical mission was the Swedish military up to?)
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Vrungel said,
May 15, 2007 at 10:25 am
Another way (in addition to first solution above) would be a bit more complicated
dance and find perpendiculars to the line between two give trees at the both
points. Any tree along those perpendiculars will do as well.
To find perpendicular for one of two given trees you could draw two circles
form both trees using for example 1/4 the rope from one tree and 3/4 the rope
from another they will intersect in one place then draw two more circles of the
same radius, say 1/2 rope, from that intersection and middle point. The line
between those intersections created by those circles will pass through one of
the given trees, the one you drew 1/4 rope first circle from, and will be
perpendicular to the line between given trees. You can do the same for another
given tree.
iNic said,
May 15, 2007 at 8:19 pm
Yes that is a possible solution too. However, in an ordinary Swedish forest it can be difficult to draw acceptable circles on the ground. Only if we are on a mission to some desert country it could work well. But in that case we could use the full length of the rope for maximum accuracy:
Tie the rope to the thickest of the (palm) trees and draw a segment of a large circle above the midpoint between the trees. Do the same with the rope tied to the other tree and make sure the free rope is the same length as before. The intersection of the circle segments corresponds to where we have the stick in the third solution. Proceed in analogy to that solution.
Note also that the first and third solution uses the very same geometrical model, only that the two given trees are placed into the model differently.
rmjarvis said,
May 16, 2007 at 11:02 am
For the new puzzle, I came up with a proof for an even tighter version of the problem. Specifically, if you write the 17 numbers in any random order, then there is necessarily some sequential subset of these numbers which is a multiple of 17.
For example:
3 1 8 15 3 16 9 11 13 4 1 6 13 16 10 11 7
The procedure for finding a solution is to keep a running total along the series, and always taking mod 17 when you go over 17. (Likewise, if any of the original numbers are negative or greater than 17, just put down the mod 17 value.)
For the above series, we have:
3 4 12 10 13 12 4 15 11 15 16 5 1 0 10 4 11
Then look for a repeated value. There are several to choose from here: 4, 12, 15, …
Let’s take the first two 4’s for example. The first 4 is at the second number (1), and the second 4 is at the seventh number (9). So we skip the first two values (including the 1) and take the next five (ending at the 9):
8 + 15 + 3 + 16 + 9 = 51 = 3*17
Alternatively, you can use the 0 sum that we found at position 14. In that case, we add up all the first 14 numbers:
3 + 1 + 8 + 15 + 3 + 16 + 9 + 11 + 13 + 4 + 1 + 6 + 13 + 16 = 119 = 7*17
The proof that this procedure will always work is as follows:
There are exacly 17 values in the running totals. Since all of these are mod 17, then either there are two equal values, or they accound for all 17 values from 0 to 16, in which case there must be a 0, which also gives us a solution. Therefore, there is always a solution.
Obviously, this generalizes to any number, not just 17.
contactm3 said,
June 7, 2007 at 3:47 pm
rmjarvis: I think you created your mod 17 table incorrectly. 1 mod 17 = 1, not 4. 8 mod 17 = 8, not 12. etc. Or, perhaps I misunderstood how you arranged your second array.
However, I do agree with the begining of your method as far creating a second set/array who’s values are the first array’s values mod 17 (or mod x, in a general form). I discovered the same approach. But I can’t follow you from there to a generalized proof (please help!)
let the size of our set (or “length of our array”, if you will) = x. Any integer, n, mod x = some number from 0 to (x-1). This means that there are, at most, three possible states of our second array:
1.) the second array includes at least one instance of the integer ‘0’. In this case we know for certain that some subset of our original set sums to kx for some integer k.
2.) all values in our second array will be the same number, k. In this case, there will be x occurences of k. Thus, the sum of all the values of the array will = kx.
3.) neither of the first cases will be true, meaning all x positions in the array will be filled with some value from 1 through (x-1). Since there are more positions in the array to fill than unique numbers to fill them with, at least two values in the array will be the same. ** This is the point rmjarvis reached in his post. I noticed that if [a mod y = q], and [b mod y = r], and [(q+r) mod y = 0], then [(a+b) mod y = 0]. I have not yet seen a proof that an array in this third state nessessarily contains a subset who’s sum mod 17 = 0 (though I intuit an elegant one exists).
I guess it’s time to listen to the podcast to find out the answer :_(
Interesting note: I once ran into this very same bump while working on P vs. NP. It’s truth seemed so obvious that I just made a note that said “come back and proove this later” and continued moving forward under the assumption that it was true. lol.