Maths Olympiad Prep

Library / /179 of 183

, 2025

Combinatorics Difficulty 4.9 AIME Find the answer Canada

In an arithmetic grid, adjacent numbers increase by a
fixed integer a>0a>0 moving left to
right within each row. Also, adjacent numbers increase by a fixed
integer b>0b>0 moving top to bottom
within each column. For example, the grid shown is a 3×33 \times 3 arithmetic grid with a=2a = 2 and $b =
5$.

11
33
55

66
88
1010

1111
1313
1515

Suppose that an 8×88 \times 8
arithmetic grid has a 11 in the top
left corner, and a number less than 7575 in the bottom right corner. How many
such grids have a 4545 somewhere in
column 5?

Pick one

Solution

We adopt the notation [row number, column number] to be equal to
the contents of a specific square in the grid.

Since [1,1][1,1] is 11 and adjacent numbers increase by a
fixed integer a>0a>0 moving left to
right within each row, then [1,2][1,2]
is 1+a1+a, [1,3][1,3] is 1+2a1+2a, and so on to the end of the row
where [1,8][1,8] is 1+7a1+7a.

Similarly, adjacent numbers increase by a fixed integer b>0b>0 moving top to bottom within each
column, and so the contents of each square in row 2 is bb greater than the adjacent square in row
1.

That is, [2,1][2,1] is 1+b1+b, [2,2][2,2] is 1+a+b1+a+b, [2,3][2,3] is 1+2a+b1+2a+b, and so on to the end of the row
where [2,8][2,8] is 1+7a+b1+7a+b.

Continuing in this way in row 3, we get [3,1][3,1] is 1+2b1+2b, [3,2][3,2] is 1+a+2b1+a+2b, [3,3][3,3] is 1+2a+2b1+2a+2b, and so on to [3,8][3,8] which is equal to 1+7a+2b1+7a+2b.

We continue this pattern in the table below, and include each of the
entries in column 5 since the focus of the question is on this
column.

1
1+a1+a
1+2a1+2a
1+3a1+3a
1+4a1+4a
1+5a1+5a
1+6a1+6a
1+7a1+7a

1+b1+b
1+a+b1+a+b
1+2a+b1+2a+b
1+3a+b1+3a+b
1+4a+b1+4a+b
1+5a+b1+5a+b
1+6a+b1+6a+b
1+7a+b1+7a+b

1+2b1+2b
1+a+2b1+a+2b
1+2a+2b1+2a+2b
1+3a+2b1+3a+2b
1+4a+2b1+4a+2b
1+5a+2b1+5a+2b
1+6a+2b1+6a+2b
1+7a+2b1+7a+2b

1+3b1+3b
1+a+3b1+a+3b
\vdots
\vdots
1+4a+3b1+4a+3b
\vdots
\vdots
\vdots

1+4b1+4b
1+a+4b1+a+4b

1+4a+4b1+4a+4b

1+5b1+5b
1+a+5b1+a+5b

1+4a+5b1+4a+5b

1+6b1+6b
1+a+6b1+a+6b

1+4a+6b1+4a+6b

1+7b1+7b
1+a+7b1+a+7b

1+4a+7b1+4a+7b

1+7a+7b1+7a+7b

We are given that the number in the bottom right corner of the grid
is less than 7575, and so 1+7a+7b<751+7a+7b<75 or 7a+7b<747a+7b<74.

Dividing each term of this inequality by 77, we get 7a7+7b7<747\dfrac{7a}{7}+\dfrac{7b}{7}<\dfrac{74}{7}
or a+b<747a+b<\dfrac{74}{7} and since
aa and bb are positive integers, then a+b10a+b\leq10.

Since a+b10a+b\leq10, then by
multiplying each term by 44, we get
4a+4b404a+4b\leq40.

In the table above, [5,5][5,5] is 1+4a+4b1+4a+4b. Since 4a+4b404a+4b\leq40, then 1+4a+4b411+4a+4b\leq41 and so [5,5][5,5] cannot equal 4545.

Further, since bb is a positive
integer, then each of the entries in column 55 above row 5 is less than 1+4a+4b1+4a+4b and thus cannot equal 4545.

Thus if 4545 appears in column 5 of
this grid, then it can only appear in rows 6, 7 and 8.

