Competition problem — Number theory

Library / /306 of 462

Number theory Difficulty 6.2 National Olympiad Prove it Ireland

The runcible positive integers are defined recursively as follows:
* $1$ and $2$ are runcible
* If $a$ and $b$ are runcible (where $a$ and $b$ are not necessarily distinct) then $2a + 3b$ is runcible.
Is $2024$ runcible?

Solutions — 2

Solution 1

Since $1$ and $2$ are runcible, then $8 = 2 \cdot 1 + 3 \cdot 2$ is runcible. If $a$ is runcible, then $5a = 2a + 3a$ is also runcible. By induction, $5^k a$ is runcible for all natural numbers $k$ . Hence $1000 = 5^3 \cdot 8$ is runcible and $2024 = 2 \cdot 1000 + 3 \cdot 8$ is also runcible.

Solution 2

We prove the following, more general statement:
*If $n \ge 15$ and $n$ is not a multiple of $3$ , then $n$ is runcible.*
The runcibility of $2024 = 3 \times 674 + 2$ then follows immediately.
For the proof we use the principle of infinite descent. Suppose there is a counterexample, that is some $n > 15$ that is not a multiple of $3$ and is not runcible. Take the minimal such $n$ .
We check by brute force that there are no counterexamples with $15 < n < 36$ . Direct calculations express the runcible numbers $5$ , $7$ , $8$ , $10$ , $13$ , $16$ , $17$ , $19$ , $20$ , $22$ , $23$ , $25$ , $26$ , $28$ , $29$ , $31$ , $32$ , $34$ and $35$ (which includes all non-multiples of $3$ between $15$ and $36$ ) in terms of smaller runcible numbers:

$2a + 3b$	$b = 1$	$b = 2$	$b = 5$	$b = 7$	$b = 8$	$b = 10$
$a = 1$	$5$	$8$	$17$	$23$	$26$	$32$
$a = 2$	$7$	$10$	$19$	$25$	$28$	$34$
$a = 5$	$13$	$16$		$31$
$a = 7$		$20$	$29$	$35$
$a = 8$		$22$

Thus any minimal

n

must have

n > 36

. Consider two cases: either

n

is odd or

n

is even. In the odd case,

(n-3)/2

is a positive integer and we have

n = 2 \cdot \frac{n-3}{2} + 3 \cdot 1

where

(n-3)/2

is a non-multiple of

3

, at least

16

, and less than

n

so is runcible by the minimality of

n

. That implies that

n

is runcible.
In the even case

(n-6)/2

is a positive integer and we have

n = 2 \cdot \frac{n-6}{2} + 3 \cdot 2.

As before,

(n-6)/2

is a non-multiple of

3

and is at least

16

, and less than

n

so is runcible by the minimality of

n

, which in turn implies

n

is runcible. Thus, we have a contradiction. There is no minimal

n

which exceeds

15

, is not a multiple of

3

and is not runcible. This proves the claimed general statement and solves the problem.

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.