MPMP: Take-away Triangles
This post was made to explain the general behavior in one of Matt Parker's Maths Puzzles
Summary:
1. Show that the order of numbers in the set doesn't matter for the triangle.
2. Show that you can transform the set by making one of the values always 0.
3. Show that taking repeated differences leads to the same algorithm as the Euclidean Algorithm for finding the GCD.
4. Conclude that the pattern of numbers (a, b, c) reduces to a cycle of two of GCD(|b - a|, |c - a|) and one of 0.
1. The numbers on the vertices of the triangle can be represented as a set of three numbers (a, b, c). The order of the numbers doesn't matter, as any configuration of the numbers will yield the same triangle, just in another orientation by flipping or rotating the triangle.
2. Taking the difference of each pair of possible numbers will give another set of three numbers, and again, the order doesn't matter for the same reasons as shown above. Since only the differences are being calculated, the results will not change if you change every value by some constant.
Calculating the differences vs. adding all values by a constant and calculating the differences:
| Differences | Differences with Constant |
|---|---|
| (a, b, c) | (a + E, b + E, c + E) |
| (|a - b|, |a - c|, |b - c|) | (|(a + E) - (b + E)|, |(a + E) - (c + E)|, |(b + E) - (c + E)|) |
| (|a - b|, |a - c|, |b - c|) | (|a - b|, |a - c|, |b - c|) |
We can change every value by some constant so that one of the values will be 0. Subtracting every value by 'a', we get:
(0, |b - a|, |c - a|)
When calculating the differences for this new set of numbers, we will end up with (|a - b|, |a - c|, |b - c|), as expected from the table above. The reason why we want a configuration like this will be explained in the next section.
3. What happens when trying to repeatedly take the difference of the set of three numbers with a 0 as one of them? A concrete example is needed.
| Differences |
|---|
| (0, 2, 15) |
| (2, 15, 13) |
| (13, 11, 2) |
| (2, 11, 9) |
| (9, 7, 2) |
| (2, 7, 5) |
| (5, 3, 2) |
| (2, 3, 1) |
| (1, 1, 2) |
| (0, 1, 1) |
| (1, 1, 0) |
| (0, 1, 1) |
Notice how, starting at (2, 15, 13), the next iteration of numbers keeps the smallest two numbers of the previous iteration. Also notice that taking the difference of the smallest two numbers gives the third number of the next iteration. For example, for (2, 15, 13), 2 and 13 are kept, and the difference of the two makes 11, which makes the next set of numbers (13, 11, 2). Also, a loop is reached at the end, where there are only 1's and 0's. Here's another example:
| Differences |
|---|
| (0, 3, 15) |
| (3, 15, 12) |
| (12, 9, 3) |
| (3, 9, 6) |
| (6, 3, 3) |
| (3, 3, 0) |
| (0, 3, 3) |
| (3, 3, 0) |
There are similarities to the last sequence of differences, but now the final state is a loop of only 3's and 0's. The algorithm that is behind this process has a parallel to the Euclidean Algorithm, using subtraction only. In the Euclidean Algorithm, differences are also taken, and the result of the difference and the smallest of the two operands are used in the next calculation. See below:
| Euclidean Algorithm | Represented as a set of three numbers |
|---|---|
| 15 - 3 = 12 | (15, 3, 12) |
| 12 - 3 = 9 | (12, 3, 9) |
| 9 - 3 = 6 | (9, 3, 6) |
| 6 - 3 = 3 | (6, 3, 3) |
| 3 - 3 = 0 | (3, 3, 0) |
The second column is another representation of the first column. Note how the second column matches the sets of values in the previous differences table. Since the Euclidean Algorithm is used to find the Greatest Common Divisor (GCD) of two numbers, then this repeated difference of numbers on the vertices of the triangle does the same thing. The difference process reduces the set of numbers down to values of the GCD of the two non-zero values of the set.
4. Recall the transformation made earlier, where the set of points (a, b, c) is equivalent to (0, |b - a|, |c - a|). As shown above, the two non-zero numbers of the set are reduced into their GCD. So, the general rule for how (a, b, c) evolves is that it will reduce to a set of three numbers where one is 0, and the other two are the GCD of |b - a| and |c - a|.