Competition problem — Number theory

Library / /41 of 41

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it New Zealand

Problem:
Is it possible to place a positive integer in every cell of a $10 \times 10$ array in such a way that both the following conditions are satisfied?
- Each number (not in the top row) is a proper divisor of the number immediately below.
- Each row consists of 10 consecutive positive integers (but not necessarily in order).

Solution

Solution:
Answer: Yes. In fact it is even possible to achieve such an array where each row consists of ten consecutive positive integers in increasing order. We shall construct an example explicitly.

Initially let the top row be $(1,2,3,\ldots ,10)$ in this order. Then iteratively if the contents of a particular row are
$(n,n + 1,n + 2,\ldots ,n + 9)$
then construct the next row to be
$\left((n + 9)! + n,(n + 9)! + n + 1,(n + 9)! + n + 2,\ldots ,(n + 9)! + n + 9\right).$
So the completed array will look like this:

1	2	3	...	10
$10! + 1$	$10! + 2$	$10! + 3$	...	$10! + 10$
:	:	:	:	:
$n$	$n + 1$	$n + 2$	...	$n + 9$
$(n + 9)! + n$	$(n + 9)! + n + 1$	$(n + 9)! + n + 2$	...	$(n + 9)! + n + 9$
:	:	:	:	:

To prove that this construction works, we simply need to verify that

\left((n + 9)! + n + i\right)

is always a multiple of

(n + i)

for each

i = 0,1,2,3,\ldots ,9

. We prove this by combining these two trivial divisibilities:

(n + i)\mid (n + 9)! \qquad \mathrm{and} \qquad (n + i)\mid (n + i).

Thus this construction satisfies the required conditions.

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.