We begin by noting that aa and
bb are positive integers, and since
a+b10a+b\leq10, then a9a\leq9 and b9b\leq9.

If [6,5][6,5] is 45, then 1+4a+5b=451+4a+5b=45 or 4a+5b=444a+5b=44.

If a=1a=1, then 4×1+5b=444\times1+5b=44 or 5b=405b=40, and so b=8b=8.

We confirm that when a=1a=1 and b=8b=8, then a+b10a+b\leq10 and so the number appearing in
the bottom right corner of the grid is less than 7575.

Thus, in the arithmetic grid with a=1a=1 and b=8b=8, [6,5][6,5] is 45.

If a=2a=2, then 4×2+5b=444\times2+5b=44 or 5b=365b=36 or b=365b=\dfrac{36}{5} (which is not an
integer), and so there is no such arithmetic grid in which [6,5][6,5] is 4545 when a=2a=2.

We could continue substituting the remaining values of aa from 33 to 99 to determine for which values of aa, 4a+5b=444a+5b=44 and a+b10a+b\leq10 and bb is a positive integer.

Alternately, we might notice that 4a4a is a multiple of 44, as is 4444.

Thus, if 4a+5b=444a+5b=44 then 5b5b must also be a multiple of 44 and so bb must be a multiple of 44.

The only remaining positive integer bb for which b9b\leq9 and bb is a multiple of 4 is b=4b=4.

When b=4b=4, we get 4a+5×4=444a+5\times4=44 or 4a=244a=24 and so a=6a=6.

We again confirm that when a=6a=6 and
b=4b=4, then a+b10a+b\leq10 and so the number appearing in
the bottom right corner of the grid is less than 7575.

In the arithmetic grid with a=6a=6 and
b=4b=4, [6,5][6,5] is 4545.

Thus, there are exactly 22 such
grids in which 4545 appears in row 6,
column 5.

If [7,5][7,5] is 4545, then 1+4a+6b=451+4a+6b=45 or 4a+6b=444a+6b=44 or 2a+3b=222a+3b=22.

In this case, we similarly notice that 2a2a is a multiple of 22, as is 2222.

Thus, if 2a+3b=222a+3b=22 then 3b3b must also be a multiple of 22 and so bb must be a multiple of 22.

We proceed by checking values of bb
which are equal to positive even integers.

When b=2b=2, we get 2a+3×2=222a+3\times2=22 or 2a=162a=16 and so a=8a=8.

In this case, a+b10a+b\leq10 and so the
number appearing in the bottom right corner is less than 7575.

In the arithmetic grid with a=8a=8 and
b=2b=2, [7,5][7,5] is 4545.

When b=4b=4, we get 2a+3×4=222a+3\times4=22 or 2a=102a=10 and so a=5a=5.

In this case, a+b10a+b\leq10.

In the arithmetic grid with a=5a=5 and
b=4b=4, [7,5][7,5] is 4545.

When b=6b=6, we get 2a+3×6=222a+3\times6=22 or 2a=42a=4 and so a=2a=2.

In this case, a+b10a+b\leq10.

In the arithmetic grid with a=2a=2 and
b=6b=6, [7,5][7,5] is 4545.

When b=8b=8, we get 2a+3×8=222a+3\times8=22 which is not possible
since a>0a>0.

Thus, there are exactly 33 such
grids in which 4545 appears in row 7,
column 5.

If [8,5][8,5] is 4545, then 1+4a+7b=451+4a+7b=45 or 4a+7b=444a+7b=44.

We notice that 4a4a is a multiple of
44, as is 4444.

Thus, if 4a+7b=444a+7b=44 then 7b7b must also be a multiple of 44 and so bb must be a multiple of 44.

We proceed by checking the two possible values of bb, namely b=4b=4 and b=8b=8.

When b=4b=4, we get 4a+7×4=444a+7\times4=44 or 4a=164a=16 and so a=4a=4.

In this case, a+b10a+b\leq10 and so the
number appearing in the bottom right corner is less than 7575.

In the arithmetic grid with a=4a=4 and
b=4b=4, [8,5][8,5] is 4545.

When b=8b=8, we get 4a+7×8=444a+7\times8=44 which is not possible
since a>0a>0.

Thus, there is exactly 11 such grid
in which 4545 appears in row 8,
column 5, and so there are 2+3+1=62+3+1=6
grids in total.

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.