Maths Olympiad Prep

Library / /38 of 75

Combinatorics Difficulty 5.0 AIME Find the answer Italy

Problem:

How many positive integers of 10 digits abcdefghijabcdefghij are there, with all digits different, that satisfy the conditions a+j=b+i=c+h=d+g=e+f=9a+j=b+i=c+h=d+g=e+f=9?

Note: a number cannot start with 00.

Pick one

Solution

Solution:

The answer is (A). Let us call, as in the text, abcdefghijabcdefghij the 10 digits of the number.

For numbers of the required form, fixing the first 5 digits a,b,c,d,ea, b, c, d, e uniquely determines the whole number because of the imposed condition (since we can derive f=9ef=9-e, g=9dg=9-d, h=9ch=9-c, i=9bi=9-b, j=9aj=9-a).

On the other hand, if among the first five digits there were two equal digits, or two digits summing to nine, we would have a number that does not satisfy the conditions, because on one hand we required that the digits be all different, and on the other hand, if two digits with sum nine appeared among the first five, they would also appear - in the opposite order - among the last 5, whereas we want them all to be different.

It is therefore sufficient to count the numbers of 5 digits (the first 5), with a,b,c,d,ea, b, c, d, e all different and such that no pair has sum 9.

Forgetting for now the fact that a number must not start with 0, we see that aa can be chosen in 10 ways, bb in 8 ways (all digits, except aa, already used, and 9a9-a), cc in 6 ways (all digits are possible, except a,ba, b and 9a,9b9-a, 9-b), dd in 4 and ee in 2 possible ways.

From these, however, we must subtract the numbers that start with the digit zero, which are (since a=0a=0, at this point, is fixed) 86428 \cdot 6 \cdot 4 \cdot 2 by the same reasoning as above (8 choices for the digit bb, 6 for cc, 4 for dd and 2 for ee).

The answer to the problem is therefore 1086428642=(101)8642=345610 \cdot 8 \cdot 6 \cdot 4 \cdot 2 - 8 \cdot 6 \cdot 4 \cdot 2 = (10-1) \cdot 8 \cdot 6 \cdot 4 \cdot 2 = 3456.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.