Competition problem — Combinatorics

Library / /84 of 196

Combinatorics Difficulty 5.0 AIME Prove it Soviet Union

Problem:

The numbers $1$ and $2$ are written on an empty blackboard. Whenever the numbers $m$ and $n$ appear on the blackboard the number $m + n + mn$ may be written. Can we obtain

(1) $13121$ , (2) $12131$ ?

Solution

Solution:

(1) $13121 = 2 + 4373 + 2$ . $4373, 4373 = 2 + 1457 + 2$ . $1457, 1457 = 2 + 485 + 2$ . $485, 485 = 2 + 161 + 2$ . $161, 161 = 2 + 53 + 2$ . $53, 53 = 2 + 17 + 2$ . $17, 17 = 2 + 5 + 2$ . $5, 5 = 2 + 1 + 2$ . $1$ .

Put $M = m + 1$ , $N = n + 1$ . Then the number derived from $m$ and $n$ is $MN - 1$ . So if $M$ and $N$ are of the form $2^a 3^b$ then so is $MN$ . Thus we can only ever write up numbers of the form $2^a 3^b - 1$ . But $12131 = 2^2 3^2 337 - 1$ , which is not of the required form.

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.