Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2020 INMO Problems/Problem 3

Revision as of 12:25, 5 November 2020 by Ftheftics (talk | contribs) (→‎Solution(1))

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 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)

$\boxed{\text{Definition}}$. 
Let,$A=\{ 0,1,2,\cdots ,9\}$.Call as subset $\mathcal{S}$ of $A$ $\textbf{achivable}$ 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$\mathcal{S} \subset A$ is $\textbf{not achivable}$ if $|\mathcal {S}| \le 4$.


$\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$|\mathcal{S}|<4$.

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_INMO_Problems/Problem_3&oldid=136604"