Up to now, I have at least ten proofs that's the problem is wrong .... but all my proofs are wrong Nice question. I would be very interested in any solution too.

This was problem 7 in the tournament of towns, am I right?

lambruscokid wrote: This was problem 7 in the tournament of towns, am I right? So, can you please provide a link or a solution.

I'm not sure about where it comes from, it's been given to me by a friend. If anyone knows a solution please post it, it's quite an unorthodox problem...

iMbaVidak wrote: ! bump Are you sure there is an olympiad-level solution for this problem ? In what contest / book did you find it ?

pco wrote: iMbaVidak wrote: ! bump Are you sure there is an olympiad-level solution for this problem ? In what contest / book did you find it ? This problem is from Tournament of Towns 2010, Senior A Level, the last problem.

Johan Gunardi wrote: pco wrote: iMbaVidak wrote: ! bump Are you sure there is an olympiad-level solution for this problem ? In what contest / book did you find it ? This problem is from Tournament of Towns 2010, Senior A Level, the last problem. Thanks. So it's supposed to be solved in less than 30-60mn I continue to search ...

Observations: All of the transformations are invariant (mod 9), so the one digit number is whatever the number is congruent to mod 9. This leads us to think about the digital sum of n. Let S(n) equal the sum of the digits of the number n. We want to show that $ S^{10}(n) = D(n)$ where D(n) is the digital sum of n. I'm not sure how to proceed from here...

