2020 INMO Problems/Problem 3

PROBLEM

Let $S$ be a subset of $\{0,1,2,\cdots ,9\}$ . Suppose there is a positive integer $N$ such that for any integer $n>N$ , one can find positive integers $a,b$ so that $n=a+b$ and all the digits in the decimal(Base 10) representations of $a,b$ (expressed without leading zeros) are in $S$ . Find the smallest possible value of $|S|$ .

$\emph{Proposed by Sutanay Bhattacharya}$

Solution(1)

. 
Let,.Call as subset  of   if it follows the said property.

i.e for any natural $n>1$ ,it can be represented as sum of two natural $a,b$ such that degits in decimal representation of $a,b$ always $\in \mathcal{S}$ .

$\boxed{\text{Claim}}$

For any is  if .

$\textbf{Proof.}$

Let,s cheak for $|\mathcal {S} |=4$ .

Suppose, $\mathcal{S}= \{s_1,s_2,s_3,s_4\}$ .

So ,All elements of $\mathcal{S}$ are distinct mod 10. Now, suppose $B=\mathcal{S} *\mathcal{S}=\{x:x=s_i+s_j \pmod{10} ,1\le i,j \le 4\}$ .

now , $B$ has atmost $8$ elements .But we have $10$ distinct congruence modulo 10.

So,it can not cover all natural $n>1$ .

Similar argument for.

So,These contradiction prove our claim . Now ,Look for $|\mathcal{S}|=5$ . In this case we get 10 distinct congruence modulo 10. So ,we can guess that $|\mathcal{S}| \ge 5$ are $\textbf{ achivable}$ .

Now ,take an example as everyone above has taken $\mathcal{S}=\{ 0,1,2,5,8\}$ . ~trishan So, we are done with this!

Solution(2)

The answer is $5$ . First, we show this is achieved. Consider $S = \{0,1,2,3,7\}$ . Since $0+0=0, 0+1=1, 1+1=2, 1+2=3, 2+2=4, 2+3=5, 3+3=6, 0+7=7, 1+7=8,$ and $2+7=9$ , so all digits can be split individually. The only case any problem can arise is when we try to split $n$ as $a+b$ and end up with one of $a$ or $b$ equal to $0$ . If $n$ has any of the digits $2,3,4,5,7,8,9$ , or has at least two non-zero digits, then this problem won't arise. The only cases where a problem can arise is when $n=10^k$ or $n=7 \cdot 10^k$ for some non-negative integer $k$ . We take $N=11$ . Then $k \ge 1$ . But then

$10^k = 777 \cdots 7 + 22 \cdots 23$ and $7 \cdot 10^k = 3777 \cdots 7 + 322 \cdots 23$

Now, we claim $|S| \ge 5$ for any "good" subset $S$ . Suppose a good subset $S$ with $4$ elements exists. Note that there are $\binom{4}{2} + 4 = 10$ different additions possible. The sums $i+j$ should clearly be distinct modulo $10$ . This means that for any $X > N$ , the $a$ and $b$ that exist for $X$ are [b]unique upto a switch [/b] of the corresponding digits between $a$ and $b$ (just keep going from the units digit to the most significant digit sequentially, observing that upto a switch, the digits we choose for $a$ and $b$ are unique). But then, for any digit $d \in \{0,1,\cdots, 9\}$ , consider $Y_d = dX$ obtained by putting the digit $d$ in front of $X$ . By the "uniqueness" mentioned before, the digit $d$ must be formed by the addition of two digits in $S$ .

Therefore, all digits from $0$ to $9$ can be obtained by summing two digits in $S$ (and not just $\pmod {10}$ ). This means no number in $S$ can be $\ge 5$ (otherwise that number added to itself gives a number greater than $10$ ). But then $9$ cannot be formed by adding two digits in $S$ . We have arrived at a contradiction.

Page

Toolbox

Search

2020 INMO Problems/Problem 3

PROBLEM

Solution(1)

Solution(2)