Thanks to Florian W. Borchers for pointing out (and solving) this puzzle.
Find a number M of 10 digits that satisfies the following conditions:
The digits of M are all different, i.e each digit occurs exactly once, and:
- the number that forms the last two digits of M is divisible by 2,
- the number that forms the last three digits of M is divisible by 3,
- …
- the number that makes up all ten digits of M is divisible by ten.
What is the smallest such number? What about other r-adic number systems,
binary numbers, ternary numbers, etc, up to r = 9 or 11.
Let’s call the \(i\)-th digit \(m_i\) (from right) and the number formed by the last \(i\) digits \(M_i\). So the number \(M\) is \(m_{10}m_9 \ldots m_2m_1\)
\(M_2\) is divisible by 2 and \(M_5\) is divisible by 5, therefore the rightmost digit is \(m_1 = 0\). Then \(m_2\,0\) is divisible by 4 and digit \(m_2\) is in the set \(\{2,4,6,8\}\). If \(m_2\) is 2 or 6, then \(m_3\) is in \(\{1,3,5,9\}\) because of divisibility by 8; for \(m_2\) equal to 4 or 8 there is no new condition.
As we want to find the smallest number, it will be advantageous to consume the bigger digits first. We set \(m_2 = 8\) and hope for the best.
\(m_3m_20\) being divisible by 3 means \(m_3+m_2+m_1= 0\,(3)\), and divisibility by 8 means \(4m_3+2m_2+m_1=0\,(8)\) (1000 is divisible by 8). With the assumed values for \(m_1\) and \(m_2\) it follows that \(m_3\) is even and \(m_3=1\,(3)\), thus \(m_3=4\). Our number now looks like \(m_{10}m_9\ldots m_4 480\), and we have almost used up all the divisibility rules for \(1,2,3,4,5\) and \(8\) (\(3\) still being alive, 10 is already ‘inactive’) – not much progress.
[Florians Trick] Astonishingly, there is a simple argument that shows \(m_{10}=9\). The sum of all 10 digits is \(\sum_{i=1}^{10} m_i = 10\times 9/2 = 45 = 0\,(9)\). But the puzzle requires \(\sum_{i=1}^9 m_i = 0\,(9)\). So \(m_{10}\) can be divided by 9 which is only possibel when \(m_{10} = 9\) !
What else do we know? Divisibility by 6 here implies that 3 is dividing \(m_6m_5m_4 480\) or \(m_6+m_5+m_4 = 0\,(3)\). And divisibility by 7 means \[ m_7 + 5m_6 + 4m_5 + 6m_4 = 3\,(7) \] where \(\{m_9, \ldots,m_4\} = \{1,2,3,5,6,7\}\). As above, let’s try to pick up the bigger digits first, that is \(\{m_4,m_5,m_6\}=\{5,6,7\}\) – which satisfies divisibility by 3 automatically – and \(\{m_7,m_8,m_9\}=\{1,2,3\}\).
\(\cdots\) to be continued \(\dots\)
Can we do the same for \(r\)-adic numbers? For \(r=2\), numbers in binary representation, \(m_2m_1\) has to be divisible by 2, thus \(m_1=0\), \(m_2=1\) and \((10)_2\) is the only solution.
For ternary numbers with digits 0, 1, 2 (3-adic or ternary representation), 3 dividing \(m_3m_2m_1\) implies \(m_1=0\) again. Now 2 divides \(3m_2\) and \(m_2\) has to be even, but 0 is gone, so \(m_2=2\) and \((120)_3\) is the only solution.
For larger \(r\) this gets more complicated (for a human) as some calculations have to be done in the \(r\)-adic number system. Instead we will employ a computer to do the calculations for us.
A ‘brute-force’ approach will simply genrate all \(r\)-adic numbers of length \(r\) and check whether they fullfil the requested conditions. Numbers that solve the puzzle will be returned and printed.
The following function will take r as input, generate all permutations of the digits 0, 1, …, r in a matrix L, and for each row, i.e. each permutation or r-adic number, check the congruences modulo 1, …, r.
generate_div_numbers <- function(r) {
l = prod(1:r)
L = pracma::perms(c(0:(r-1)))
M = c()
for (i in 1:l) {
Li = L[i, ]
cs = cumsum(r^(0:(r-1)) * Li)
if (all(cs %% c(1:r) == 0)) {
m = as.numeric(paste0(rev(Li), collapse = ''))
M = c(M, m)
}
}
n = length(M); Ms = sort(M)
if (n > 0) {
cat(n, "solution(s) found.\n")
for (i in 1:n) {
cat(Ms[i], '|', r, '\n')
}
} else
cat("No solutions found.\n")
}The solutions found will be stored in a vector M. As a result, the number of solutions found will be printed as well as all solution, smallest ones first. After each number the base \(r\) is noted behind a bar ‘|’.
We will check it for some small values of r, for r=3 to check our earlier result, and r=5 and r=7 to see something new.
generate_div_numbers(3)
## 1 solution(s) found.
## 120 | 3
generate_div_numbers(5)
## 1 solution(s) found.
## 23140 | 5
generate_div_numbers(7)
## 1 solution(s) found.
## 3516240 | 7 It is not true that there is always a unique solution. For composite numbers \(r\) we find several solutions:
| r | no. solutions | smallest |
|---|---|---|
| 4 | 2 | 3120 |
| 6 | 12 | 512340 |
| 8 | 10 | 72451630 |
| 9 | 8 | 415823760 |
Coming back to our original puzzle with \(r=10\) we see many solutions.
generate_div_numbers(10)202 solution(s) found.
9123567480 | 10
9123675840 | 10
...
9873564120 | 10
9876351240 | 10We see for example that we can always interchange the second and third digit and get another solution, e.g. 9123567480 and 9213567480. There are more of these ‘interchanging’ rules. These rules indicate a “degree of freedom” from the divisibility rules and are the reason for the many solutions to exist.
For \(r = 12\) there are more than 2000 numbers of length 12 that fulfill all the divisibility rules.
Hunting for larger \(r\) values, we are in for a surprise:
generate_div_numbers(11)No solutions found.It seems that some of the divisibility rules– for example those for 3 and 11 – contradict each other and prevent any solutions for the puzzle. It is unclear whether this may happen for higher divisibility rules, too.
By the way, the same for \(r = 13\): there are no solutions, that is numbers of length 13 that fulfill all divisibility rules.
There appear to be more solution numbers if \(r\) is the product of smaller numbers. For instance, in the discussion for \(r=10\) we realized that the conditions for 2, 5, and 10 partly overlap and thus we end with a lesser number of restrictive conditions.
The same arguments as above prove that any such solution must end in a \(0\) digit. And in the case \(r\) is even, \(m_r=r-1\) is a must. For \(r\) uneven this is not the case as our examples show; instead \(m_r=\frac{r-1}{2}\) seems to be right.
It is unclear whether there is always a unique (or no) solution if \(r\) is prime. Actually, I expect it to be different.
Looking at this puzzle as a discrete satisfaction problem, another tool that can be applied is MiniZinc https://www.minizinc.org/. Setting up a constraint satisfaction model in a file div_rules_puzzle.mzn, one can find all cases up to \(r=16\) and also show that there is no solution for \(r=17\).
% 'Divisibility rules' Puzzle
include "alldifferent.mzn";
int: r = 16; % No. of digits
set of int: IDX = 1..r; % indices
array[IDX] of var 0..(r-1): D; % array of digits
constraint alldifferent(D); % all digits are different
constraint D[1] = 0; % we know the rightmost one
% constraint D[r] = r-1 % only true for r even
constraint forall (j in 2..(r-1))
(sum(i in 1..j) (D[i]*(r mod j)^(i-1)) mod j = 0);
solve satisfy;Assuming the command minizinc is part of the PATH environment variable, the following command solves the case \(r=16\).
$ minizinc div_rules_puzzle.mzn
Compiling div_rules_puzzle.mzn
Running div_rules_puzzle.mzn
D = array1d(1..16, [0, 2, 1, 4, 3, 14, 10, 8, 6, 7, 11, 12, 13, 5, 9, 15]);
----------
Finished in 85msecThus one solution in the hecadecimal system is: ‘F95DCB768AE34120’.
To get all solution one applies the a- option when calling MiniZinc with minizinc -a ... – for \(r=12\) there are really many of them. Note the short running time of 0.085 seconds.
For r=18 und r=19 we get an error message “integer overflow” because MiniZinc calculates with 32-bit integers, so intermediate results cannot be larger than \(2^{32}-1\).