Problem
Source: IMO ShortList 1998, number theory problem 7
Tags: number theory, sum of digits, Digits, Divisibility, IMO Shortlist
22.10.2004 18:18
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
05.06.2009 10:11
We prove by induction. First we prove for $ 3^k$ digits. In this case we claim $ 3^k$ $ 1$s will satisfy the sequence. $ 111 = 37*3$, so it is true for $ k = 1$. Assume it is true for $ k$. Then $ 3^k|\frac {10^{3^k} - 1}{9}$. So we need to prove $ 3^{k + 1}|\frac {10^{3^{k + 1}} - 1}{9} = (\frac {10^{3^k} - 1}{9})(10^0 + 10^k + 10^{2k})$. We have $ 3^k$ divides what is in the first parentheses, and $ 3$ divides what is in the second, since the sum of the digits of it is $ 3$. so $ 3^{k + 1}$ divides this and we are done. Now we subtract a number $ m$ from $ 3^k$ $ 1$s such that the sum of the digits is still $ 3^k$, but there is one less digit, and the number is still divisible by the sum of its digits. To do this, first remove the first $ 1$, i.e. subtract $ 10^{3^{k - 1}}$. Now we need to add $ 10^a$ such that $ 3^k|10^a - 10^{3^{k - 1}} = 10^a(1 - 10^{3^{k - 1} - a})$ which is equivalent to $ 3^k|(10^{3^{k - 1} - a} - 1)$, which is just $ 3^{k - 1} - a$ $ 9$s. Since $ 3^k|\frac {10^{3^k} - 1}{9}$, $ 3^k|10^{3^{k - 2}} - 1$. So let $ 3^{k - 1} - a = 3^{k - 2}$, i.e. $ a = 3^{k - 1} - 3^{k - 2}$. So we just subtract $ m$ which will cause a $ 1$ further on to increase to $ 2$, reducing the number of the digits by $ 1$ but retaining the divisibility by the sum of the digits. If the first digit is $ 2$, we subtract $ m$ twice, if it is $ 3$ we subtract $ m$ $ 3$ times which will cause a $ 1$ further on to increase to $ 4$ and so on. We will never be forced to add $ 1$ to a digit which is already $ 9$, since we can terminate the process when all digits are $ 9$, which is when there are $ 3^{k - 1}$ digits. This is because $ \frac {3^k}{3^k - 1 - (3^k - 3^{k - 2} - 1)} = 9$, so when each time we remove the front digit we add to the digit $ 1/9$th of the length of the original number along from the digit we subtracted, meaning we will end with $ 3^{k - 1}$ $ 9$s. So since this is true for all numbers of the form $ 3^k$, and all numbers between $ 3^k$ and $ 3^{k + 1}$ it is true for all $ n$
05.12.2009 16:42
I'm confused about this solution. Can you apply the process to 111111111?
23.12.2009 04:14
I'll rewrite the proof since the version above has a number of typos which cause it to be very confusing. We prove by induction. First we prove for $ 3^k$ digits. In this case we claim $ 3^k$ $ 1$s will satisfy the sequence. $ 111 = 37*3$, so it is true for $ k = 1$. Assume it is true for $ k$. Then $ 3^k|\frac {10^{3^k} - 1}{9}$. So we need to prove $ 3^{k + 1}|\frac {10^{3^{k + 1}} - 1}{9} = (\frac {10^{3^k} - 1}{9})(10^0 + 10^k + 10^{2k})$. We have $ 3^k$ divides what is in the first parentheses, and $ 3$ divides what is in the second, since the sum of the digits of it is $ 3$. so $ 3^{k + 1}$ divides this and we are done. Now consider the $ q$ digit long number between $ \frac {10^{3^k} - 1}{9}$ and $ \frac {10^{3^{k - 1}} - 1}{9}$ which works. We construct a number of $ q - 1$ digits which works. We claim subtracting a multiple of $ m = 10^{3^k - r} - 10^{3^k - r - 3^{k - 2}}$ preserves both the sum of the digits and the property that the number is divisible by its digits, where $ r-1$ is the number of digits less than $ 3^k$ we have. Indeed, it is clear that subtracting $ m$ (or a multiple of $ m$) preserves the sum of the digits, since it increases one digit by one and decreases another by $ 1$. Also, $ 3^k$ divides our number to start with by the inductive hypothesis, and $ 3^k|10^{3^k - r} - 10^{3^k - r - 3^{k - 2}}$ is equivalent to $ 3^k|10^{3^{k - 2}} - 1$ But this is clear since we established above that $ 3^k|\frac {10^{3^k} - 1}{9}$./ We will never be forced to add $ 1$ to a digit which is already $ 9$, since we can terminate the process when all digits are $ 9$, which is when there are $ 3^{k - 1}$ digits. This is because $ \frac {3^k}{3^k - r - (3^k - 3^{k - 2} - r)} = 9$, so when each time we remove the front digit we add to the digit $ 1/9$th of the length of the original number along from the digit we subtracted, meaning we will end with $ 3^{k - 2}$ $ 9$s. So our construction is essentially as follows: look at a number of $ q$ digits with first digit $ s$ which works. subtract $ m$ $ s$ times. We now have a number of $ q - 1$ digits which works. (This fails for $ k = 1$ and $ k = 0$ since we use $ 3^{k - 2}$, but it is trivial to contruct examples for these cases) For the $ 11111111$ example we have $ 111111111$ $ 21111111$ $ 3111111$ $ 411111$ $ 51111$ (e.g. here $ r=5$, $ k=2$) $ 6111$ $ 711$ $ 81$ $ 9$ (although we can stop when we reach $ 6111$ since $ 3$ digits is already a power of $ 3$)
09.01.2010 11:55
Wow,very nice solution!Thank you so much! Here are two solutions(the second is the official one)
Attachments:



