1998 RMO - extension question

Number Theory Level 3

Inspiration - thanks to Michael Huang for posting the first problem.

A positive integer is written on a board. We repeatedly erase its unit digit and add $5$ times that digit to what remains.

Consider the sequence of numbers generated in this manner. What is the eventual behaviour of this sequence?

One or more of the following can happen: depending on the initial number on the board, the sequence...

can tend to infinity
can tend to a unique fixed value
can tend to any one of several (finitely many, but more than one) fixed values
can tend to any one of infinitely many fixed values
can become periodic with a period length greater than $1$ but less than $10$
can become periodic with a period length greater than or equal to $10$ but less than $100$
can become periodic with a period length greater than or equal to $100$

Code the options you think are possible as a seven-digit binary number, and enter its decimal equivalent as your answer. For example, if you think the first, third and fifth options are possible, your binary number would be $1010100_2$ and you would enter $84$ as your answer.

[An example to clarify the answer options: if instead we looked at repeatedly summing the digits of a positive number, the only correct option would be the third one - it will always tend to a fixed, single digit value]

The answer is 38.

1 solution

Chris Lewis
May 29, 2019

The correct answer is $38=0100110_2$ .

One of three things can happen to the sequence:

it can tend to the fixed point $49$
it can become periodic with period $6$ (the numbers in the cycle are $7\to35\to28\to42\to14\to21\to7$ )
it can become periodic with period $42$ (the numbers in this cycle are $1\to5\to25\to27\to \cdots \to20\to2\to10\to1$ )

The length $42$ cycle is made up of all the numbers $1$ to $48$ excluding multiples of $7$ .

To prove nothing else can happen, consider the map: we take a number of the form $10a+b$ (where $b$ is a single digit and $a$ is a non-negative integer) and replace it with $a+5b$ .

The difference of these is $\Delta=10a+b-(a+5b)=9a-4b$ . The largest $b$ can be (as a single digit) is $9$ ; so if $a>4$ then $\Delta>0$ , meaning that any number larger than $49$ is mapped to a smaller number. Eventually the terms must fall into the range $1$ to $49$ and become periodic (or fixed) as described above.

By the way, I had wanted to submit this as a "select all options that apply" format question (rather than the binary coding), but couldn't see a way to do this. Does anyone know if/how this can be done?

Chris Lewis - 2 years ago

1998 RMO - extension question

The answer is 38.

1 solution

0 pending reports