A Brain-Teaser: [Multiples of 11]
From The Sunday Times, 9th June 1957 [link]
In how many different ways can the following groups of digits be arranged so that the resultant number is a multiple of 11?
(a) 1, 2, 3, 4, 5.
(b) 1, 2, 3, 4, 5, 6.
(c) 1, 2, 3, 4, 5, 6, 7.
This is one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of £5 was offered.
This puzzle was originally published with no title.
[teaser-1957-06-09] [teaser-unnumbered]
GeoffR and 
Frits, and 
Hugh Casement, 
Jim Olson and 
Tony Brooke-Taylor, 
John Crabtree, and 
S2T2 
Jim Randell 9:36 am on 31 October 2021 Permalink |
Again, the advent of computers means that this problem can be tackled with a very simple program, that constructs all possible rearrangements of the digits, and counts those that are divisible by 11.
The following Python program runs in 56ms.
Run: [ @replit ]
from enigma import (subsets, nconcat, icount, printf) # find numbers that are multiples of 11 def m11s(ds): for ss in subsets(ds, size=len, select="P"): n = nconcat(ss) if n % 11 == 0: yield n for ds in [(1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6, 7)]: t = icount(m11s(ds)) printf("{ds} -> {t}")Solution: (a) 0; (b) 0; (c) 576.
We can be a bit cleverer though.
One test for divisibility by 11 is to calculate the alternating sum of the digits (i.e. 1st digit − 2nd digit + 3rd digit − 4th digit + …), and if this is divisible by 11, then the original number is divisible by 11. And it also means that any number formed by rearrangement of the digits, providing the digits originally in odd positions are still in odd positions (and the digits in even positions are still in even positions), will also be divisible by 11.
The following Python program is a longer, but more efficient method of counting the numbers. (And indeed the internal runtime decreases from 9.03ms to 151µs).
from enigma import (subsets, factorial, printf) # count the number of multiples of 11 that can be made from digits ds def count_m11s(ds): r = 0 t = sum(ds) # consider the 2nd, 4th, ... digits n = len(ds) k = n // 2 for ss in subsets(ds, size=k): if (t - 2 * sum(ss)) % 11 == 0: r += factorial(k) * factorial(n - k) return r for ds in [(1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6, 7)]: t = count_m11s(ds) printf("{ds} -> {t}")In the case of the digits (1, 2, 3, 4, 5, 6, 7), we find that the following numbers in (odd) and (even) positions will form multiples of 11:
Each collection of digits contributes factorial(4) × factorial(3) = 144 numbers to the total.
So the answer is: 4 × 144 = 576.
LikeLike
GeoffR 12:37 pm on 31 October 2021 Permalink |
from itertools import permutations cnt5, cnt6, cnt7 = 0, 0, 0 # 5 consecutive digits - divisibility by 11 for p1 in permutations((1,2,3,4,5)): a,b,c,d,e = p1 num1 = 10000*a + 1000*b + 100*c + 10*d + e if num1 % 11 == 0: cnt5 += 1 print('5 digits divisibility count = ', cnt5) # 6 consecutive digits - divisibility by 11 for p2 in permutations((1,2,3,4,5,6)): a,b,c,d,e,f = p2 num2 = 100000*a + 10000*b + 1000*c + 100*d + 10*e + f if num2 % 11 == 0: cnt6 += 1 print('6 digits divisibility count = ', cnt6) # 7 consecutive digits - divisibility by 11 for p3 in permutations((1,2,3,4,5,6,7)): a,b,c,d,e,f,g = p3 num3 = 1000000*a + 100000*b + 10000*c + 1000*d + 100*e + 10*f + g if num3 % 11 == 0: cnt7 += 1 print('7 digits divisibility count = ', cnt7) # 5 digits divisibility count = 0 # 6 digits divisibility count = 0 # 7 digits divisibility count = 576LikeLike