RMO part 1!

A 10 digit number with no repeated digits and leading digit nonzero is called a ''magic number''if it is divisible by 99999.

How many such magic numbers are there?


The answer is 3456.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Patrick Corn
Sep 15, 2015

Since x x has 10 10 digits and is of the form ( 1 0 5 1 ) y (10^5-1)y , we see that 1 0 4 < y 1 0 5 + 1 10^4 < y \le 10^5+1 . We can rule out y = 1 0 5 y = 10^5 and 1 0 5 + 1 10^5+1 since it leads to an x x with repeated digits, so this means that y y has 5 5 digits.

Note that x = ( y 1 ) ( 1 0 5 y ) x = \overline{(y-1)(10^5-y)} , so the two five-digit halves of x x are numbers with no repeated digits that add up to 99999 99999 . For example y = 23986 y = 23986 , x = 2398576014 x = 2398576014 . Note that the digits that are five spaces apart are paired up with each other; each pair sums to 9 9 .

The number of choices for x x is the number of choices for the left five digits of x x . We can choose one of two digits from each pair of digits that add to 9 9 , and then we can permute those digits however we want; so the number of such x x is almost 2 5 5 ! 2^5 \cdot 5! ; but we cannot have a leading 0, so we must subtract the 2 4 4 ! 2^4 \cdot 4! choices that involve picking a first digit of 0 0 . So the answer is 2 5 5 ! 2 4 4 ! = 3456 2^5 \cdot 5! - 2^4 \cdot 4! = \fbox{3456} .

could u explain the permutatio part and why x = ( y 1 ) ( 1 0 5 y ) x = \overline{(y-1)(10^5-y)}

Department 8 - 5 years, 6 months ago

Log in to reply

It's probably easiest if you just work through an example, like y = 23986 y = 23986 . Multiplying that by 1 0 5 1 10^5-1 gives 2398600000 23986 2398600000 - 23986 , so the rightmost five digits are 1 0 5 23986 10^5-23986 and the second five digits are 23986 1 23986-1 .

Patrick Corn - 5 years, 6 months ago
Ankit Kumar Jain
Feb 13, 2017

Almost the same solution as @Patrick Corn but I explain it differently.

The number can be written as 1 0 5 . a 1 a 2 a 3 a 4 a 5 + a 6 a 7 a 8 a 9 a 10 10^{5}.\overline{a_{1}a_{2}a_{3}a_{4}a_{5}} + \overline{a_{6}a_{7}a_{8}a_{9}a_{10}} .

Therefore , 99999 a 1 a 2 a 3 a 4 a 5 + a 6 a 7 a 8 a 9 a 10 99999 \mid \overline{a_{1}a_{2}a_{3}a_{4}a_{5}} + \overline{a_{6}a_{7}a_{8}a_{9}a_{10}} .

Now clearly , a 1 a 2 a 3 a 4 a 5 + a 6 a 7 a 8 a 9 a 10 < 199998 \overline{a_{1}a_{2}a_{3}a_{4}a_{5}} + \overline{a_{6}a_{7}a_{8}a_{9}a_{10}} < 199998

a 1 a 2 a 3 a 4 a 5 + a 6 a 7 a 8 a 9 a 10 = 99999 \Rightarrow \overline{a_{1}a_{2}a_{3}a_{4}a_{5}} + \overline{a_{6}a_{7}a_{8}a_{9}a_{10}} = 99999

a i + a 5 + i = 9 \Rightarrow a_{i} + a_{5 + i} = 9 , where i 1 , 2 , 3 , 4 , 5 {i}\in{1 , 2 , 3 , 4 , 5} .

Therefore it is equivalent to finding the number of possible 5 pairs such that the sum of the elements in a pair = 9 and all the ten digits are used.

It is equal to 2 5 . 5 ! 2 4 . 4 ! 2^{5}.5! - 2^{4}.4! ....... (Subtracting cases when a 1 = 0 a_{1} = 0 )

Therefore , the number of magic numbers = 3456 \fbox{3456}

How did you do the permutation and combinations step Please explain the last step clearly

Vinayak Gupta - 4 years, 1 month ago

Log in to reply

It is like..Distributing the pairs ( 0 , 9 ) , ( 1 , 8 ) , ( 2 , 7 ) , ( 3 , 6 ) , ( 4 , 5 ) (0,9),(1,8),(2,7),(3,6),(4,5) into two groups and assigning them a place in that number..

So for distributing the pairs , we have 2 5 = 32 2^5 = 32 ways and for arranging them 5 ! = 120 5! = 120 ways....i.e. 32 × 120 = 3840 32\times120 = 3840 ways.

But we need to ensure that the first digit of the number doesn't become 0..For that we need to follow the same with 4 pairs ....distribute them...arrange them...i.e 2 4 × 4 ! = 16 × 24 = 384 2^4\times {4!} = 16\times24 = 384 ways.

therefore our answer becomes 3840 384 = 3456 3840-384=3456

Ankit Kumar Jain - 4 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...