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 N1N2N3N4N5N6N7N8N9.

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.  N5 must be 5, so we have N1N2N3N45N6N7N8N9.  N2, N4, N6, and N8, must be even, which means that the odd-numbered numbers must be odd.  N1 + N2 + N3 must be divisible by three.

N4 + 5 + N6 must be divisible by three as well, by the divisibility-by-six rule, and the facts that N1 + N2 + N3 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 N4 and N6 must be even, N4N5N6 must be 258, 456, 654, or 852.  Since N3 must be odd, using 456 or 852 would make N1N2N3N4 not divisible by four.  So, N4N5N6 must be either 258 or 654.

Let’s choose N4N5N6 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 N1 + N2 + N3 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 N2=4, N1 and N3 must be 1 and 7 (in either order); and if N2 is 6, N1 and N3 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 N6N7N8, 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, N4N5N6 = 654.  Look at N6N7N8.  N6=4, and the whole must be divisible by eight.  N8 has to be either 2 or 8, but there are no available numbers for N7 in 4N78 that are divisible by eight.  So, N8 is 2, and N2=8.  The only available numbers for N7 in 4N72 that are divisible by eight are 3 and 7.

So we have N18N3654N72N9, with 1, 3, 7, and 9 yet to be assigned, and either N7=3 or N7=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 N1 and N3 (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!