04.10.2015 12:51
wrong $$ $$
16.11.2019 16:50
Suppose $n$ is sufficiently large such that $n \geq 9(2+\lceil \log_2{n} \rceil)$( roughly something like $n \geq 81$ will work, though this can be optimised to be lower). First of all, consider a number with $(2+ \lceil \log_2(n)) \rceil)$( we will call this number $k_n$ from now on) digits, such that none are zero, such that this number is a multiple of $2^{k_n}$( it is obvious that such a number exists, we can for instance make one which has digits $1$ and $2$ only).Because $n$ is sufficiently large, one can obviously make an $n$ digit number which has all nonzero digits, whose digit sum is $2^{k_n}$ and whose last $k_n$ digits are the same as that of the number we chose. Clearly, this number works. So we are finished for the problem if $n \geq 81$. The rest can be made through examples. For completeness, here are the examples for $n=1$ to $80$( which also shows a way for a second construction): $n=1$ to $10$: $1,12,132,1212,22225,222222,1111112,33333325,333333333,3333311125$ $n=11$ to $20$: $33322211125,333221111125,3332111111125,33311111111125$ and this pattern(digit sum $25$, last $2$ digits $25$) can be followed up to $n=20$. $n=21$ to $70$ Here we can make numbers with last two digits $25$ and digit sum $75$. This pattern can take us up to $70$. $71$ to $80$: Make numbers with last $3$ digits $125$ and digit sum $375$. Using this strategy and extending it can be a second way to find a construction. Proved.
05.05.2021 04:10
The base cases are easy. Indeed, it is possible to see that $1$, $12$, $112$, $4112$ work. For the next numbers, we will define a infinite sequence $(a_1,a_2,a_3,...)$. Let $a_1= 1136$. We define $a_n = a_{n-1}+10^{n+2}c$, where we pick $c=1$ if $a_{n-1} \equiv 2^{n+2} $ (mod $2^{n+3}$) and $c=2$ if $a_{n-1}. \equiv 0 $ (mod $2^{n+3}$ ). Hence, $2^{n+3} \mid a_n$ for all $n$. It is well-known that $2^k \mid x$ if and only if the last $k$ digits of $x$ are divisible by $2^k$. So we will construct a number with $a_n$ as it`s last $n+3$ digits and we will make the sum of all digits to be $2^{n+3}$ Observe that if $x=(11...11(a_n))$ and $s(t)$ be the sum of digits of the number $t$, hence the largest number of digits we can make with $a_n$ is $2^{n+3}- s(a_n)$ So we only have to verify if $$ 2^{n+3}-s(a_n) +(n+3) \geq \lfloor \frac{2^{n+4}-s(a_{n+1})}{9} \rfloor +(n+4)$$That is, if we can make larger and larger numbers picking $a_{n+1}$. But this is inequality is obvious, since $s(a_{n+1})$ grows at most $2$ at time.
25.06.2023 22:14
For $n=1$ use $1$, for $n=2$ use $12$, for $n=3$ use $112$. Let the current number be $k_n$, so $k_3=112$. We will separate the numbers starting from $k_3$ into the free part $a_n$ and the rigid part $b_n$. For $n=3$, let $a_n=1$ and $b_n=12$. We can get $k_n$ by concatenating $a_n$ and $b_n$. We will use an algorithm to generate $a_{n+1}$ and $b_{n+1}$ from $a_n$ and $b_n$. - If $a_n$ is not a string of $1$s, subtract $1$ from a digit that is not yet $1$ and put a $1$ at the beginning of $a_n$ to get $a_{n+1}$, and let $b_{n+1}=b_n$. - Otherwise, let the length of $b_n$ be $t$. Putting a $1$ or a $2$ at the beginning of $b_n$ will result in it having a $\nu_2$ of $t$ or at least $t+1$, so choose the one that gets it at least $t+1$, and that's our new $b_{n+1}$. Multiply $a_n$ by $9$ then keep docking off $1$s off non-$1$s(starting from the least significant digit first, say) until the sum of its digits plus the sum of the digits of $b_{n+1}$ is exactly $2^{t+1}$, and that's our $a_{n+1}$. For the sake of clarity, here are the first few terms of $a_i$, $b_i$, and $k_i$: \begin{tabular}{l|l|l|l} $n$ & $a_n$ & $b_n$ & $k_n$ \\ \hline $3$ & $1$ & $12$ & $112$ \\ \hline $4$ & $4$ & $112$ & $4112$ \\ \hline $5$ & $13$ & $112$ & $13112$ \\ \hline $6$ & $112$ & $112$ & $112112$ \\ \hline $7$ & $1111$ & $112$ & $1111112$ \\ \hline $8$ & $7111$ & $2112$ & $71112112$ \\ \hline $9$ & $16111$ & $2112$ & $161112112$ \\ \end{tabular} After solving the problem, I wrote code to test that it works and to hopefully make my solution clearer. def helper(n): if n <= 2: raise Exception("pet the catloe") if n == 3: return [1,12] a,b = helper(n-1) firstCase = False for i in range(len(str(a))): if str(a)[i] != "1": firstCase = True a = list(str(a)) a[i] = str(int(a[i])-1) a = "".join(a) a = "1" + a a = int(a) break if firstCase: return [a,b] # We are in the second case b1 = int("1"+str(b)) b2 = int("2"+str(b)) newB = "" if b1 % (2**len(str(b1))) == 0: newB = b1 else: newB = b2 newB = str(newB) a = "9"*len(str(a)) while sum(int(x) for x in a) + sum(int(x) for x in newB) > 2**len(newB): for i in range(len(a)-1,-1,-1): if a[i] == "1": continue a = list(a) a[i] = str(int(a[i])-1) a = "".join(a) break return [int(a), int(newB)] def solve(n): if n == 1: return 1 if n == 2: return 12 a,b = helper(n) return int(str(a)+str(b)) for n in range(1,31): answer = solve(n) if answer % sum(int(x) for x in str(answer)) == 0: print(answer,"is valid for n =",n) else: print(answer,"is INVALID for n =",n)def helper(n): if n <= 2: raise Exception("pet the catloe") if n == 3: return [1,12] a,b = helper(n-1) firstCase = False for i in range(len(str(a))): if str(a)[i] != "1": firstCase = True a = list(str(a)) a[i] = str(int(a[i])-1) a = "".join(a) a = "1" + a a = int(a) break if firstCase: return [a,b] # We are in the second case b1 = int("1"+str(b)) b2 = int("2"+str(b)) newB = "" if b1 % (2**len(str(b1))) == 0: newB = b1 else: newB = b2 newB = str(newB) a = "9"*len(str(a)) while sum(int(x) for x in a) + sum(int(x) for x in newB) > 2**len(newB): for i in range(len(a)-1,-1,-1): if a[i] == "1": continue a = list(a) a[i] = str(int(a[i])-1) a = "".join(a) break return [int(a), int(newB)] def solve(n): if n == 1: return 1 if n == 2: return 12 a,b = helper(n) return int(str(a)+str(b)) for n in range(1,31): answer = solve(n) if answer % sum(int(x) for x in str(answer)) == 0: print(answer,"is valid for n =",n) else: print(answer,"is INVALID for n =",n)RunResetPop Out /
04.08.2023 12:41
Lemma: For any n and any s, such that n<=s<=9*n, there exists a n-digit number with digit sum s. Proof: This is trivial: Use 11111…111 with n digits, and keeping adding one to a non-9 digit you pass through s by IVT on the way to 999…999. Fix n, the number of digits. Let k=floor(log2(5*n)). We will show that there exists a number of k digits, divisible by 2^k, which does not contain any zeros. Suppose the decimal representation of k contains t digits. Start with the string s=0000…000[2^k], k-t zeros at the front to make n digits in total. Here [2^k] is the decimal representation of 2^k. For each zero, starting from the right, we greedily make a new string s’, with that zero having been plugged in with some other digit, and no more zeros created to the right. At a certain step, suppose the latest zero in the number is in the 10^r place (as in, units place tens place hundreds place etc). Now add 10^r * 2^k to the number. This ends in r zeros, so no digit after is affected. The new number s’ is also divisible by 2^k iff s was, as we only ever added multiples of 2^k. We keep doing this until the last n digits of the new s are 0, which will happen eventually as s has only finitely many digits. At this time s will have at most k+t+1 digits. This is because we never modified digits before the k+t+1 th from the end. (the real point of the proof is that the effect on # of digits and sum of digits for large n of the last k digits is negligible) Now consider the new s’, let it be o. Suppose o has p digits, k<=p<=k+t+1, and has a digit sum of S. We want the total digit sum to be 2^k, with n digits. We need to prove that (n-p)<=2^k-S<=9(n-p). S<=(k+t+1)9 <= 18k. (as t<k) We bound on 2^k. 2.5n<=2^k<=5n 2.5n-18k<=2^k-S<=5n-18k we just must prove that (n-p) <= 2.5n-18k (inequality 1) and that 5n-18k<=9(n-p) (inequality 2) then we would be done by the lemma. To prove inequality 1, n-p <= 2.5n-18k -p<=1.5n-18k If 1.5n>=18*floor(log2(5n)), this is trivially true. 5n-18k<=9n-9p (inequality 2) -18k <= 4n-9p well here, p<=2k as k+t+1<2k so RHS >= 4n-18k >= LHS as n is positive. So inequality 2 is always true. Now for inequality 1: 1.5n>=18*floor(log2(5n)) n >= 12*floor(log2(5n)) n >= 12*floor(log2(n))+36 If n>108 this is trivial to prove using induction. So the proof is complete with some small case checking (only 108 cases). These are solutions for 9 to 108, generated with this python program (with 1 to 8 added without the program) from math import *from copy import *def genersum(numdig, sumdig): orsumdig=copy(sumdig) ornumdig=copy(numdig) #generate number with numdig digits, summing to sumdig number='' for i in range(copy(numdig)): numdig-=1 number+=str(min(9,sumdig-numdig)) sumdig-=int(number[-1]) if sumdig<0: return '-1' if sum(map(int,number))!=orsumdig or len(number)!=ornumdig: #print(sum(map(int,number)),len(number)) return '-1' #impossible return numbern=124 #number of digitsk=9 #widthdef solve(n): #n is the number of digits k=floor(log2(5*n)) u=2**k t=floor(log10(u))+1 s=str(u) cur=u st=str(cur).zfill(k) while 1: if '0' not in st[-k:]: break tau=k-st.rfind('0') cur+=10**tau * u st=str(cur).zfill(k) su=sum(map(int,str(cur))) remsu=u-su remd=n-len(str(cur)) rest=genersum(remd,remsu) if rest=='-1': return -1 ans=rest+str(cur) ch1=(int(ans)%sum(map(int,ans)))==0 ch2=(len(str(ans)))==n ch3='0' not in ans if ch1 and ch2 and ch3: return ans return -1for i in range(1,1000): print(i,solve(i))from math import * from copy import * def genersum(numdig, sumdig): orsumdig=copy(sumdig) ornumdig=copy(numdig) #generate number with numdig digits, summing to sumdig number='' for i in range(copy(numdig)): numdig-=1 number+=str(min(9,sumdig-numdig)) sumdig-=int(number[-1]) if sumdig<0: return '-1' if sum(map(int,number))!=orsumdig or len(number)!=ornumdig: #print(sum(map(int,number)),len(number)) return '-1' #impossible return number n=124 #number of digits k=9 #width def solve(n): #n is the number of digits k=floor(log2(5*n)) u=2**k t=floor(log10(u))+1 s=str(u) cur=u st=str(cur).zfill(k) while 1: if '0' not in st[-k:]: break tau=k-st.rfind('0') cur+=10**tau * u st=str(cur).zfill(k) su=sum(map(int,str(cur))) remsu=u-su remd=n-len(str(cur)) rest=genersum(remd,remsu) if rest=='-1': return -1 ans=rest+str(cur) ch1=(int(ans)%sum(map(int,ans)))==0 ch2=(len(str(ans)))==n ch3='0' not in ans if ch1 and ch2 and ch3: return ans return -1 for i in range(1,1000): print(i,solve(i))RunResetPop Out /
10.10.2023 21:57
By LTE, $\nu_3(\tfrac19(10^n-1))=\nu_3(n)$, so $3^k\mid \underbrace{111\dots 1}_{3^k \text{ 1s}}$. We also know that by LTE, $10^{2\cdot 3^{n-1}}\equiv 10^{3^{n-1}}\equiv 1\pmod {3^{n}}$ for all $n\ge 2$. We can now proceed with the proof for non-powers of $3$. Let $3^k$ be the smallest power of three larger than $n$. Suppose $2\cdot 3^{k-1}\le n\le 3^{k}-1$. We begin with the number \[\frac{1}{9}(10^n-1)=\sum_{i=0}^{3^k-1}{10^i}\]We will modify this number while keeping the sum of digits equal to $3^k$ and also keeping the number itself divisible by $3^k$. Consider the number $10^{n+i}-10^{n+i-2\cdot 3^{k-1}}$ for some nonnegative integer $i\le 3^k-n-1$. Since $3^k\mid 10^{2\cdot 3^{k-1}}-1$, we have $3^k\mid 10^{n+i}-10^{n+i-2\cdot 3^{k-1}}$ by multiplying by $10^{n+i-2\cdot 3^{k-1}}$, which is an integer because of our definitions. Indeed, we have that the following number is divisible by $3^k$: \begin{align*} \sum_{i=0}^{3^k-1}{10^i}-\sum_{i=0}^{3^k-n-1}{10^{n+i}-10^{n+i-2\cdot 3^{k-1}}} &= \sum_{i=0}^{3^k-1}{10^i} - \sum_{i=n}^{3^k-1}{10^i} + \sum_{i=n-2\cdot 3^{k-1}}^{3^{k-1}-1}{10^i} \\ &= \underbrace{111\dots 1}_{n \text{ 1s}} + \underbrace{111\dots 111}_{3^k-n \text{ 1s}}\underbrace{000\dots 0}_{n-2\cdot 3^{k-1} \text{ 0s}} \end{align*}Which clearly has $n$ digits, as required. For example, when $n=2\cdot 3^{k-1}$, this number is \[\underbrace{111\dots 1}_{3^{k-1} \text{ 1s}}\underbrace{222\dots 2}_{3^{k-1} \text{ 2s}}\]Note that we are just moving a number of contiguous ones right $2\cdot 3^{k-1}$ place values to make the new number have $n$ digits. When $3^{k-1}\le n\le 2\cdot 3^{k-1}-1$, we can do the same thing but moving right $3^{k-1}$ place values. Since the writeup process is tedious and it is isomorphic to the previous case, I will not write it all out. Have an example instead: \begin{eqnarray*} f(9)&=&111111111 \\ f(8)&=&11111211 \\ f(7)&=&1111221\\ f(6)&=&111222\\ f(5)&=&11322\\ f(4)&=&1332\\ \end{eqnarray*}