Competition problem — Algebra — Maths Olympiad Prep

Library / /146 of 196

Algebra Difficulty 5.7 AIME, harder Prove it Soviet Union

Problem:

(1) Player $A$ writes down two rows of $10$ positive integers, one under the other. The numbers must be chosen so that if $a$ is under $b$ and $c$ is under $d$ , then $a + d = b + c$ . Player $B$ is allowed to ask for the identity of the number in row $i$ , column $j$ . How many questions must he ask to be sure of determining all the numbers?

(2) An $m \times n$ array of positive integers is written on the blackboard. It has the property that for any four numbers $a$ , $b$ , $c$ , $d$ with $a$ and $b$ in the same row, $c$ and $d$ in the same row, $a$ above $c$ (in the same column) and $b$ above $d$ (in the same column) we have $a + d = b + c$ . If some numbers are wiped off, how many must be left for the table to be accurately restored?

Solution

Solution:

(1) is trivial. We can write the condition as $b - a = d - c$ , so the $10$ numbers in the first row and $1$ in the second row can all be chosen arbitrarily. Hence at least $11$ questions are needed. But they are also sufficient. Having determined those numbers, the others immediately follow.

(2). The $m + n - 1$ numbers in the first row and first column can all be chosen arbitrarily, but are sufficient to determine all the numbers. Hence at least $m + n - 1$ numbers must survive.

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.