0910.4: Solution

Congratulations to Evan Van Tassell '13, for winning the Fourth Logic Puzzle - a two-time winner!

The single correct number (see below) was also submitted by Amelia Appel '13, Linnaea Chapman '10, Michael Kranz '10, Raul Patrascu '12, Jack Riffle '12, and Shichen Xu '12. Thanks to all who submitted solutions!

The solution appeals to several well-known divisibility rules. Any number divisible by two is even. The sum of the digits of any number divisible by three will also be divisible by three. If the last two digits of a number are divisible by four, the whole number will be divisible by four. Numbers divisible by five have either 0 or 5 as their last digit. Numbers divisible by six will be divisible by both two and three. If the last two digits of a number are divisible by eight, the whole number will be divisible by eight. The sum of the digits of any number divisible by nine will also be divisible by nine.

Let’s call the number N_{1}N_{2}N_{3}N_{4}N_{5}N_{6}N_{7}N_{8}N_{9}.

A few constraints follow quickly. Since any solution will use all the digits from 1-9, whose sum is forty-five, we need not worry about divisibility by nine. N_{5} must be 5, so we have N_{1}N_{2}N_{3}N_{4}5N_{6}N_{7}N_{8}N_{9}. N_{2}, N_{4}, N_{6}, and N_{8}, must be even, which means that the odd-numbered numbers must be odd. N_{1} + N_{2} + N_{3} must be divisible by three.

N_{4} + 5 + N_{6} must be divisible by three as well, by the divisibility-by-six rule, and the facts that N_{1} + N_{2} + N_{3} must be divisible by three and that the difference between a number divisible by three and another number divisible by three will also be divisible by three. Given that N_{4} and N_{6} must be even, N_{4}N_{5}N_{6} must be 258, 456, 654, or 852. Since N_{3} must be odd, using 456 or 852 would make N_{1}N_{2}N_{3}N_{4} not divisible by four. So, N_{4}N_{5}N_{6} must be either 258 or 654.

Let’s choose N_{4}N_{5}N_{6} as 258, first. There are two even numbers remaining, 4 and 6, and each will be flanked by two odd numbers other than 5. Since N_{1} + N_{2} + N_{3} must be divisible by three, we have to find pairs of the remaining odd numbers that will, when added to 4 or 6, are divisible by three. Thus, if N_{2}=4, N_{1} and N_{3} must be 1 and 7 (in either order); and if N_{2} is 6, N_{1} and N_{3} must be 3 and 9 (in either order). Thus, there are only seven options:

147258369

147258963

741258369

741258963

369258147

369258741

963258147

963258741

If we look at N_{6}N_{7}N_{8}, which must be divisible by eight, we can eliminate all but 147258963 and 741258963. We can eliminate those two options by dividing their first seven digits by seven.

Thus, N_{4}N_{5}N_{6} = 654. Look at N_{6}N_{7}N_{8}. N_{6}=4, and the whole must be divisible by eight. N_{8} has to be either 2 or 8, but there are no available numbers for N_{7} in 4N_{7}8 that are divisible by eight. So, N_{8} is 2, and N_{2}=8. The only available numbers for N_{7} in 4N_{7}2 that are divisible by eight are 3 and 7.

So we have N_{1}8N_{3}654N_{7}2N_{9}, with 1, 3, 7, and 9 yet to be assigned, and either N_{7}=3 or N_{7}=7. Working with the first three numbers, only the combinations of 1 and 3, 1 and 9, and 7 and 9 can be assigned to N_{1} and N_{3} (in either order). These two constraints leave only eight options:

183654729

189654327

189654723

981654327

981654723

789654321

987654321

At this point, the only reasonable option is to divide each of the above eight numbers by 7. Only 381654729 survives, and is the only solution.

Have a nice break!