A nine-digit positive integer $n$ is called a Moffat number if

- its digits are $0,1,2,3,4,5,6,7,8$ with no repetition,
- the sum of each group of 5 digits in a row is divisible by 5 , and
- the sum of each group of 7 digits in a row is divisible by 4 .

For example, 578460213 is not a Moffat number because, while the sum of each group of 7 digits in a row is divisible by 4 , not all of the sums of groups of 5 digits in a row are divisible by 5 . Determine the sum of all Moffat numbers.

## PART B

For each question in Part B, your solution must be well-organized and contain words of explanation or justification. Marks are awarded for completeness, clarity, and style of presentation. A correct solution, poorly presented, will not earn full marks.
We label the digits of $n$ in order from left to right as $n_{1}, n_{2}, n_{3}, n_{4}, n_{5}, n_{6}, n_{7}, n_{8}, n_{9}$. Since $n$ is a nine-digit integer, then $n_{1} \neq 0$.

From the given information, the following sums must be multiples of $5: n_{1}+n_{2}+n_{3}+n_{4}+n_{5}$ and $n_{2}+n_{3}+n_{4}+n_{5}+n_{6}$ and $n_{3}+n_{4}+n_{5}+n_{6}+n_{7}$ and $n_{4}+n_{5}+n_{6}+n_{7}+n_{8}$ and $n_{5}+n_{6}+n_{7}+n_{8}+n_{9}$.

Also, the following sums must be multiples of 4: $n_{1}+n_{2}+n_{3}+n_{4}+n_{5}+n_{6}+n_{7}$ and $n_{2}+n_{3}+n_{4}+n_{5}+n_{6}+n_{7}+n_{8}$ and $n_{3}+n_{4}+n_{5}+n_{6}+n_{7}+n_{8}+n_{9}$.

We need the following fact, which we label $(*)$ :

If $a$ and $b$ are positive integers that are both multiples of the positive integer $d$, then their difference $a-b$ is also a multiple of $d$.

This is true because if $a=e d$ and $b=f d$ for some positive integers $e$ and $f$, then $a-b=e d-f d=d(e-f)$ which is a multiple of $d$.

By $(*),\left(n_{1}+n_{2}+n_{3}+n_{4}+n_{5}\right)-\left(n_{2}+n_{3}+n_{4}+n_{5}+n_{6}\right)=n_{1}-n_{6}$ must be a multiple of 5 . Since $n_{1}$ and $n_{6}$ are taken from the list $0,1,2,3,4,5,6,7,8$ and no pair of numbers from this list differs by more than 8 , then for $n_{1}-n_{6}$ to be a multiple of 5 , we must have that $n_{1}$ and $n_{6}$ differ by 5 .

Similarly, $n_{2}$ and $n_{7}$ differ by $5, n_{3}$ and $n_{8}$ differ by 5 , and $n_{4}$ and $n_{9}$ differ by 5 .

The pairs from the list $0,1,2,3,4,5,6,7,8$ that differ by 5 are 0,5 and 1,6 and 2,7 and 3,8 . These integers must be assigned in some order to the pairs $n_{1}, n_{6}$ and $n_{2}, n_{7}$ and $n_{3}, n_{8}$ and $n_{4}, n_{9}$.

Note that $n_{5}$ is not in the list of positions affected and 4 is not in the list of integers that can be assigned to these slots.

Therefore, $n_{5}=4$.

Using $(*)$ again, we also see that $n_{1}$ and $n_{8}$ differ by a multiple of 4 , and $n_{2}$ and $n_{9}$ differ by a multiple of 4 .

Suppose that $n_{1}=1$. Then from above, $n_{6}=6$ (using divisibility by 5 ) and $n_{8}=5$ (using divisibility by 4 , since the only integer from our list that differs from 1 by a multiple of 4 is 5 ). Since $n_{8}=5$, then using divisibility by 5 , we have $n_{3}=0$.

So if $n_{1}=1$, the digits of $n$ look like $1 \_0 \_46 \_5 \ldots$.

Using similar analysis, we make a table that lists the first digit, and the resulting configurations:

| $n_{1}$ | Configuration |
| :---: | :---: |
| 1 | $1 \_0 \_46 \_5 \_-$ |
| 2 | $2 \_1 \_47 \_6 \_$ |
| 3 | $3 \_2 \_48 \_7-$ |
| 5 | $5 \_6 \_40 \_1-$ |
| 6 | $6 \_7 \_41 \_2-$ |
| 7 | $7 \_8 \_42 \_3 \_$ |
| 8 | $8 \_5 \_43 \_0 \_$ |

Note that, in the case where $n_{1}=8$, we know that $n_{8}$ differs from 8 by a multiple of 4 , but cannot equal 4 since $n_{5}=4$ already.

While it is necessary that $n_{1}$ and $n_{8}$ differ by a multiple of 4 , it is not sufficient to guarantee that the sum of each set of 7 consecutive digits is a multiple of 4 .

Since the sum of the 9 digits of $n$ is $0+1+2+3+4+5+6+7+8=36$ (which is a multiple of 4) and $n_{3}+n_{4}+n_{5}+n_{6}+n_{7}+n_{8}+n_{9}$ is a multiple of 4 , then $n_{1}+n_{2}$ must be a multiple of 4 . Since each of the digits is between 0 and 8 , then the maximum sum of two digits is 15 , and so the possible multiples of 4 to which $n_{1}+n_{2}$ can be equal are 4,8 and 12 .

If $n_{1}=1$, then this means that $n_{2}=3$ or $n_{2}=7$.

If $n_{1}=2$, then $n_{2}=6$, which is not possible, since $n_{8}=6$.

If $n_{1}=3$, then $n_{2}=1$ or $n_{2}=5$.

If $n_{1}=5$, then $n_{2}=3$.

If $n_{1}=6$, then $n_{2}=2$, which is not possible, since $n_{8}=6$.

If $n_{1}=7$, then $n_{2}=1$ or $n_{2}=5$.

If $n_{1}=8$, then $n_{2}=0$ or $n_{2}=4$, which are not possible, as these digits are already used.

If $n_{2}=3$, then using a similar analysis to that above, we have $n_{7}=8$ and $n_{9}=7$ and $n_{4}=2$.

Thus, when $n_{1}=1$ and $n_{2}=3$, then $n=130246857$.

Using similar analysis on the remaining cases, we obtain the following possible values for $n$ :

130246857, 170846253, 312048675, 352648071, 536240817, 576840213, 718042635, 758642031

We can check that each of these nine-digit integers has the desired properties.

The sum of these eight nine-digit integers is 3555555552 .

(We note that the sum of the possible values for each digit is 32 .)

ANSWER: 3555555552

## Part B