04 Proof by cases

Quite often experimentation with a situation leads to a conclusion that a result can only be established after an exhaustive consideration of a mutually exclusive set of cases. This method is usually known as proving by cases. The challenge is two-fold. First, one needs to identify the cases that might apply and to describe them in a way that is clear, efficient and preferably non-overlapping. Secondly, one needs to ensure that the cases are exhaustive, that nothing is left out.

The method can be illustrated by the following problem, which is extracted from a larger problem used in the Mathematics Challenge for Young Australians.

Example 4.1

An equiangular hexagon is one in which all angles are equal. If all its side lengths are integers, it is an equiangular hexagon with integer length sides, or an eqhil.

The diagram below shows an equiangular (also equilateral) triangle with side length n. From each corner equilateral triangles with side lengths a, b and c have been cut. The resulting figure is an equiangular hexagon. If n, a, b and c are integers the side lengths of the hexagon are integers. So this is an eqhil. Every eqhil can be constructed in this way.

An eqhil can be dissected into u unit equiangular triangles (all the triangles have side length 1).

For example, if n=6, a=1, b=2 and c=2, the eqhil formed has size 27 because it can be dissected as shown.

An eqhil can be described by its side lengths taken in order. The eqhil shown has side lengths 1, 3, 2, 2, 2, 3 in that order.

Find an equiangular triangle of side length different from 6 whose corners can be cut as described above to produce the eqhil of side lengths 1, 3, 2, 2, 2, 3 in order.

Strategy

This problem requires some structure to be set up, in such a way that ultimately we will be certain we have covered all the cases.

Solution 4.1

We note that an equiangular triangle of side length n contains

1 + 3 + ... + (2n - 1) = n²

unit equiangular triangles. The given eqhil cannot be formed from an equiangular triangle with n< 5, since then the total number of unit triangles before cutting is 25<27.

Try an equiangular triangle with n=7 containing 49 unit triangles. Cut off corners using the following systematic approach: choose integers a, b and c, where 0<a≤b≤c, together with the restriction b+c≤n-1 (if b+c≥n, an eqhil is not formed). Note that u, the number of remaining unit triangles, is given by

u = n² - a² - b² - c² = 49 - a² - b² - c²,

when n=7, with b+c≤6.

The table exhausts all possibilities and the combination a=2, b=3 and c=3 gives the required eqhil from an equilateral triangle with n=7.

Comment

The method can also be illustrated by the following problem, one of the more challenging problems from the Australian Mathematics Competition.

Example 4.2

The sum of n positive integers is 19. What is the maximum possible product of these n numbers?

Strategy

This problem is also excellent for classroom interaction. Students can try to obtain maximum products with various selections but soon discover that high numbers adding to 19 don’t seem to help, while at the other extreme the number one is also useless. Students will eventually see that a summand m bigger than 4 can always be replaced to good effect by 2 and m − 2. They will also see that 4 can always be replaced by 2 and 2. They will also be able to formally dispose of the case of an integer being 1. So they are left to consider only sums that use the numbers 2 and 3. The situation is finally resolved by noting that replacing any three 2s in the sum by two 3s will increase the product.

Solution 4.2

We are looking for a maximum product n₁ x n₂ x n₃ x … x n_k where n₁ + n₂ + n₃ + … + n_k=19.

If any factor n_i is ≥ 5, it can be replaced with 2(n_i - 2) for a larger product, since 2(x-2)>x for x ≥ 5; so every factor is ≤ 4.

If any factor n_i is equal to 4, it can be replaced by 2 x 2 with no change to the product. So we shall do this and then every factor is ≤ 3.

If any factor is 1, it can be combined with another factor, replacing 1 x n_i by (n_i + 1) which increases the product. So now all factors are 2 or 3.

If there are three or more 2s, 2 x 2 x 2 can be replaced by 3 x 3 to increase the product. So there are at most two 2s.

There is only one way that 19 can be written as such a sum, there are five 3s and two 2s.

So the maximum product is 3⁵ x 2² = 972.

Discussion

In this problem, students might ask whether the number 19 plays an essential role, or whether the same argument is available when this number is replaced by some other. A common practice in competition problems is to ask students to look at a particular instance of a general result; a student who is aware of this may often establish the general result, often by a more effective argument as the solver is not distracted by irrelevant factors particular to the situation.

A secondary challenge for a more senior student studying calculus is to decide whether there is a continuous version of the challenge and formulate it exactly.