Russia National Contest Pr 1998-7

[sirio11]

The digits are all distinct, so you need to use all of them for the 10 digit numbers.

Now 0+1+2+...+9 = 45, so all the numbers are multiples of 9, since 11111 is not, then the numbers must be multiples of 99999

Let N = abcdefghij = abcde00000 + fghij
Lets call p = abcde and q = fghij then N = 100000p + q = 99999p + p + q

Since N must be multiple of 99999, then p+q is a multiple of 99999 and since p,q are 5 digits numbers, the only possibility is for their sum to be 99999; therefore

a+f=9 b+g=9 c+h=9 d+i=9 e+j=9

a can be chosen 9 ways (can't be zero), once a is chosen, f is fixed, now b can be chosen of 8 ways (no a,f); c has 6 ways, d has 4 ways and e has 2, so the final answer is:

9*8*6*4*2 = 3456 numbers


Another way to count them:

You have 5 couples {a,f},{b,g},{c,h},{d,i},{e,j}

These can be chosen of 5! ways, and each couple has 2 options, so you have 5!*2^5 ways, but here we are counting some numbers with a=0, we need to discount those, if a=0, f=9 and we have 4!*2^4 ways for the other couples, then our number will be:

5!*32 - 4!*16 = 4!*16(5*2-1) = 24*16*9 = 3456

[jay_shark]

Yes Sirio that's correct .

It really is a simple permutations problem once you figure out the constraints I gave earlier . For some reason I neglected that the integers were distinct when I wrote up the solution late last night , but it's fairly straightforward otherwise .