Track / Stage 6 / 66 of 400 #1066 of 1964

Problem 1066

National olympiad, first round

Number theory Difficulty 6.1 Prove it

(9 points) Given a natural number. In one move, plus signs are written between some of the digits of the number, and the resulting sum is calculated (for example, from the number 123456789, $12345+6+789=13140$ can be obtained). In the next move, plus signs are written between some of the digits of the obtained sum, and the sum is calculated again, and so on. Prove that from any number, a single-digit number can be obtained in no more than 10 moves.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution. Four moves are sufficient.

For numbers less than 1000, the statement is obvious.

Larger numbers are broken down into four-digit blocks (which do not start with 0), possibly plus zeros and one number less than 1000 at the end (for example, $12300004500060=1230+0+0+0+4500+0+60$ ). If this results in $k$ four-digit blocks, then the sum is at least $1000 k$ . Now we replace one by one the non-zero addends with the sum of their digits. As a result, the sum becomes no more than $36 k+27<100 k$ , i.e., the sum is at least one digit smaller. Since the sum decreased by less than 9999 at each move, the last sum before the reduction in the number of digits was of the form 10....0abcd. This sum can be obtained with the first move, and then the number can be replaced with the sum of its digits three times.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.