My problem!

anantmudgal09 wrote: Let $S$ be a subset of $\{0,1,2,\cdots ,9\}$. Suppose there is a positive integer $N$ such that for any positive integer $n$, one can find positive integers $p,q$ so that $n=p+q$ and all the digits in the decimal representations of $p,q$ (expressed without leading zeros) are in $S$. Find the smallest possible value of $|S|$. Proposed by Sutanay Bhattacharya The actual problem statement was actually this. But yeah, they both are same.

For the exam P3, just see that $\{0,1,2\}$ or $\{0,1,3\} \subset S.$ Then show that $4$ elements in $S$ cannot span single digits numbers. Then for $|S|=5$ take $S=\{0,1,2,5,8\}.$

Ankoganit wrote: My problem!

Exactly that is what I wrote. The most easiest among all problems of the paper

..........

This was good, although still easy. Note that "{0, 1,2,3,6}" Also works.

Probably the simplest problem in the paper, but yet not a bad problem: Note that as $1=1+0=0+1$, both $1$ and $0$ must belong to $S$. Moreover, as $3=0+3=1+2$, one of $3$ or $2$ must belong to $S$. Claim: There are at least 5 elements in S. Assuming to contrary, take 2 cases: Case 1: $2$ belongs to $S$. As $5=0+5=1+4=2+3$, one of $5,4,3$ must belong to $S$. Either ways, 9 is not representable as a pairwise sum of 2 elements of set $[0,1,2,x]$, $x$ being one of $3,4,5$. Case 2: $3$ belongs to $S$. Again, as $5=0+5=1+4=2+3$, we get 9 is not representable as pairwise sum of elements of set $[0,1,3,x]$, where $x$ is one of $2,4,5$. Thus $S$ has $\geq 5$ elements, and as set $S=[0,1,2,5,8]$ clearly works, we're done.

Nice problem (although not that difficult, however, some proofs may not be rigorous enough, as the problem is better understood intuitively) My solution during the test.... We claim that the minimum number of elements in $S$ is 5. First, we prove that $|S|=4$ does not suffice. As $1$ has only one representation of the form $p+q$ That is $0+1$, we see that $0$ and $1$ belong to $S$. Also, $3$ has two possible representations, $1+2$ and $0+3$. Thus, atleast one of $2$ and $3$ belong to the set $S$. Assume $|S|=4$ Now, we take cases Case 1 $2$ and $3$ belong to $S$ The set ${0,1,2,3}$ does not satisfy the problem conditions as $9=p+q$ has no solutions. Contradiction Case 2 $2$ belongs to $S$ but $3$ does not belong to $S$. $S={0,1,2,n}$ Since $9=p+q$ must have a solution, $n$ has to be one of $9$, $8$ or $7$. Since $5=p+q$ must have a solution, $n$ has to be one of $5$, $4$ or $3$. Contradiction Case 3 $2$ does not belong to $S$ but $3$ belongs to $S$. $S={0,1,3,n}$ Since $9=p+q$ must have a solution, $n$ must be one of $9$, $8$ or $6$. Since $5=p+q$ must have a solution, $n$ must be one of $5$, $4$, or $2$. Contradiction Hence $|S| \geq 5$. We claim that $|S|=5$ is possible. Indeed, consider $S={0,1,2,3,6}$ Proceeding by induction on the number of digits - The base case is as follows $1=1+0, 2=1+1, 3=1+2, 4=2+2, 5=2+3, 6=6+0, 7=6+1, 8=6+2, 9=6+3 $. We call these representations of the digits. Assume that all $k$ digit numbers can be represented in the required form. We prove that all $k+1$ digit numbers have this property. Let $n=10a+b$ where $0\leq b \leq 9$. Let $a=p_1+q_1$ where the digits of $p_1$ and $q_1$ are in $S$. Let the representation of $b=\alpha +\beta $. Then we can write $n=(10p_1+\alpha)+(10q_1+\beta)$ where the digits of these two numbers are in the set $S$. Hence our inductive step is complete. So, the minimum value of $|S|$ is $5$, as claimed.

