Zi Song's bound

Claim: For integers $a, b$ , we have $S(ab) \leq S(a) S(b)$ .
This can be shown by considering the digit expansion. Let $a = \sum a_i 10^i, b = \sum b_i 10^i$ , then $ab = \sum_i \left[ \sum_{0\leq k \leq i} a_{k} b_{i-k} 10^i \right]$ . As such, $S(ab) \leq \sum_{i} \left [ \sum_{0 \leq k \leq i} a_k b_{i-k} \right] = S(a) S(b)$ .

Claim: $S(10x) = S(x)$ .
This is obvious, since $10x$ is just $x$ with a $0$ appended to the end.

Thus, $S(5x) \leq S(5) S(x) = 5 S(x)$ , so $\frac {S(x) }{S(5x) } \geq \frac {1}{5}$ . Equality holds when $x=1$ (and possibly other cases), so we have $X = \frac {1}{5}$ .
Also, $S(x) = S(10x) \leq S(2) S(5x) = 2 S(5x)$ , thus $\frac {S(x) }{S(5x)} \leq 2$ . Equality holds when $x=2$ (and possibly other cases), so $Y=2$ .
Thus, $X +Y = \frac {11}{5}$ , so $a+b=11+5=16$ .

Let $n = \sum_{k=1}^m a_{k} 10^{k-1}$ where $a_{k}$ is the kth digit of n, $0≤ a_{k}≤9$ and m is the number of digits. Then $S(n) = \sum_{k=1}^m a_{k}$ . We write $5n = \sum_{k=1}^m 5a_{k} 10^{k-1} = \sum_{k=1}^m (b_{k} 10^{k} + c_{k} 10^{k-1})$ where $5a_{k}=10b_{k}+c_{k}$ . Now we note that $c_{k}$ is either 5 or 0 and $0≤b_{k}≤4$ (because $5 \times 9 = 45$ ). So for every k we have $c_{k+1}+b_{k}<10$ which allows us to write: $S(5n)=\sum_{k=1}^m S(5a_{k})$ . Lets look at $S(5a_{k})$ . If $a_{k}$ is even $c_{k}=0$ and $0≤b_{k}≤4$ . In general we find that if $a_{k}$ is even $S(5a_{k}) = \frac{a_{k}}{2}$ . If $a_{k}$ is odd $c_{k}=5$ and $0≤b_{k}≤4$ . In general we find that if $a_{k}$ is odd $S(5a_{k}) = \frac{a_{k}-1}{2}+5$ . Let $j$ be the number of even numbered digits of n and without loss of generality we can assume that $a_{1},a_{2},a_{3},...,a_{j}$ are even and $a_{j+1},a_{j+2},a_{j+3},...,a_{m}$ are odd. Then we have:

