How to Break a Math Problem Down from First Principles
This Oxford University entrance exam question illustrates the systematic, first principles reasoning that all good mathematicians use, and which GPT4 still struggles with
Many of us are familiar with the rules of the sides of a right angled triangle. By the Pythagorean Theorem, if a and b are the two smaller sides, and c is the longest side, then a² + b² = c². Well known integer solutions to this are known as Pythagorean Triples. Examples include (3, 4, 5) and (5, 12, 13).
A more general construct is a Triangular Triple. Any trio of positive integers which can form the lengths of the sides of a triangle is called a triangular triple. Obviously, integer Pythagorean triples are triangular triples. But in general, an integer triple (a, b, c) is a triangular triple if, when listed in (non-strictly) increasing order, the sum of the first two integers is strictly larger than the third.
As an example, lets take the triple (4, 2, 3). These can be the lengths of the sides of a triangle because 2 + 3 > 4. Similarly (2, 2, 2) is a triangular triple. But (1, 3, 1) is not a triangular triple, as it is not possible to construct a triangle with these side lengths (1 + 1 ≯ 3).
A recent Oxford University entrance question related to triangular triples, and I think it’s a lovely illustration of how you can progressively deconstruct a problem from first principles in order to solve questions which look very challenging at first.
This problem defined a function f(P), where P > 2, as the number of triangular triples which sum to P. In the end it asks us to find f(21). Finding the number of triangular triples which sum to 21 sounds like a real brain-buster, but using some progressive, systematic steps we can find a very easy way to calculate this. At the end I’ll also show that AI like GPT4 has a real problem with these kinds of questions that require first principles reasoning.
Here are the various parts of the question and my solutions. I found it an interesting question and a good exercise at mathematical thinking that required very little textbook knowledge.
(i) Find the values of f(3), f(4), f(5), f(6)
This simply gets us used to thinking about and understanding a new concept.
- Since the only positive integer triple that sums to three is (1, 1, 1), and this is clearly a triangular triple, f(3) = 1
- Any positive integer triple which sums to 4 must contain 2. Hence the other two numbers are both 1. Since 1+1 is not strictly greater than 2, no triangular triples exist and f(4) = 0.
- Any positive integer triple which sums to 5 must contain 2 or 3, but not both. If it contains 3 , then the others must both be 1 and this is not triangular. If it contains 2, then the others must be 1 and 2, and this is triangular. Hence (2, 2, 1), (2, 1, 2) and (1, 2, 2) are all such triangular triples, and so f(5) = 3.
- Any positive integer triple which sums to 6 must consist of one 4 and two 1’s (not triangular), one each of 3, 2 and 1 (not triangular) or three 2’s (triangular). Therefore the only triangular triple is (2, 2, 2) and hence f(6) = 1.
(ii) If (a, b, c) is a triangular triple, prove that (a+1, b+1, c+1) is also a triangular triple
First note that we can always assume a, b, c are in (nonstrictly) increasing order — because if they are not, we can simply rearrange them so that they are. This reasoning will be important for most of this question.
Now since a+b >c, we can say (a+1) + (b+1) = (a+b)+2 > c+2 > c+1. Hence (a+1, b+1, c+1) is a triangular triple.
(iii) If (x, y, z) is a triangular triple and x+y+z is even and no less than 6, prove that x, y and z are all at least 2, and that (x-1, y-1, z-1) is also a triangular triple.
Again assume x, y, z are increasing. To prove that all three are at least 2, we just need to show that x cannot be 1. Assume x = 1. Then 1+y+z is even and so y+z is odd.
Also we have 1+y > z, so y > z -1, hence y ≥ z. But we know y ≤ z and hence y = z. So y+z is even.
This is a contradiction, so x > 1.
(iv) Prove that, for any positive integer k ≥ 3, f(2k-3) = f(2k)
From Part (ii) we know that any triangular triple which sums to 2k-3 can be mapped uniquely to a triangular triple which sums to 2k by simply adding 1 to each integer. This means that the set of triangular triples which sums to 2k is at least as big as the set of triangular triples which sums to 2k-3.
From Part (iii), since 2k is even and no less than 6, we know that we can map each triangular triple which sums to 2k uniquely to a triangular triple which sums to 2k-3 by subtracting 1 from each integer. This means that the set of triangular triples which sums to 2k-3 is at least as big as the set of triangular triples which sums to 2k.
Hence both sets must have the same size and so f(2k-3) = f(2k).
(v) Let S ≥ 3 and let P = 2S. Show that (a, b, c) is a triangular triple which sums to P if and only if each of a, b, c is strictly smaller than S
This is an ‘if and only if’ proof so I need to prove it in both directions.
Again assume a, b, c are increasing and sum to P.
First we need to prove that if a+b > c, then c < S. Assume c ≥ S. Then a+b > c ≥ S, so a+b+c > 2S = P. This is a contradiction, so c < S.
Now we need to prove that if c < S then a+b > c. If c < S, then 2S-c > S > c. But a+b+c = P = 2S, so a+b = 2S-c. Hence a+b > c.
(vi) For any a with 2 ≤ a ≤ S-1, show that the number of possible values of b such that (a, b, P-a-b) is a triangular triple is a-1
By part (v), P-a-b = 2S-a-b ≤ S-1. So S-a+1 ≤ b. But also b ≤ S-1. So given any specific value of a, the value of b can range from S-a+1 to S-1. So the total number of possible values of b is (S-1)-(S-a) = a-1.
(vii) Find an expression for f(P) for any even P no less than 6
Let (a, b, P-a-b) be a triangular triple with P even and no less than 6. From Parts (iii) and (v) we know that a can have a value from 2 up to S — 1, and from part (vi), we know that, for each such value of a, there are a-1 values of b.
So our expression for f(P) can be derived as follows:
(viii) Find f(21)
By Part (iv), f(21) = f(24). And since 24 is even and greater than 6 we can use our new formula from Part (vii), with S = 12, giving us an answer of 55.
Let’s double check using a crude counting function in R:
# crude function to count triangular triples which sum to P
n_triangular_triples <- function(P) {
check <- c()
for (a in 1:P) {
for (b in 1:(P - a)) {
if (P - a - b > 0) {
sorted <- sort(c(a, b, P - a - b))
if ((sum(sorted) == P) && (sorted[1] + sorted[2] > sorted[3])) {
check <- append(check, 1)
}
}
}
}
sum(check)
}
# test on P = 21
n_triangular_triples(21)
[1] 55Of course, we can also use our neat formula to find f(P) for larger P. For example, f(997) = f(1000) = 124,251. We can check using our function in R, if you are willing to wait a few seconds for it to cycle through all the possible triples.
n_triangular_triples(997)
[1] 124251How did GPT4 do at this?
Not very well, despite its desire to mansplain the Triangle Inequality Theorem, as you can see below. I asked the question three times and the answers I got were 100, 22, and 190. Guess there is no substitute for real intelligence!
What did you think of this problem? Feel free to comment.