$\boxed{\text{Definition}}$. Let,$A=\{ 0,1,2,\cdots ,9\}$.Call as subset $\mathcal{S}$ of $A$ 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 not achivable if $|\mathcal {S}| \le 4$. 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 achivable . Now ,take an example as everyone above has taken $\mathcal{S}=\{ 0,1,2,5,8\}$. So, we are done with this! I was just finding $\mathcal{S}$ for single digits natural and suddenly observe the guess holds .

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 unique upto a switch 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. A cute problem, and my second favourite . My first thought was that this was a construction + counting problem, with the answer being $4$ (This is because a simple enumeration argument shows that $|S| \ge 4$, because $3^2 < 10$). But once I got to $|S|=4$, I quickly realised that $4$ is just too tight to work. Even in base $b$, the distinct modulo $b$ argument will always give a better lower bound ($\sim \sqrt{2b}$) than the enumeration lower bound ($\sim \sqrt{b}$).

Actually, $10^k$ can be represented as $0$ $+$ $10^k$ because $p$ and $q$ are non-negative integers. @below, Yeah OK. My Bad.

TheMathsBoy wrote: Actually, $10^k$ can be represented as $0$ $+$ $10^k$. Except in the new formulation, we are not allowed to have $a$ and $b$ to be $0$.

Sorry for the late solution, but can someone pls check? After my epic fail in INMO 2020, this problem is the only one which has kept the hope of getting atleast 17 marks burning.

I find all set problems cute. Claim 1: The value of $|S|$ must be at least $5$. Proof: For any $n>N$, and $a+b=n$, let $l_1,l_2$ be the last two digits of $a,b$ respectively. Then the set of all possible values for the last digits of $l_1+l_2$ is $\{0,1,\dots,9\}$ since $l_1+l_2\equiv n\pmod{10}$. AFTSOC that $|S|=4$, and let $S=\{a_1,a_2,a_3,a_4\}$. Then $l_1+l_2=a_i+a_j$ for $i,j\in \{1,2,3,4\}$. Since there are $\binom{4}{2}+4=10$ ways to choose the sum $a_i+a_j$ ($i,j$ may be equal), and they map bijectively to $\{0,1,\dots,9\}$ modulo $10$, it follows that none of them are equal modulo $10$. So there should be exactly $5$ even numbers out of the $10$ sums. Since $a_1+a_1$, $a_2+a_2$, $a_3+a_3$, and $a_4+a_4$ are all even, exactly one of $a_i+a_j$ where $i\neq j$ must be even. WLOG $a_1+a_2$ is even. Then $a_1+a_3$ and $a_2+a_4$ are odd. But then $a_3+a_4$ becomes even, a contradiction. The value of $|S|$ can't be less than $4$ because then we will have less than $10$ sums $a_i+a_j$ where $a_i,a_j\in S$, and won't traverse the whole of $\{0,1,\dots,9\}$. So $|S|\geq 5$. $\square$ Claim 2: A set $S$ with $|S|=5$ is possible. Proof: Consider $S=\{0,1,3,4,5\}$. Any digit can be made from these $5$ numbers without any carries, so choosing $N= 9$, for any $n>N$, and going from the right to left, for any digit $d$ in $n$, we can find $a_1,a_2\in S$ such that $a_1+a_2=d$, put $a_1$ in $a$ and $a_2$ in $b$, and continue like this to get $a+b=n$. In case we end up with one of $a,b$ zero, then $n$ must consist of only $0,1$ and $3$. In this case, if $n$ has more than one non-zero digit, then we can put two of them in $a,b$ each, so that $a,b$ are both non-zero. The other possibilities are if $n=1000\dots 0$ or $n=3000\dots 0$. Let $d(x)$ be the number of digits of $x$. In the first case, take $a=999\dots 9$ and $b=1$, with $d(a)=d(n)-1$. In the second case take $a=909090\dots 0909$ and $b=2090909\dots 9091$. with $d(a)+1=d(b)=d(n)$. $\square$ Long story short, the answer is $\boxed{5}$. $\blacksquare$

what iff i prove $|S|>=6$ but have the exact same intuition. how much marks am i expected to get

I used the set, $S=\{ 1,2,3,4,8\} $ @below, the problem posted on this forum by am09.

zephyr7723 wrote: I used the set, $S=\{ 1,2,3,4,8\} $ In the original formulation? Or the paper formulation?

