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

Difference between revisions of "2020 INMO Problems/Problem 3"

(Created page with "==PROBLEM== Let <math>S</math> be a subset of <math>\{0,1,2,\cdots ,9\}</math>. Suppose there is a positive integer <math>N</math> such that for any integer <math>n>N</math>,...")
 
(→‎Solution(1))
Line 9: Line 9:
  
 
i.e for any natural <math>n>1</math>,it can be represented as sum of two natural <math>a,b</math> such that degits in decimal representation of <math>a,b</math> always <math>\in \mathcal{S}</math>.
 
i.e for any natural <math>n>1</math>,it can be represented as sum of two natural <math>a,b</math> such that degits in decimal representation of <math>a,b</math> always <math>\in \mathcal{S}</math>.
−
----------
 
 
<math>\boxed{\text{Claim}}</math>
 
<math>\boxed{\text{Claim}}</math>
  
Line 29: Line 28:
 
  Similar argument for<math>|\mathcal{S}|<4</math>.
 
  Similar argument for<math>|\mathcal{S}|<4</math>.
  
−
So,These contradiction prove our claim.
+
So,These contradiction prove our claim .
−
 
 
−
----------
 
 
Now ,Look for <math>|\mathcal{S}|=5</math>. In this case we get 10 distinct congruence modulo 10. So ,we can guess that <math>|\mathcal{S}| \ge 5</math>are <math>\textbf{ achivable}</math> .
 
Now ,Look for <math>|\mathcal{S}|=5</math>. In this case we get 10 distinct congruence modulo 10. So ,we can guess that <math>|\mathcal{S}| \ge 5</math>are <math>\textbf{ achivable}</math> .
  
Line 37: Line 34:
 
So, we are done with this!
 
So, we are done with this!
 
------------
 
------------
 +
 
==Solution(2)==
 
==Solution(2)==
 
The answer is <math>5</math>. First, we show this is achieved. Consider <math>S = \{0,1,2,3,7\}</math>. Since <math>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, </math> and <math>2+7=9</math>, so all digits can be split individually. The only case any problem can arise is when we try to split <math>n</math> as <math>a+b</math> and end up with one of <math>a</math> or <math>b</math> equal to <math>0</math>. If <math>n</math> has any of the digits <math>2,3,4,5,7,8,9</math>, or has at least two non-zero digits, then this problem won't arise. The only cases where a problem can arise is when <math>n=10^k</math> or <math>n=7 \cdot 10^k</math> for some non-negative integer <math>k</math>. We take <math>N=11</math>. Then <math>k \ge 1</math>. But then
 
The answer is <math>5</math>. First, we show this is achieved. Consider <math>S = \{0,1,2,3,7\}</math>. Since <math>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, </math> and <math>2+7=9</math>, so all digits can be split individually. The only case any problem can arise is when we try to split <math>n</math> as <math>a+b</math> and end up with one of <math>a</math> or <math>b</math> equal to <math>0</math>. If <math>n</math> has any of the digits <math>2,3,4,5,7,8,9</math>, or has at least two non-zero digits, then this problem won't arise. The only cases where a problem can arise is when <math>n=10^k</math> or <math>n=7 \cdot 10^k</math> for some non-negative integer <math>k</math>. We take <math>N=11</math>. Then <math>k \ge 1</math>. But then

Revision as of 12:25, 5 November 2020

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"