2020 INMO Problems/Problem 3
PROBLEM
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(BASE10) representations of
(expressed without leading zeros) are in
. Find the smallest possible value of
.
Solution(1)
. 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 anyis
if
.
Let,s cheak for .
Suppose,.
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!
Solution(2)
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
and
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.