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 13:25, 5 November 2020
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 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.