The ruler of a wealthy kingdom pays his mathematics tutor with gold coins every day. Every evening, the tutor needs to choose a new positive integer and teach him some properties of the number. The king pays him as many gold coins as the minimum number of distinct digits any positive multiple of this number has.

What is the maximum number of gold coins he can earn every week?

## Andrew B. solved this puzzle:

14 per week.

Suppose he chooses the integer n. Consider the numbers of the form 111…111 (with up to n + 1 1's). By the pigeonhole principle, two of them are congruent mod n, and so the difference between them is of the form 111…111000…000 which is a multiple of n.

If n is a multiple of 10, any multiple of it ends with 0, so it has no multiples with only 1 distinct digit.