$\frac{S(n)}{S(5n)}=\frac{S(n)}{(S(5a_{1})+S(5a_{2})+S(5a_{3})+...+S(5a_{j}))+(S(5a_{j+1})+S(5a_{j+2})+S(5a_{j+3})+...+S(5a_{m})}$

$=\frac{S(n)}{( \frac{a_{1}}{2}+\frac{a_{2}}{2}+\frac{a_{3}}{2}+...+\frac{a_{j}}{2})+( \frac{a_{j+1}-1}{2}+5+\frac{a_{j+2}-1}{2}+5+\frac{a_{j+3}-1}{2}+5+...+\frac{a_{m}-1}{2}+5)}$

$=\frac{S(n)}{\frac{1}{2}(a_{1}+a_{2}+a_{3}+...a_{j})+(\frac{a_{j+1}}{2}+\frac{a_{j+2}}{2}+\frac{a_{j+3}}{2}+...+\frac{a_{m}}{2}+(5-\frac{1}{2})(m-j))}$

$=\frac{S(n)}{\frac{1}{2}S(n)+\frac{9}{2}(m-j)} =\frac{2}{1+\frac{9(m-j)}{S(n)}}$

To find the maximum value of $\frac{S(n)}{S(5n)}=\frac{2}{1+\frac{9(m-j)}{S(n)}}$ we try to find the minimum value of $\frac{9(m-j)}{S(n)}$ $(1)$ . The numerator of $(1)$ is zero when $m=j$ that is when all the digits of n are even. That gives us $Y=\frac{2}{1+\frac{9(0)}{S(n)}}=2$ . To find the minimum value of $\frac{S(n)}{S(5n)}$ we try to find the maximum value of $(1)$ . Maximum value of the numerator in $(1)$ is when j=0 which tells us that the digits of n are odd. The denominator is the smallest when the sum of n's digits is the smallest, which is when all the digits are 1. That will give $S(n)=m$ and therefore $X=\frac{2}{1+\frac{9(m)}{m}}=\frac{2}{10}=\frac{1}{5}$ . If $1 \leq j \leq m-1$ then $0 < m-j < m$ so any mix of even and odd digits will give $(1)$ a value between $X$ and $Y$ .

In order to find the minimum, we minimize S(n) as much as possible so we plug in n = 1 and 5n = 5, and we get sums of each respectively, 1 and 5 implying that S(n)/S(5n) = 1/5. Using other cases, we found out that for other integers that the maximum value for S(n)/S(5n) is 2 for one-digit integers n = 2, 4, 6, and 8. Evaluating 1/5 + 2 = 1/5 + 10/5 = 11/5. Hence, 11+5 = 16.

But how were we able to get 2 as maximum and 1/5 as minimum? Since for all positive integers ranging, there are infinite positive integers but since we are given a fraction which may have its minimum and maximum. When finding the minimum, we make sure the integers we are choosing are as much as possible minimized. So, hence, the minimum 1/5.

But how about the maximum, we can't maximize the integers, remember that we are dealing with fractions. Also, talking about sum of the digits, there may be possible values for the numerator and denominator, numerator can range from 1 to infinity (ranging for all positive integers), but let's take case by case.

For example, a 3-digit number can have its sum ranging from 1 to 27 and since depending on the numerator, the sum of its digits may differ i.e. all even digits in the numerator must have sum of its digits when multiplied by 5 halved.

Write $n=\sum a_i10^i.$ It's easy to show that (convince yourself of this, it is quite simple!) $S(5n)=S\left(\sum 5a_i10^i\right)=\sum S(5a_i10^i)=\sum S(5a_i).$ For example, $18=S(5\cdot 1458)=S(5\cdot 1)+S(5\cdot 4)+S(5\cdot 5)+S(5\cdot 8)=S(5)+S(20)+S(25)+S(40)=5+2+7+4=18.$ Now we want the min and max of $\frac{S(n)}{S(5n)}=\frac{\sum S(a_i)}{\sum S(5a_i)}.$ Remark that $\min \left(\frac{S(a_i)}{S(5a_i)}\right )\leq \frac{\sum S(a_i)}{\sum S(5a_i)} \leq \max \left(\frac{S(a_i)}{S(5a_i)}\right ).$ It's easy to check that for digits $a_i$ , $\min \left(\frac{S(a_i)}{S(5a_i)}\right )=\frac{1}{5}$ and $\max \left(\frac{S(a_i)}{S(5a_i)}\right )=2.$ Thus $\frac{1}{5}\leq \frac{\sum S(a_i)}{\sum S(5a_i)} \leq 2,$ and equality is easy to achieve in both cases with $a_i=1,2$ , respectively.

There are two main steps to this problem: Finding the minimum value, and finding the maximum value. Here's how to do both.

Minimum Value -->

Since the problem specifies positive integers, the minmum value of S(n) is 1. When S(n) = 1, then S(n) = 5 - This will also hold when n is 10 or 50, among other values.

So the minimum value, X, is $\frac{1}{5}$ .

Maximum Value -->

The maximum value can be obtained with a simple guess-and-check synopsis of the first 9 natural numbers. 1 gives us 0.2; 2 gives us 2. If you look further down the number scale, you'll find that it is impossible to obtain a greater value than 2.

Therefore, the maximum value, Y, is 2.

Putting It All Together...

X + Y = $\frac{1}{5}$ + 2 = $\frac{11}{5}$

So the final answer is 11 + 5, which equals 16 .

As everyone else probably did, I started plugging in values and noticing that $\frac{1}{5}$ is the minimum and $2$ is the maximum value for $\frac{S(n)}{S(5n)}$ . Of course, since we're mathematicians, we can't make that claim until we prove it.

What we want to prove is $\frac{1}{5} \leq \frac{S(n)}{S(5n)} \leq 2$ . Before we go on to the actual proof, let's see what happens when we multiply a number by 5.

Consider a number $n=\overline{a_1a_2a_3...a_k}$ , where k is the natural number denoting the number of digits of $n$ .
Let $5n=\overline{b_1b_2b_3...b_kb_{k+1}}$ , where $b_{k+1} \in \{ 0, 1 , 2, 3, 4 \}$ .
Notice that the digit $b_0$ can be written as $r_0$ , where $r_0 = 5$ if $a_0$ is odd and $r_0 = 0$ if $a_0$ is even.
For $i \in \{1, 2, 3, ... , k\}$ , $b_i$ can be written as $b_i=r_i + \lfloor{a_{i-1}/2} \rfloor$ , where, again, $r_i = 5$ if $a_i$ is odd and $r_i = 0$ if $a_i$ is even. What this actually means is that the i-th position of the number $5n$ is the sum of the number we carried over from the previous position and the last digit of $5a_i$ .
For $i = k+1$ , we have $b_{k+1}= \lfloor{a_{k}/2} \rfloor$ .

Now, let's prove the left side of the inequality, which is equivalent to $\sum\limits_{i=0}^{k} (r_i + \lfloor{a_{i}/2} \rfloor) \leq 5\sum\limits_{i=0}^k a_i$ . Moving this around, we get $\sum\limits_{i=0}^{k} r_i \leq \sum\limits_{i=0}^k (5a_i - \lfloor{a_{i}/2} \rfloor)$ , which holds because for each $i$ , $r_i \leq 5a_i - \lfloor{a_{i}/2} \rfloor$ . If $a_i$ is odd, then $r_i=5$ and we get $5 \leq \frac{9a_i+1}{2}$ , which is true for all odd digits, whereas if $a_i$ is even, $r_i=0$ and the inequality is reduced to $\frac{9a_i}{2} \geq 0$ , which is also true for all even digits.
So, the left side of the inequality is proven.

The proof of the right side is similar to the proof of the left, and becomes $\sum\limits_{i=0}^k r_i \geq \sum\limits_{i=0}^k (a_i - 2\lfloor{a_{i}/2} \rfloor)$ . If we compare every $r_i$ and its respective $a_i-2\lfloor{a_{i}/2} \rfloor$ , we get $0 \geq 0$ if $a_i$ is even, and $10 \geq 1$ if $a_i$ is odd.

Each digit $d$ of $n$ contribute in $S(5n)$ for :

$\frac{d}{2} + 0$ if d is even

$\left (\frac{d}{2}-\frac{1}{2} \right ) + 5$ if d is odd

(since $d \le 9$ there is no carry).

So $\boxed{S(5n) = \frac{9}{2}odd(n) + \frac{1}{2}S(n) }$ where $odd(n)$ is the number of odd digits in n

then $\boxed{ \frac{S(n)}{S(5n)} = \frac{2}{9 \frac{odd(n)}{S(n)}+1} }$

So

• min = $\frac{1}{5}$ when all digits are 0 or 1

• max = $2$ when all digits are even

Conjecture:

1. That the maximum occurs when all the digits are even or zeroes

2. That the minimum occurs when all the digits are 1s or zeroes

Proof: 1-->

Consider any number with all digits even. For example, we take 246. Multiplying by 5 means multiplying by 10/2. First, multiplying by 10 (giving 2460) doesn't have any effect on s(n), it only introduces a zero. Second, multiplying by 1/2 halves all the digits ( giving 1230). This halves s(n), and s(n)/s(5n) equals 2. Now consider changing one or more of the digits of 246 with the next odd digit. We change 6 to 7. The 0 gets added as usual, we get 2470 but dividing by 2, we get 1235. And s(n)/s(5n) becomes smaller than 2 (the numerator increased only by one while the denominator increased by 5). Adding one to any digit of an all even digit number involves an addition of 5 to s(5n). This reasoning, though non rigorous, can be applied to all even digited numbers and we see that the maximum must be 2.

2-->

In a similar manner, we take 111 for our example. Multiplying by 10 gives 1110 while dividing by 2 gives 555. The ratio we get is 3/15=1/5. Now, if we change any of the digits, say, the hundreds 1 with 3, to get 311. Multiplying by 10, we get 3110. And dividing by 2, we get 1555. S(n) increases by 2 while s(5n) by only 1. So the ratio increases. Replacement by other digits involves only half of the new digit being added to s(5n), and t hat with the possibility of decreasing s(5n) by 5(in case of replacement with an even digit). Again, this reasoning can be generalised to establish that 1/5 is the minimum.

   We have, then, X+Y = 2+1/5=11/5. And a+b= 11+5=16

So by intuition, it should not be hard for one to feel out that the minimum values should be obtained with some superset of $n = \displaystyle \sum_k 1 \cdot 10^k$ and the maximum values are obtained with some superset of $n = \displaystyle \sum_k 2 \cdot 10^k$ . We can get a very rigorous proof of this by considering the well known fact that $S(ab) \leq S(a) S(b)$ , proven by expansion. We have $S(5x) \leq 5 S(x)$ for the lower bound and $S(x) = S(10x) \leq 2 S(5x)$ for the upper bound. At this point, computing $2 + \displaystyle \frac{1}{5}$ should be trivial.

Python 3.4.2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def digitalsum(x):
    """Returns sum of digits of the number"""
    if x<10:
        return x
    else:
        return (x%10)+digitalsum(x//10)
def f(n):
    return digitalsum(n)/digitalsum(5*n)
a=[]
for i in range(1,100):
    a.append(f(n))
print(max(a)+min(a)) #Prints 2.2

#On looking at the list a, I noticed the periodicity. Thus, didnt tried for bigger values.

Let $n=\overline { { a }_{ 1 }{ a }_{ 2 }{ a }_{ 3 }... }$ . Then $S\left( n \right) ={ a }_{ 1 }+{ a }_{ 2 }+{ a }_{ 3 }...$ and $S\left( 5n \right) =S\left( 5{ a }_{ 1 } \right) +S\left( 5{ a }_{ 2 } \right) +S\left( 5{ a }_{ 3 } \right) ...$ .

In order to maximize the value of $\frac { S\left( n \right) }{ S\left( 5n \right) }$ every digit ${ a }_{ i }$ must attain the maximum value for $S\left( { a }_{ i } \right)$ and minimum for $S\left( 5{ a }_{ i } \right)$ or the opposite for minimizing.

We can easily check for which digits it occurs by simple arithmetic. For convenience let $f\left( n \right) =\frac { S\left( n \right) }{ S\left( 5n \right) }$ , we exclude $0$ as it doesn't affect neither sum.

We have that:

$f\left( 1 \right) =\frac { 1 }{ 5 }$ , $f\left( 2 \right) =2$ , $f\left( 3 \right) =\frac { 1 }{ 2 }$ ,

$f\left( 4 \right) =2$ , $f\left( 5 \right) =\frac { 5 }{ 7 }$ , $f\left( 6 \right) =2$ ,

$f\left( 7 \right) =\frac { 7 }{ 8 }$ , $f\left( 8 \right) =2$ , $f\left( 9 \right) =1$ .

From this we can see that the numerator is maximized and denominator minimized when ${ a }_{ i }=\left\{ 0,2,4,6,8 \right\}$ and the opposite when ${ a }_{ i }=\left\{ { 0 },{ 1 } \right\}$ .

Thus $Y=2$ (e.g $n=2048$ ) and $X=\frac { 1 }{ 5 }$ (e.g $n=1000110$ ).

Finally $X+Y=\frac { 11 }{ 5 }$ , so $a+b=16$ .

For minimum value take n as 1.It comes as 1/5 For maximum value take n as 2.It comes as 2 2+1/5 =11/5 Therfore a+b=16

The maximum value of the expression s(n)/s(5 n) is 2 which comes when n=2,4,6....that is at even numbers. The minimum value of this expression is 1/5 which comes for n=1,5 and so on. so x=1/5 and y=2. Hence x+y will be 11/5 (11 and 5 are coprime positive integers) Hence a=11 and b=5 and so a+b will be 16

minimum is when s(5n)=5*s(n) so minimum is 1/5 = 0.2 maximum is when the number that occurs after 5n gives a digit sum of 1 so any such number like 2 ,10 will do maximum value = 2 x+y=2+.2=2.2 x+y=11/5 = 16

The value of S(n) and S(5n) are calculated for different values of n and it is found that the ratio S(n)/S(5n) attains minimum in case of n=1 on considering the ratio for odd digits i.e 1,3,5,7 and maximum in case of all the single digit even numbers and the maximum value is two for n=2,4,6,8 and for n=9 the ratio is 1.Using all the odd digits sequentially for n i.e n=1357 the ratio is 8/13 which is far more than the ratio obtained for n=1. Similarly using all the even digits sequentially for n i.e for n=2468 the ratio is 2. Thus the sum of minimum and maximum value is given by 1/5+2=(1+10)/5=11/5. Value of a=11 and b=5 and a+b=16.

The minimum value 'X' can be got by using n=1,which gives (1/5). The maximum value 'Y' can be got by using various values for n which includes all even numbers , which gives 2. X+Y=(1/5)+2=(1/5)+(10/5)=11/5 Therefore the answer is 11+5=16.

To get X minimum of s(n)/s(5n) we want minimum s(n) which is 1 for n=1 & 10 & 100 & 1000 etc Here s(5n)=5 So X minimum of s(n)/s(5n) will be 1/5

To get Y maximum of s(n)/s(5n) we want minimum s(5n) which is 1 for n=2 & 20 & 200 & 2000 etc Here s(n)=2 So Y maximum of s(n)/s(5n) will be 2/1

So adding X and Y we get 1/5+2/1 = (1+10)/5*1 Final answer is 16

Note that the proof is incomplete as I have not proved 2 statements (1) minimum numerator gives minimum X and (2) minimum denominator gives maximum Y