Competition problem — Combinatorics

Combinatorics Difficulty 5.0 AIME, harder Prove it Hong Kong

There is a $20 \times 20$ table and $400$ cards printed with the numbers $1$ to $400$ . The cards are then distributed to the cells of the table so that there is one card in each cell. After that, we put a red sticker on the card in each row with the largest number, and a blue sticker on the card in each column with the largest number. Let $A$ denote the smallest number on the $20$ cards with red stickers, and $B$ denote the smallest number on the $20$ cards with blue stickers. How many different possible values of $|A - B|$ are there?

Solution

Answer: $362$

For convenience we shall use the term 'red number' to the number on a card with a red sticker, and similarly for 'blue number'. Clearly, a red number, being a row maximum, is at least $20$ . Also, since $A$ is the smallest red number, there are $19$ other red numbers greater than $A$ , so $A$ is at most $381$ . The same is true for $B$ . That is, both $A$ and $B$ are between $20$ and $381$ (inclusive), and so $|A - B|$ is at most $361$ .

We shall prove that all these $362$ possibilities (from $0$ to $361$ ) for $|A - B|$ are attainable. Indeed, we can make $A = 381$ and $B$ can be equal to any value between $20$ and $381$ . To make $A = B = 381$ we can use the following configuration (the arrangements of the starred entries are unimportant):

381	*	*	...	*
*	382	*	...	*
*	*	383	...	*
...	...	...	...	...
*	*	*	...	400

On the other hand for any

B \in \{20, 21, ..., 380\}

, we can use the following configuration to obtain such value of

B

while having

A = 381

1	*	*	...	*	381
2	382	*	...	*	*
3	*	383	...	*	*
...	...	...	...	...	...
19	*	*	...	399	*
B	*	*	...	*	400

It follows that the answer is

362

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.