2025 AMC 10B Problem 23

P21-25~6 minPrint

Diophantine Equations Modular Arithmetic Set up the equation/formula and compute; no special trick needed Substitute to simplify (u = x+1/x, shifting, scaling)

A rectangular grid of squares has $141$ rows and $91$ columns. Each square has room for two numbers. Horace and Vera each fill in the grid by putting the numbers from $1$ through $141 \times 91 = 12{,}831$ into the squares. Horace fills the grid horizontally: he puts $1$ through $91$ in order from left to right into row $1$ , puts $92$ through $182$ into row $2$ in order from left to right, and continues similarly through row $141$ . Vera fills the grid vertically: she puts $1$ through $141$ in order from top to bottom into column $1$ , then $142$ through $282$ into column $2$ in order from top to bottom, and continues similarly through column $91$ . How many squares get two copies of the same number?

Show solution without answering

Key insight

Horace writes 91(r−1) + c and Vera writes 141(c−1) + r. Setting them equal gives 9r = 14c − 5, solved by c = 1, 10, 19, …

Solution

1. Horace's number in a square. Use row $r$ (from $1$ to $141$ ) and column $c$ (from $1$ to $91$ ). Horace fills rows of $91$ . Before row $r$ he has filled $r - 1$ full rows, then he counts $c$ more:
$H = 91(r - 1) + c.$
Check: row $2$ , column $1$ gives $91 + 1 = 92$ , as the problem says.

2. Vera's number in the same square. She fills columns of $141$ . Before column $c$ she has filled $c - 1$ full columns, then she counts $r$ more:
$V = 141(c - 1) + r.$

3. Set them equal.
$91r - 91 + c = 141c - 141 + r.$
Move the $r$ 's to the left and the $c$ 's to the right: $90r - 140c = -50$ . Divide by $10$ :
$9r = 14c - 5.$

4. Find the first few solutions by trying $c$ . We need $14c - 5$ to be a multiple of $9$ .
- $c = 1$ : $14 - 5 = 9$ . Yes, $r = 1$ .
- $c = 2$ to $9$ : $23, 37, 51, 65, 79, 93, 107, 121$ . None is a multiple of $9$ .
- $c = 10$ : $140 - 5 = 135 = 9 \times 15$ . Yes, $r = 15$ .

Why a jump of $9$ ? Adding $9$ to $c$ adds $14 \times 9 = 126$ to $14c - 5$ , and $126$ is a multiple of $9$ . So the pattern of which $c$ work repeats every $9$ columns, and since only $c = 1$ worked among $1$ to $9$ , the solutions are exactly
$c = 1, 10, 19, \ldots \quad\text{and}\quad r = 1, 15, 29, \ldots,$
with $c$ going up by $9$ and $r$ going up by $14$ each time.

Stay inside the grid. The column can go up to $91 = 1 + 9 \times 10$ , and the row up to $141 = 1 + 14 \times 10$ . Both reach their limit at the same step, so the solutions are the steps $0, 1, 2, \ldots, 10$ : that is $11$ squares. The last one is the bottom-right corner, where both write $12{,}831$ .

The answer is $\boxed{\textbf{(C)}\ 11}$ .

Why this works

Each way of filling gives a simple formula in the row and column, so "same number in a square" is one equation with two whole-number unknowns. Trying small values finds the first solution and the jump size, and the rest form an evenly spaced list. When counting an evenly spaced list, count the terms, not the gaps; the two corner squares (both hold $1$ and $12{,}831$ ) are a good check that the list is right.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Index the square in row $r$ and column $c$ , with $1 \le r \le 141$ and $1 \le c \le 91$ .

Horace works in rows of $91$ , so he finishes $r-1$ complete rows and then counts $c$ squares:
$H = 91(r-1) + c .$
Vera works in columns of $141$ , so she finishes $c-1$ complete columns and then counts $r$ squares:
$V = 141(c-1) + r .$

Set $H = V$ :
$91r - 91 + c = 141c - 141 + r \implies 90r - 140c = -50 \implies 9r - 14c = -5,$
after dividing by $10$ . So
$9r = 14c - 5 .$

Reduce modulo $9$ : $14c \equiv 5$ , i.e. $5c \equiv 5 \pmod 9$ , and $5$ is invertible mod $9$ , so $c \equiv 1 \pmod 9$ . Write
$c = 9k + 1 \implies 9r = 14(9k+1) - 5 = 126k + 9 \implies r = 14k + 1 .$

Now impose the size of the grid:
$1 \le 9k+1 \le 91 \implies 0 \le k \le 10, \qquad 1 \le 14k+1 \le 141 \implies 0 \le k \le 10 .$

Both give the same range, so $k = 0, 1, \dots, 10$ : that is $11$ squares. They run from $(r,c) = (1,1)$ , which holds $1$ twice, to $(141, 91)$ , which holds $12{,}831$ twice.

The answer is $\boxed{\textbf{(C)}\ 11}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 7: Algebra With Integers
Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Intermediate Algebra, Chapter 20: Some Advanced Strategies (§20.2)
Introduction to Algebra, Chapter 11: Special Factorizations (§11.5)