2020 INMO Problems/Problem 3
Let be a subset of . Suppose there is a positive integer such that for any integer , one can find positive integers so that and all the digits in the decimal(Base 10) representations of (expressed without leading zeros) are in . Find the smallest possible value of .
. Let,.Call as subset of if it follows the said property.
i.e for any natural ,it can be represented as sum of two natural such that degits in decimal representation of always .
For any is if .
Let,s cheak for .
So ,All elements of are distinct mod 10. Now, suppose .
now , has atmost elements .But we have distinct congruence modulo 10.
So,it can not cover all natural .
Similar argument for.
So,These contradiction prove our claim . Now ,Look for . In this case we get 10 distinct congruence modulo 10. So ,we can guess that are .
Now ,take an example as everyone above has taken . ~trishan So, we are done with this!
The answer is . First, we show this is achieved. Consider . Since and , so all digits can be split individually. The only case any problem can arise is when we try to split as and end up with one of or equal to . If has any of the digits , or has at least two non-zero digits, then this problem won't arise. The only cases where a problem can arise is when or for some non-negative integer . We take . Then . But then
Now, we claim for any "good" subset . Suppose a good subset with elements exists. Note that there are different additions possible. The sums should clearly be distinct modulo . This means that for any , the and that exist for are [b]unique upto a switch [/b] of the corresponding digits between and (just keep going from the units digit to the most significant digit sequentially, observing that upto a switch, the digits we choose for and are unique). But then, for any digit , consider obtained by putting the digit in front of . By the "uniqueness" mentioned before, the digit must be formed by the addition of two digits in .
Therefore, all digits from to can be obtained by summing two digits in (and not just ). This means no number in can be (otherwise that number added to itself gives a number greater than ). But then cannot be formed by adding two digits in . We have arrived at a contradiction.