Russia National Contest Pr 1998-7

[sirio11]

A 10-digit number is said to be "interesting" if its digits are all distinct and it's a multiple of 11111. How many "interesting" integers are there?

[jay_shark]

I just had a solution written out but somehow it erased .

In any case , I figured out that if the 10 digit integer is abcdefghij then it turns out that the solutions are

a+f=9 , b+g=9 , c+h=9 , d+i=9 , e+j=9 as long as we take into account that the first digit cannot be a 0 .

So a solution may be 4321056789 or 5678943210 ...
It's relatively easy to count the total number of solutions given the constraints .

[sirio11]

[ QUOTE ]
It's relatively easy to count the total number of solutions given the constraints .

[/ QUOTE ]

Do tell us the answer.

[furyshade]

[ QUOTE ]
I just had a solution written out but somehow it erased .

In any case , I figured out that if the 10 digit integer is abcdefghij then it turns out that the solutions are

a+f=9 , b+g=9 , c+h=9 , d+i=9 , e+j=9 as long as we take into account that the first digit cannot be a 0 .

So a solution may be 4321056789 or 5678943210 ...
It's relatively easy to count the total number of solutions given the constraints .

[/ QUOTE ]

unless im doing something wrong it seems the answer is 10 nPr 10, or 3628800

[sirio11]

[ QUOTE ]
unless im doing something wrong it seems the answer is 10 nPr 10, or 3628800

[/ QUOTE ]

You're counting a lot of numbers not in the solution. Remember, they need to be a multiple of 11111.

[furyshade]

[ QUOTE ]
[ QUOTE ]
unless im doing something wrong it seems the answer is 10 nPr 10, or 3628800

[/ QUOTE ]

You're counting a lot of numbers not in the solution. Remember, they need to be a multiple of 11111.

[/ QUOTE ]

then is it 10^5, if there are 10 combinations of x+y=9, and 5 sets of pairs

[sirio11]

It's not 10^5, one of the things you need to remember is that the first digit can not be zero.

[furyshade]

[ QUOTE ]
It's not 10^5, one of the things you need to remember is that the first digit can not be zero.

[/ QUOTE ]

so then what is the correct way of doing it, 10,001 seems too obvious

[jay_shark]

There are 10^5 solutions to the 5 equations .

Now we subtract the number of ways a=0 and f=9 .
This means there are 8 available numbers for the four equations and so we have 10^5 - 8^4 = 95,904

================================================== =======

Here is the solution :

The 10-digit number can be written as
a*10^9 + b*10^8 + c*10^7 + ...+ i*10^1 +j*10^0

a*10^9 =a*10^4mod11111
b*10^8=b*10^3mod11111
c*10^7=c*10^2mod11111
d*10^6=d*10^1mod11111
e*10^5=e*10^0mod11111

So we require

(a+f)*10^4 + (b+g)*10^3 + ... + (e+j)*10^0 =y*11111 for 1<=y<=16 , since the maximum value for a+f = 17 and the minimum value for a+f = 1 . It turns out that the only solution is when a+f=9 , in which case b+g=9 , c+h=9 etc .

[sirio11]

[ QUOTE ]
There are 10^5 solutions to the 5 equations .

[/ QUOTE ]

All digits are distinct, so there are way less than 10^5 solutions