03 Discrete optimisation

Discrete optimisation is quite a different skill than that found in calculus, where the variables are real (not integers), and situations are continuous. Here the variables are integer, and the standard method involves two steps,

1. Show optimality, that is, give an argument to show that the proposed solution cannot be exceeded.
2. Show that this demonstrated optimum exists.

The first part is usually a challenging mathematical argument, while the second requires no more than production of an optimum. Other than the fact that the variables are integer, the method is usually given away by the openness of a statement requiring an optimum (maximum or minimum).

The following is an example from an AMC problem which was not easy but was set in its primary division.

Example 3.1

An apartment block has a number of square apartments and a number of square gardens. Apartments must have at least one window, either to the outside or to a garden. In figure 1, one apartment has a window to an internal garden G, and ten have windows to the outside.

What is the smallest number of gardens needed for an apartment block built on a 6 by 6 square, as in figure 2, so that each apartment has a window to the outside or to an internal garden?

Strategy

It is probably easy to guess that the answer will be a fairly small integer, but the mathematical argument to identify that number, particularly to optimality argument, will need to be quite precise.

Solution 3.1

First we look for optimality.

Consider the 6 by 6 block as shown in figure 1. All the outside apartments have exterior views, so we need only deal with the 16 interior squares.

Putting in one garden will remove one apartment and bring light to (at most) four other apartments.

This complying arrangement will deal with at most five of the internal squares and so, as 3x5 <16, at least four gardens are required.

Given we have a minimum, now we need to give an example consistent with this.

It is relatively easy to find such a solution with 4 gardens, as shown in figure 2.

So the smallest number of gardens required is 4.

Discussion

The following example, from the International Mathematics Tournament of Towns, is one in which there is a nice use of Eulerian graph theory, which is also a useful tool in networking problems.

Example 3.2

A village is constructed in the form of a square, consisting of 9 blocks, each of side length l, in a 3 by 3 formation. Each block is bounded by a bitumen road.

If we commence at a corner of the village, what is the smallest distance we must travel along bitumen roads, if we are to pass along each section of bitumen road at least once and finish at the same corner?

Strategy

This problem is also an excellent interactive classroom problem. Students can try for some time to improve their first results until everyone is convinced they have a result which cannot be beaten.

Solution 3.2

The optimality part of the proof requires graph theory reminiscent of the Königsberg bridges. It is noted that there are three types of node, those with 2, 3 and 4 joining lines. In the case of the even-numbered ones a shortest path can go through them optimally, with an inward route matched by an outward route. However there are eight nodes with three joining lines, which means they have to be visited twice, involving an apparent wasted visit. Assuming they are in four pairs and that an extra route can be shared between a pair, there are at least four extra routes required. Since there were 24 routes in any case, the shown route travelling along 28 links is optimal.

The shortest route does turn out to be of length 28l, with existence shown by the diagram.

Diagrams

Composers of problems such as this often face the issue of whether or not to include a diagram in the problem statement. The level of challenge can be quite different for such problems dependent on whether or not a diagram is provided. In inclusive competitions and in classroom use diagrams are more common. In advanced competitions such as the International Mathematical Olympiad, constructing the diagram is usually part of the challenge and diagrams are rarely if ever provided in the description of the problem.