How about converting to base 2 That will give just two elements 0 and 1 Then one can do binary addition etc.

anantmudgal09 wrote: 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|$. Proposed by Sutanay Bhattacharya the part "(expressed without leading zeroes)" wasn't in the question paper

a and b are nonnegative integers. Not positive.

Here is a solution which replaces Ankoganit's parity argument with a case bash. There are only $16$ cases, each of which is very easy to check. The answer is $|S| = 5$. We first show that all $|S| \leq 4$ fail. Suppose not. First, note that the sum-set $S + S$ must contain an element in each mod $10$ residue class: indeed, if not, pick a mod $10$ residue $a$ for which no element in $S + S$ is equivalent to $a$ mod $10$, and pick some large integer which ends in $a$. Note that $|S + S| \leq \binom{|S|}{2} + |S|$, so if $|S| < 4$, $|S + S| < 10$, impossible. Thus, $|S| = 4$. If $|S| = 4$, $|S + S| \leq \binom{|S|}{2} + |S| = 10$. Hence, there cannot be any two elements in $S + S$ which are equivalent mod $10$. In particular, this implies that $k$ and $k + 5$ cannot both be in $S$, as $k + k \equiv (k + 5) + (k + 5) \pmod{10}$. In addition, note that any element in $S + S$ is at most $9 + 9 = 18$. Thus, $9 \in S + S$. This implies that $S \times S$ must contain one of $(0, 9), (1, 8), (2, 7), (3, 6), (4, 5)$. Since $7 = 2 + 5$, it cannot contain $(2, 7)$. Now, we are ready to bash. In the following case bash, when we write $a = b$ we mean $a \equiv b \pmod{10}$. Suppose $S \times S$ contains $(0, 9)$. Then, $S$ cannot contain $4, 5$. Additionally, since $1 + 9 = 0 + 0$ and $8 + 0 = 9 + 9$, $S$ cannot contain $1, 8$. Finally, $S \times S$ cannot contain $(2, 7)$ or $(3, 6)$. This implies that $S \times S$ contains one of $(6, 2), (6, 7), (3, 2), (3, 7)$. The first of these is bad because $6 + 6 = 2 + 0$, the second is bad because $6 + 0 = 7 + 9$, the third is bad because $0 + 2 = 9 + 3$, and the last is bad because $3 + 7 = 0 + 0$. Thus, $S \times S$ cannot contain $(0, 9)$. Suppose $S \times S$ contains $(1, 8)$. Then, $S$ cannot contain $6, 3$; since $4 + 8 = 1 + 1$ and $5 + 1 = 8 + 8$, $S$ cannot contain $4, 5$. Since $S \times S$ cannot contain $(2, 7)$ or $(0, 9)$, it must contain one of $(0, 2), (0, 7), (9, 2)(9, 7)$. The first of these is bad because $1 + 1 = 0 + 2$, the second is bad because $7 + 1 = 0 + 8$, the third is bad because $2 + 8 = 9 + 1$, and the last is bad because $7 + 9 = 8 + 8$. Thus, $S \times S$ cannot contain $(1, 8)$. Suppose $S \times S$ contains $(3, 6)$. Then, $S$ cannot contain $1, 8$; since $0 + 6 = 3 + 3$ and $9 + 3 = 6 + 6$, $S$ cannot contain $0, 9$. Since $S \times S$ cannot contain $(2, 7)$ or $(4, 5)$, it must contain one of $(5, 2), (5, 7), (4, 2), (4, 7)$. The first of these is bad because $5 + 3 = 2 + 6$, the second is bad because $5 + 5 = 7 + 3$, the third is bad because $4 + 4 = 2 + 6$, and the last is bad because $4 + 6 = 3 + 7$. Thus, $S \times S$ cannot contain $(3, 6)$. Finally, suppose $S \times S$ contains $(4, 5)$. Then, $S$ cannot contain $0, 9$; since $6 + 4 = 5 + 5$ and $3 + 5 = 4 + 4$, $S$ cannot contain $3, 6$. Since $S \times S$ cannot contain $(1, 8)$ or $(2, 7)$ it must contain one of $(1, 2), (1, 7), (8, 2), (8, 7)$. The first of these is bad because $1 + 6 = 2 + 4$, the second is bad because $1 + 7 = 4 + 4$, the third is bad because $8 + 2 = 5 + 5$, and the last is bad because $8 + 4 = 5 + 7$. Thus, $S \times S$ cannot contain $(4, 5)$. As we have exhausted all cases, $|S| = 4$ is impossible. For $|S| = 5$, the set $\{0, 1, 2, 4, 5\}$ works: indeed, \begin{align*} 0 &= 0 + 0 \\ 1 &= 0 + 1 \\ 2 &= 1 + 1 \\ 3 &= 1 + 2 \\ 4 &= 2 + 2 \\ 5 &= 1 + 4 \\ 6 &= 1 + 5 \\ 7 &= 2 + 5 \\ 8 &= 4 + 4 \\ 9 &= 4 + 5. \end{align*}Unless all digits of an integer $n$ are $1$s or $0$s, we may find $a, b$, all of whose digits are in $S$, for which $a + b = S$, in the obvious way. If $n$ has at least two $1$'s, we may find such $a$ and $b$ by letting $a$ have a $1$ in one of the positions, and $b$ have a $1$ in the other position. If $n$ has only one $1$, $n$ is a power of $10$; in this case, we can take $a = b = \frac{n}{2}$ (as long as $n > 1$). Thus, this set $S$ indeed works, so we are done.

