Earlier today I set you the following puzzle:
Find all the ways to arrange four points so that only two distances occur between any two points.
In other words, how many ways are there to draw four dots on a piece of paper such that whichever two dots you choose, the distance between these two points is one of two values?
Solution: there are six ways, and I’ll show them straight away, before discussing how you might have gone about finding them. (The first one I had already given as an example.)
In the setting of the question I mentioned that Peter Winkler, the source of the problem, said that nearly everyone misses a solution.
So, how do you go about making sure that you catch them all?
There are different approaches. I’m going to give an outline of Colin Wright’s proof, as presented here on his excellent maths blog.
He refers to the two distances in any in any solution as the long one, and the short one. First, he argues, it must be the case than in any solution, three of the points make a triangle that has one long and two short sides.
So, let’s draw a triangle with one long and two short sides: points A and C are fixed, but B can be anywhere on the dotted line. (It can’t be higher than the dotted line since then the blue lines would no longer be the short distances.)
To find a solution we need to position the fourth point, D, such that it links to the other points using either a short or a long distance.
There are 8 possible ways it could do that. The distances from D to A, B and C could be
-
short, short, short
-
short, short, long
-
short, long, short
-
short, long, long
-
long, short, short
-
long, short, long
-
long, long, short
-
long, long, long
For each case, Colin either finds a valid position for D, or shows that there isn’t one. This exhaustive search finds the six patterns above. For more details I recommend that you read his full proof here.
Thanks Colin for telling me the problem in the first place!
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.