bokagadha wrote: $ S^{10}(n) = D(n)$ where D(n) is the digital sum of n. That statement is certainly false, which is what seems to make this a hard problem (the fact that it doesn't even seem to be true at first look, at least to me). To disprove that, start with 99 which takes 2 applications of $ S$ to get to $ D$. Next, take the number consisting of 11 digits, all 9. The first step brings it to 99, so it takes 3 steps. To continue, compute the previous number divided by 9, and take the number consisting of that many 9s and keep doing that. Now, the reason that this doesn't disprove the problem is by putting the plus signs in other places, we can (hopefully) come up with lots of small digits which cancels out the fact that digit sum is the smallest possible single step, for example we can shorten the sequence for the number consisting of 11 9s above by on the first step keeping two 9s together, so that the first sum is 180, then the digit sum is 9. As for the original problem, I have no ideas. Probably a similar statement should hold in base $ b$ (with 10 steps replaced by $ b$ steps? or maybe a different function of $ b$), but I doubt considering it more generally would help.

Perhaps I wasn't clear. So take your example of 99. $ S(99) = 18$ $ S^2(99) = 9$. $ S^3(99) = 9$ etc. You can still take the digit sum of a 1 digit number, but the digit sum is the digit itself. For your example with 11 9s. Could you give an example of when the algorithm will take more than 10 steps. I think that it'll break down at some point, which makes this method valid. I could be wrong though. The reason I think this method is mainly right is mainly because of the time limit that was said. If you only have 30-60 minutes to carry this problem through, then a complicated algorithm would be unreasonable. So I think either this is the exact algorithm or close to it. I again could be underestimating the difficulty of the competition.

I guess my description wasn't clear: Take $ a_2=99$ (the 2 is for two applications to reach its digital sum), and take $ a_n=10^{\frac{a_{n-1}}9}-1$. Then $ a_n$ consists of $ a_{n-1}/9$ digits, each is 9, so the sum of its digits is $ a_{n-1}$, so $ a_n$ takes $ n$ applications of sum-of-digits to reach a one digit number. In general, we can just construct a sequence, where the sum of the digits of an element of the sequence is equal to the previous number, and my $ a_n$ is an example of such a sequence where the terms grow slowly compared to most sequences like that.

pco wrote: Johan Gunardi wrote: pco wrote: iMbaVidak wrote: ! bump Are you sure there is an olympiad-level solution for this problem ? In what contest / book did you find it ? This problem is from Tournament of Towns 2010, Senior A Level, the last problem. pco wrote: Thanks. So it's supposed to be solved in less than 30-60mn I continue to search ... last problem on a senior list might happen to be unsolvable in 30-60 min, it can even be unsolvable in 5 hours I mean have a look at other last problems from Senior levels, they are rather of a research type of problems.

iMbaVidak wrote: For any given number $ n\in \mathbb{N}$, for example $ 123456789$, we can add one or more $ +$ between its cyphers and calculate the sum gotten by that process. In the given example, we could do it like this: $ 1 + 234 + 5678 + 9 = 5922$. We now do the same step again for $ 5922$. Prove that, for any $ n$, it is possible in $ 10$ steps to get a 1-digit number. Thanks, Vidak I'm really skeptical with this problem... I mean, in the case in wich we have a number that only have the digit 1 (for example 111111111), the best reduction is when you sum all the digits and in this case you have the number of digits, so consider 11, now consider the number that consist in eleven 1's consecutives, call $ n_1$ this number (that is $ n_1=11111111111$) now consider the number that have $ n_1$ 1's consecutives, an so... if you call $ n_i$ to the ith number obtained, you have that for $ i>11$ the reduction goes to, at least, 11 in ten steps. What you think?

ZetaSelberg wrote: iMbaVidak wrote: For any given number $ n\in \mathbb{N}$, for example $ 123456789$, we can add one or more $ +$ between its cyphers and calculate the sum gotten by that process. In the given example, we could do it like this: $ 1 + 234 + 5678 + 9 = 5922$. We now do the same step again for $ 5922$. Prove that, for any $ n$, it is possible in $ 10$ steps to get a 1-digit number. Thanks, Vidak I'm really skeptical with this problem... I mean, in the case in wich we have a number that only have the digit 1 (for example 111111111), the best reduction is when you sum all the digits and in this case you have the number of digits, so consider 11, now consider the number that consist in eleven 1's consecutives, call $ n_1$ this number (that is $ n_1 = 11111111111$) now consider the number that have $ n_1$ 1's consecutives, an so... if you call $ n_i$ to the ith number obtained, you have that for $ i > 11$ the reduction goes to, at least, 11 in ten steps. What you think? Unfortunately, this is wrong. Let for example a number made of $ 9n+1$ digits $ 1$ with $ n$ as great as you want. Instead of summing digits in first step, take the sum of the nine groups of numbers made of $ n$ digits $ 1$ plus the last digit The first step gives you $ 10^n$ The second step gives $ 1$ As I said, I'm skeptical too but it's very difficult to find a counter example ...

pco wrote: ZetaSelberg wrote: iMbaVidak wrote: For any given number $ n\in \mathbb{N}$, for example $ 123456789$... I'm really skeptical with this problem... I mean, in... Unfortunately, this is wrong. Let for example a number made of $ 9n + 1$ ... You have all the reason Patrick , but... in my construction, no one number has the form $ 9n+1$ and so... no one has $ 9n+1$ digits 1. On the other hand, I am not sure if sum all digits in every step when you only have the digit 1 is the best way for to get a one digit number, because is possible that if you sum in other order (and you dont have the maximum reduction of digits in that step) and then you split the new number in other strange way and obtain lesser digits than the method that I said in only two steps (or tree, four whatever but lesser that my method). . What do you think?

ZetaSelberg wrote: pco wrote: ZetaSelberg wrote: iMbaVidak wrote: For any given number $ n\in \mathbb{N}$, for example $ 123456789$... I'm really skeptical with this problem... I mean, in... Unfortunately, this is wrong. Let for example a number made of $ 9n + 1$ ... ZetaSelberg wrote: You have all the reason Patrick , but... in my construction, no one number has the form $ 9n + 1$ and so... no one has $ 9n + 1$ digits 1. On the other hand, I am not sure if sum all digits in every step when you only have the digit 1 is the best way for to get a one digit number, because is possible that if you sum in other order (and you dont have the maximum reduction of digits in that step) and then you split the new number in other strange way and obtain lesser digits than the method that I said in only two steps (or tree, four whatever but lesser that my method). . What do you think? What I show is that summing all digits is not the best method allways. And my method works with any number made of only digits $ 1$ (and so are your numbers) : If the number is made of $ 9n+k$ digits one with $ k\in[1,9]$ use as first step the sum of $ 9$ blocks of numbers made of $ n$ $ 1$ plus sum of $ k$ last digits and the result of first step is the number $ 10^n+k-1$ At the second step, sum all digits and you get $ k$ and you are done.

pco wrote: ZetaSelberg wrote: pco wrote: ZetaSelberg wrote: iMbaVidak wrote: For any given number $ n\in \mathbb{N}$, for example $ 123456789$... I'm really skeptical with this problem... I mean, in... Unfortunately, this is wrong. Let for example a number made of $ 9n + 1$ ... ZetaSelberg wrote: You have all the reason Patrick... pco wrote: What I show is that summing... Yes! ... I understand... sorry

Actually this problem is, as some other users mentioned before, from the competition "Tournament of Towns". I participated in this competition last monday. I'm glad that I haven't seen this thread before, because this would have been quite unfair to other contestants, since I would have already given thought to the problem before participating in the competition. Thus, imo, we should stop discussing about the problem until we are sure that this competition is not open

FelixD wrote: Actually this problem is, as some other users mentioned before, from the competition "Tournament of Towns". I participated in this competition last monday. I'm glad that I haven't seen this thread before, because this would have been quite unfair to other contestants, since I would have already given thought to the problem before participating in the competition. Thus, imo, we should stop discussing about the problem until we are sure that this competition is not open I have the right to post any problem I wish on this forum. It's the choice of the competition executives to use it for their purposes or not.

iMbaVidak wrote: FelixD wrote: Actually this problem is, as some other users mentioned before, from the competition "Tournament of Towns". I participated in this competition last monday. I'm glad that I haven't seen this thread before, because this would have been quite unfair to other contestants, since I would have already given thought to the problem before participating in the competition. Thus, imo, we should stop discussing about the problem until we are sure that this competition is not open I have the right to post any problem I wish on this forum. It's the choice of the competition executives to use it for their purposes or not. So where have you seen the problem initially? Edit: I just read one of your older posts in this topic: iMbaVidak wrote: I'm not sure about where it comes from, it's been given to me by a friend. If anyone knows a solution please post it, it's quite an unorthodox problem... So you don't know where it comes from, but I'm quite sure your friend knows that. Maybe he wasn't told that one should not post the problems from the Tournament of Towns somewhere on the web, but there is a reason why they aren't available on the official homepage yet. I'm not sure wheter you are allowed to post these problems or not, but it is, as I mentioned before, unfair on everybody else who will participate in this competition.

When you do the TOT you're allowed to take the problems with you and do whatever you want with them. Anyway the Spring part is already over everywhere so np.

Here is my solution to the problem. I attached it.

Attachments:
Tournament of Towns.pdf (142kb)

Could anyone confirm if this solution is correct? It seems fine to me..

iMbaVidak wrote: For any given number $n\in\mathbb{N}$, for example $123456789$, we can add one or more $+$ between its cyphers and calculate the sum gotten by that process. In the given example, we could do it like this: $1+234+5678+9=5922$. We now do the same step again for $5922$. Prove that, for any $n$, it is possible in $10$ steps to get a 1-digit number. Here is a short solution to this cute problem. Actually, *FOUR* steps are always sufficient (and a more careful analysis should bring this down to three steps). 1. The decimal representation of every integer can be divided into packages of the following type: A single digit 0 forms a 0-package. A group of four consecutive digits with leading non-zero digit forms a 4-package. Finally the digits in the lowest (lowest two, lowest three) positions can form an exceptional package. 2. Let $n\ge1000$ be an integer with digit sum $S(n)$. If we break every 4-package into separate digits, then the problem allows us to jump from $n$ to $S(n)$. If we use every 4-package as a single 4-digit number, then we jump to an integer $T(n)\ge10S(n)$: The contribution of a 4-package to $S(n)$ is at most 36; its contribution to $T(n)$ is at least $1000>10\cdot36$. (The contribution of every 0-package remains 0, and the contribution of the exceptional package is negligible.) 3. Since $S(n)$ and $T(n)$ are at least a factor of 10 away from each other, there exists some perfect power of ten between them with $S(n)\le10^k<T(n)$. We start from $S(n)$, and then one by one transform the 4-packages from 4-single-digits into 4-digit numbers. Every transformation increases the current value by at most 9000. We stop as soon as we reach a value $U(n)\ge10^k$. Then $10^k\le U(n)\le 10^k+9000$, and the digit sum of $U(n)$ is at most 36. To summarize: We can jump from $n$ to $U(n)$, from $U(n)$ to a number $\le36$ by taking the digit sum, then to a number $\le11$, and then to a single-digit number. (And for $n<1000$ something trivial works.)

Wowwwww... very nice solution, gjw! (Just a small typo here. It should be $ 10^k\leq U(n)\leq 10^k+9962 $. Well, it isn't that important.) I thought "$ 10 $" in the statement can be reduced at first, but I didn't expect that it can be reduced to $ 4 $ !!

It seems that this problem is extremely challenging! I don't really want to try it if it is too hard. What is its difficulty relative to IMO? Thanks!

Anyone know the difficulty of this problem? Thank you very much for all your help!

Bump....

The first move is most of the difficulty of the problem. Claim: We can pair all the digits, except possibly some zeros and at most one nonzero digit, into pairs such that in each pair, the two digits are adjacent, and the left digit is nonzero. Proof. Easy; just look at consecutive blocks of nonzero digits (separated by strings of zeros). For the even length blocks, use all nonzero digits in pairs; for the odd length blocks except possibly the last one (for which there is no zero to the right), use one of the zeros from the right border. An example is shown below for illustration. \[ \boxed{13}0\boxed{46}\boxed{91}\boxed{20}000 \boxed{27}\boxed{10}\boxed{30}00000\boxed{15}3. \]$\blacksquare$ Let $t$ be the single nonzero remaining digit if it exists, otherwise, let $t = 0$. Then, let $(a_i, b_i)$ denote all the pairs, with $a_i$ being the last digit, for $1 \le i \le M$. If we commit to inserting $+$'s between any pair of digits which is not in a pair, then we will get a sum of the form \[ S(I) = t + \sum_{i \notin I} (a_i + b_i) + \sum_{i \in I} (10a_i + b_i) \]as a function of our indices $I$. The main claim is this: Claim: We can pick the set $I$ such that $S(I) = c \cdot 10^e + \varepsilon$ for some integer $1 \le c < 100$, and $0 \le \varepsilon \le 90$. In other words, $S$ has at most four nonzero digits. Proof. Define \begin{align*} X &= \sum_i \left( a_i + b_i \right) \\ Y &= \sum_i \left( 10a_i + b_i \right). \end{align*}It is easy to see $Y \ge 1.9X$, so the two leading digits of $Y$ and $X$ are different. From this it follows that the interval $[X,Y]$ contains a number of the form $c \cdot 10^e$. Now, if we imagine starting with $I = \varnothing$, so $S(I) = X+t$, and adding elements one at a time until we get $I = \{1, \dots, M\}$, where $S(I) = Y+t$. At each step, $S(I)$ increases at most $81$. So we take the first moment where $S(I) > c \cdot 10^e$, and this $I$ works. $\blacksquare$ Hence after the first step, we get a number with at most four nonzero digits; if we split all the digits after that, we get a number at most $36$. In fact, starting from any number at most $36$, two steps are sufficient to complete the problem.

Let our number have $N$ nonzero digits. We focus on the first move. Find some digit $d$ which occurs $M \geq N/10$ times (obviously this exists). From right to left, create disjoint blocks of two adjacent digits such that the leftmost digit is $d$; this gives us at least $\lfloor M/2\rfloor$ blocks. First place a plus sign between every digit, letting the temporary sum be $S$. Now, removing a plus sign between two digits in a block increases the sum by $9d$, so we can obtain the numbers $S,S+9d,\ldots,S+9d\lfloor M/2\rfloor$. Because $d \leq 9$, there exists some $0 \leq k \leq \lfloor M/2\rfloor$ such that $S+9dk$ modulo $10^{\lfloor \log_{10}(M/2)\rfloor}<M/2$ belongs to $\{0,1,2,3,4\}$—more concretely, we can find $k$ such that $S+9dk$ leaves a remainder of $S\%\gcd(d,10) \leq 4$. On the other hand, we have $$S+9dk \leq S+9d\lfloor M/2\rfloor \leq 9N+81\lfloor M/2\rfloor \leq 10^3M,$$so $S+9dk$ will have at most $9$ (less, but I don't care) nonzero digits, followed by a bunch of zeroes, ending in some digit in $\{0,1,2,3,4\}$. The second number formed will have at most $10$ nonzero digits. Now just place a plus sign between every digit to obtain a third number at most $90$, do it again to get a fourth number at most $17$, and do it one more time to guarantee a $1$-digit number after five steps. $\blacksquare$

In fact, four steps are enough. Let the starting number be $a_1a_2\dots a_n$ with $a_1\neq 0$ and $N=\sum a_i$. If $N\le 1000$, then we can move from $n$ to $N$ and get to a single digit in at most four moves. So assume $N>1000$. Perform the following algorithm: start with choosing the leftmost $a_i\ge 1$ which is not marked. Make the triple $\{a_i,a_{i+1},a_{i+2}\}$ and mark all of these three. Note that since there are at least $\frac{N}{9}$ non-zero digits, we can form at least $\frac{N}{27}-1$ triples. Now start with putting pluses in all places, so $S=a_1+a_2+\dots+a_n = N$ initially and in each step, choose a triple $\{a_i,a_{i+1},a_{i+2}\}$ which is not chosen and make $a_i+a_{i+1}+a_{i+2} \mapsto a_ia_{i+1}a_{i+2} = 100a_i+10a_{i+1}+a_{i+2}$. In each step, $S$ increases by $99a_i+9a_{i+1}$ which is at least $99$ and at most $972$. So while doing these operations, our sum $S$ will increase from $N$ to at least $N + 99\left(\tfrac{N}{27}-1\right) > 2N$. Consider the first moment the first digit of $S$ changes, at this moment $S$ will have at most four non-zero digits. We stop there and move from $a_1a_2\dots a_n$ to $S$. Put pluses in all places between digits of $S$ and we obtain a number which is at most $36$. After two more operations, we're left with a single digit, so we're done.