niyu wrote: Here is a solution which replaces Ankoganit's parity argument with a case bash.

Nice Problem.. Let $S=\{b_1, b_2,.. b_k\}$ with $2\leq k<10$ elements Such that for every element of $X$ represented as $x_n$ for $1\leq n\leq 10$ we can find $2$ elements of $S$ such that $b_i+b_j=x_n$ Or $b_i+b_j\equiv x_n\mod 10$ for $1\leq i \leq j\leq k$. Claim 1-: $k\neq 2$ If FTSOC $k=2$ then $S=\{b_1, b_2\}$ now as total number of pairs of $\{b_i, b_j\}$ we can choose from $2$ elements is $3$ so we can only cover $3$ elements of $X$ hence contradiction $k\neq 2$ Claim 2-: $k\neq 3$ FTSOC let $k=3$ then $S=\{b_1, b_2,b_3\}$ as there are $5$ odd, $5$ even elements in $X$ Now number of ways in which we can choose $2$ pairs from $3$ element is $6$ so if $k=3$ we can only cover $6$ elements and cardinality of set $X$ is $10$ which is contradiction hence $k\neq 3$ Claim 3-: $k\neq 4$ FTSOC $k=4$ then $S=\{b_1, b_2,..., b_4\}$ now as there are $5$ odd, $5$ even elements in $X$ So Either all elements of $S$ are odd or some are odd some are even or no element is odd. Now if $b_1, b_2,b_3,b_4$ are all odd then we can never ever choose $2$ ,$b_i, b_j$ such $b_i+b_j=$ Odd elements of $X$ Now if $b_1, b_2, b_3$ are odd and $b_4$ is even then number of odd pairs we can have by adding any $b_i+b_j$ is just $3$ and total number odd pairs in $X$ is $5$ so we can't cover all odd number. Now if $b_1, b_2$ is odd, $b_3, b_4$ is even then also total number of odd elements we can cover of $X$ is $4$. Now if $b_1$ is odd and $b_2, b_3, b_4$ is even then total number of odd elements we can cover of $X$ is $3$ Now if no elements of $S$ is odd then we can never ever cover any odd element of $X$ hence contradiction $k\neq 4$ Claim 4-: $k=5$ is possible Now observe For $k=5$ we can have $S=\{b_1,b_2,..,b_5\}$, if $b_1,b_2$ is odd and $b_1,b_2,b_3$ is even then we can always chose $6$ odd numbers and in this way it is possible to cover $5$ odd elements of $X$ So $k=5$ looks possible and eventually it is For Example $S=\{1,3, 0, 2,6\}$ works Hence $|S|_{min}=5$ $\blacksquare$ @below -: yes but i didn't thought about this way in actual exam.... As here I have just posted my method or how I have written my solution to this question in actual exam.

To make the computation easier can't you just consider $|S| \ge 4$ as $\binom{|S|}{2} \ge 10$?

