Maths Olympiad Prep

Library / /5 of 86

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

Consider the 4×44 \times 4 "multiplication table" below. The numbers in the first column multiplied by the numbers in the first row give the remaining numbers in the table. For example, the 33 in the first column times the 44 in the first row give the 12 (=3⋅4)12\ (=3 \cdot 4) in the cell that is in the 33rd row and 44th column.

1234
11234
22468
336912
4481216

We create a path from the upper-left square to the lower-right square by always moving one cell either to the right or down. For example, here is one such possible path, with all the numbers along the path circled:
1234
11234
22468
336912
4481216

If we add up the circled numbers in the example above (including the start and end squares), we get 4848. Considering all such possible paths:

a. What is the smallest sum we can possibly get when we add up the numbers along such a path? Prove your answer is correct.

b. What is the largest sum we can possibly get when we add up the numbers along such a path? Prove your answer is correct.

Solution

Solution:

The minimum is 4646 and the maximum is 5050. To see this more easily, tilt the grid 4545 degrees:

Figure 1

Now every path must include exactly one number from each row. The smallest and largest numbers in each row are respectively at the edge and in the middle, so the smallest and largest totals are achieved by the paths below:

Figure 2

(16)(16)

Figure 3

These totals are 4646 and 5050.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.