after awhile, I don't get one thing, why do people say 0, 1 \in S as 1 can be written as only 0+1=1? is carrying over not allowed? my solution is to show that S ≥ 4 and if S = 4 then always greater than 5 even digits

We have to notice that: Let X to be the number of elements in the subset S.As we can see that if there existed a positive integer N like that , so for any integers a and b belonging to S, let A and B be the last digit of a and b respectively.Then we must have A+B=0,1,2,3,4,5,6,7,8,9.Let Y be the number of the set (A,B) such that A+B equals to 0,1,2,3,...,9. Thus, Y=(X^2-X)/2 >=10 or X>=5. The problem has solved. We can choose S={0,1,3,4,5}

Note that the given problem is equivalent to the following Find the smallest $|S|$ which is a subset of $\{0, 1, \dots, 9\}$ such that any decimal digit can be achieved by considering the sum of 2 (possibly same) numbers mod 10 in $S$ We claim that the minimum value of $|S|$ is 5. To show this, first consider $S=\{0,1,2,5,8\}$ as a construction for $|S|=5$. Now note that showing $|S|=4$ doesn't work is enough to complete the proof. Consider $S=\{a,b,c,d\}$ Firstly note that the total number of sums for $|S|=4$ is $6+4=10$ and thus all these 10 sums must have a unique last digit. The sums $2a, 2b, 2c, 2d$ are all even and thus exactly one of the 6 pairwise sums can be even. WLOG $a+b$ is even. Thus $a$ and $c$ must have opposite parity, and $a$ and $d$ must have opposite parity. But this implies $c$ and $d$ have the same parity so $c+d$ is even and this is a contradiction.

We claim the minimal value is $|S|=5$. This is clearly enough since $S=\{0,1,3,5,6\}$ gets all digits without carrying. This is necessary by considering the last digit of the large number. If $x$ is the number of odd elements in $S$, and $y$ is the number of even elements, then $xy$ is the number of odd elements of $S+S$. Thus, if $x+y\leq 4$, then $xy\leq 4<5$ which means that not all odd last digits can be hit. Thus, $|S|\geq 5$ and we're done.

We claim that the smallest possible value of $|S|$ is $5$. We claim that $|S|=4$ fails, and then proceed to give a construction for $|S|=5$. For the sake of contradiction, assume that $S=\{a,b,c,d\}$ works. This means that we can construct any digit using the members of this set by summing two of them up (which don't have to be necessarily distinct). Since $\binom{4}{2}+4=10$, the set of results when two of them are summed must be distinct modulo $10$. Say that $x$ of these numbers are odd and $4-x$ are even. It follows that there are atmost $x(4-x)$ distinct odd numbers which can be formed by summing two elements in $S$ up. However, $x(4-x)$ is maximised at $x=2$, in which case we get a maximum of $4$ odd digits, but we wanted $5$ and this is a contradiction. For the construction, choose $S=\{1,0,2,3,7\}$. It is easy to see that we can get $0,1,2, \dots,9$ from summing two elements in $S$ and therefore this satisfies the problem conditions. The only problem is that one of the numbers could become $0$, but this only happens if all digits of that number are $1,2,3$, in which case we switch $0$ and $n$ (which is either 1,2,3) in case a number becomes 0

Here if a case leads to a contradiction, then we say that case is "bad". First we observe that $1=0+1$. So $\{0,1\} \in S$. Hence $|S| \ge 3$. Now we see that $3=0+3,1+2$. So one of $2,3$ must belong to $S$.

Now we will show that for $|S|=5$ it is possible. Let $S=\{0,1,2,3,6\}$ Let $n=\overline{a_ma_{m-1} \cdots a_0}$ We want to show that there exists $p,q$ whose digits belong to $S$ and $n=p+q$. Assume $p=\overline{p_mp_{m-1} \cdots p_0}$ $q=\overline{q_mq_{m-1} \cdots q_0}$ We consider for the time being that leading digits of $p,q$ maybe $0$.We pick a digit of $n$, say $a_i$. $$a_i=0 \implies p_i=0,q_i=0$$$$a_i=1 \implies p_i=1,q_i=0$$$$a_i=2 \implies p_i=2,q_i=0$$$$a_i=3 \implies p_i=3,q_i=0$$$$a_i=4 \implies p_i=3,q_i=1$$$$a_i=5 \implies p_i=3,q_i=2$$$$a_i=6 \implies p_i=6,q_i=0$$$$a_i=7 \implies p_i=6,q_i=1$$$$a_i=8 \implies p_i=6,q_i=2$$$$a_i=9 \implies p_i=6,q_i=3$$Hence using this way we can form any number in the desired dual sum. If there are any leading zeros of $p,q$ omitting them would not affect the solution. Hence $|S|_{\min}=5$

I just mocked a 51 on INMO?! However, I would like to admit that I was spoiled on the fact that the answer is 5, but I think (hope?) that I would have solved this regardless During the mock I mistakenly thought that $S={1,3,5,7,9}$ works but when writing this up, I realised and fixed my mistake, (eta: the image below is my scratch work, it seems that i had a couple small mistakes to fix there) It also seems that my solution has not been posted here before, so I would really appreciate if someone could check it, mainly the construction is the part i am kinda unsure about (and maybe pm me? or you can post here also) Solution to the problem with original wording: I claim the answer is $|S|=5$ and that $S={0,1,2,4,7}$ works. First let's prove ${0,1,2,4,7}$ works. It is trivial to chekc we can write all numbers between $0$ and $9$ can be written using these, indeed consider: $(0+0,0+1,0+2,1+2,0+4,1+5,4+2,0+7,1+7,2+7)$ Now use strong induction (ie, assume for all $k$ less than $n$, this is possible) Let $n \equiv r \ (\mod 10)$, where $r \in {0,1,2,\cdots 9}$ Write $r=p_u+q_u$ ($u$ stands for unit digit ) Now, as $\frac{n-r}{10}$ can be written in the form the question desires, clearly so can $n$. Like if $\frac{n-r}{10}$ is $(p_t p_{t-1} \cdots p_1)_{base 10} + (q_t q_{t-1} \cdots q_1)_{base 10}$ $n= (p_t p_{t-1} \cdots p_1 p_u)_{base 10} + (q_t q_{t-1} \cdots q_1 q_u)_{base 10}$. Now I claim that for $|S| \le 4$, we can not even cover all residues mod 10, ie. $T=({a+b \mod 10 \ | \ a,b \in S})$ and $(0,1,2,\cdots 9)$ can not be equal. Indeed, for $S \le 3$, $T$ does not even have 10 elements $(T \le \binom{|S|}2 + |S|)$. So, for $|S|=4$, let $S=(a,b,c,d)$, then the possible sum pairs are $(2a,a+b,a+c,a+d,2b,b+c,b+d,2c,c+d,2d)$ and hence these all must be different mod 10, which implies that exactly 5 of these must be 1 mod 2, but $2a,2b,2c,2d$ are clearly 0 mod 2, so exactly one of $(a+b,a+c,a+d,b+c,b+d,c+d)$ must be 1 mod 2. Now, WLOG, say $b+d$ is the even thing. As everything else is odd, in particular we get $c+d$ and $a+d$ odd which implies $c-a$ even which implies $a+c$ even also, contradiction! Wow, I am really happy today, I just solved 3 INMO problems , I will work very hard to ensure 15th Jan goes the same way

The answer is $5$ digits. First, I show it is impossible with four digits. Notice that there are ${4 \choose 2} + 4 = 10$ distinct units digits that can be achieved with some combination of digits from $S$. However, notice that the four digits that are formed by adding the same digit to itself are even; out of the combinations of distinct digits, there are at least two more of these sums that are even, so this is clearly not possible with four digits. For a construction, $\{0, 1, 2, 5, 8\}$ clearly works, as we can go digit by digit.

The answer is $|S|=5$. Our construction is $\{0,1,2,4,5\}$, which works as all digits $0-9$ can be decomposed using just these numbers. Now we show it is minimal. FTSOC assume $|S|=4$. Now, note that there are $10$ possible results modulo $10$ after adding any $2$ elements of $S$. Then, each sum must give a different number in $\{0,1,\cdots, 9\}$ taken modulo $10$. Let $S=\{a,b,c,d\}$. Note that the sum yielded from doubling each of $a,b,c,d$ will give $4$ even numbers, so we then need $1$ even and $5$ odd numbers from adding pairwise distinct elements. WLOG let the even sum be $a+b$. Note that $a,b$ must have the same parity, which implies a contradiction. Thus, $|S|>4$, so we are done. $\blacksquare$

Because the problem states "sufficiently large number," it suffices to show all the residues $\pmod{10}$ can be created as a result of the sum of two elements in $S$. Thus, the minimum value for $|S|$ is $4$ as there are $10$ possible results from adding two different elements from $S$. Assume that $|S|=4$. Clearly at least $4$ of the residues left by adding two of the elements in $S$ are even. In order to cover every residue $\pmod{10}$, there must only be $5$ even residues produced by adding all pairs of elements in $S$. Evidently this is impossible by simply trying every choice of parity. Thus, we must have $|S| \ge 5$, which is achievable with $S = \{0,1,3,4,6\}$, so $|S|=\boxed{5}$ is the answer.

We must have that for every $0 \le x \le 9$, there exists $p, q \in S$ with $p + q \equiv x \pmod{10}$. We'll show that $|S| \le 4$ isn't possible. It suffices to show that for $|S| = 4$, it isn't possible. Note that every odd residue must be produced as a result of $(p + q) \pmod{10}$, with $p, q \in S$. So, if $o$ and $e$ are the number of odd and even elements in $S$ respectively, we must have $o \cdot e \ge 5$ (since only a combination of exactly one odd element and exactly one even element can produce an odd element modulo $10$), but by AM-GM, we have $o + e \ge 2 \sqrt{o\cdot e}$, which gives $o \cdot e \le 4$, contradiction. For $|S| = 5$, just take $\{0, 1, 2, 4, 5\}$, which produces $0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 0 + 4 = 4, 0 + 5 = 5, 2 + 4 = 6, 2 + 5 = 7, 4 + 4 = 8, 4 + 5 = 9.$

Easily one of the most trivial problems I have done. Note that the original wording (in the INMO exam) makes it even more trivial, since it dosen't restrict us to satisfy single digit positive integers. This entire problem is just common sense. Posting for storage Ig :

The answer is $|S| = 5$. If $|S| = 4$ then there are at most $\binom{4}{2} + 4 = 10$ possibilities for the last digit. However we can show that some of these residues mod $10$ repeat by doing casework on parities. If there are $4$ evens, then we can't get odd residues. If there are $3$ evens and $1$ odd then there are $7$ even residues resulting in overlap. If there are $2$ even and $2$ odd then there are $6$ even residues resulting in overlap. The rest of the cases are similar. So then $|S| = 4$ is impossible. A possible construction for $|S| = 5$ is $\{0, 1, 3, 4, 6\}$ which works as we can construct all digits.

Nice! I did it with casework first, but found the slicker way when writing up. We claim that the answer is $5$, achieved by $(0,1,3,4,6)$. This obviously works because every digit from $0$ to $9$ can be represented as a sum of two digits in the set. First, $|S|\leq3$ is impossible because we will be able to make a maximum of $3^2=9$ digits. We then won't be able to make any number ending in the digit that we can't make. To prove that $|S|=4$ is impossible, we consider the number of odd digits that we can make from $S$. If the number of odd elements of $S$ is $x$, then we can make at most $x(4-x)$ odd digits. However, $0\cdot4$, $1\cdot3$, and $2\cdot2$ are all less than $5$, so we will never be able to make all $5$ odd digits that we need.

ok |S| <= 3 doesnt work since then max total no. of units digit formation = 6. Also to form 1 = a+b, 0 and 1 must be there. 2 is then formable by 1 + 1. 3 is then not formable:- to form 3 you would need 2 or 3 as an element in S. Now similarly repeat this process by a lot of casework to finally get that minimum of |S| = 5 so that all the unit digits are formable. Now we will proceed to show that for all non singular digit numbers it also works. if suppose the number is 43 then we can write 4 as a sum of some numbers from our set satisfying the a+b thing for unit digits condition. let the numbers be uni-digits a and b, then a0, b0 added give 40. Now to get the units digit we apply the same approach, assume some p+q = 3 exists (which it does) so just replace a0 with ap and b0 with bq and then ap+bq = 43 (note that a,p,b,q = digits). This should give away the procedure we are gonna be doing for other numbers. Just use this argument directly or with MI (the MI being a little bit easier to deal with)