Teaser 2843: Child’s play
From The Sunday Times, 19th March 2017 [link] [link]
Liam has a set of cards numbered from one to twelve. He can lay some or all of these in a row to form various numbers. For example the four cards:
6, 8, 11, 2
give the five-figure number 68112. Also, that particular number is exactly divisible by the number on each of the cards used.
In this way Liam used his set of cards to find another much larger number that was divisible by each of the numbers on the cards used — in fact he found the largest such possible number.
What was that number?
[teaser2843]
GeoffR, 
Frits are discussing. 
S2T2 
Jim Randell 11:29 am on 9 December 2021 Permalink |
To reduce the search space we can use some shortcuts.
Considering the cards that are included in the number, if the “10” card is included, then it would have to appear at the end, and would preclude the use of cards “4”, “8”, “12”.
Similarly if “5” is included, and any even card, then the number must end in “10” and the cards “4”, “8”, “12” are excluded.
If any of the cards “3”, “6”, “9”, “12” are included then the overall digit sum must be a multiple of 3.
Similarly if “9” is included, then the overall digit sum must be a multiple of 9.
If any of the even cards (“2”, “4”, “6”, “8”, “10”) are used, the resulting number must also be even.
This Python program uses a number of shortcuts. It considers the total number of digits in the number, as once a number is found we don’t need to consider any number with fewer digits. It runs in 263ms.
Run: [ @replit ]
from enigma import (enigma, irange, group, subsets, Accumulator, join, printf) # the cards cards = list(irange(1, 12)) # map cards to their digit sum, and number of digits dsum = dict((x, enigma.dsum(x)) for x in cards) ndigits = dict((x, enigma.ndigits(x)) for x in cards) # find maximum arrangement of cards in ss def find_max(ss): # look for impossible combinations if (10 in ss) and (4 in ss or 8 in ss or 12 in ss): return even = any(x % 2 == 0 for x in ss) if (5 in ss and even) and (4 in ss or 8 in ss or 12 in ss): return # calculate the sum of the digits ds = sum(dsum[x] for x in ss) # check for divisibility by 9 if (9 in ss) and ds % 9 != 0: return # check for divisibility by 3 if (3 in ss or 6 in ss or 12 in ss) and ds % 3 != 0: return # look for max rearrangement r = Accumulator(fn=max) fn = (lambda x: (lambda x: (-len(x), x))(str(x))) for s in subsets(sorted(ss, key=fn, reverse=1), size=len, select="P"): if even and s[-1] % 2 != 0: continue # done, if leading digits are less than current max if r.value and s[0] != r.data[0] and str(s[0]) < str(r.value): break # form the number n = int(join(s)) if all(n % x == 0 for x in ss): r.accumulate_data(n, s) return (r.value, r.data) # sort subsets of cards into the total number of digits d = group(subsets(cards, min_size=1), by=(lambda ss: sum(ndigits[x] for x in ss))) r = Accumulator(fn=max) for k in sorted(d.keys(), reverse=1): printf("[considering {k} digits ...]") for ss in d[k]: rs = find_max(ss) if rs is None: continue r.accumulate_data(*rs) if r.value: break printf("max = {r.value} [{s}]", s=join(r.data, sep=","))Solution: The number is 987362411112.
The cards are: (1, 2, 3, 4, 6, 7, 8, 9, 11, 12).
LikeLike
Frits 6:52 pm on 9 December 2021 Permalink |
If “5” is included then the number must end in “10” or “5” and the cards “4”, “8”, “12” are excluded (not relying on an even card). I got this from Brian’s solution on his puzzle site.
LikeLike
Jim Randell 10:04 am on 10 December 2021 Permalink |
@Frits: Good point.
So if “5” or “10” are used, none of “4”, “8”, “12” can be used. And vice versa, if “4”, “8” or “12” are used, none of “5” or “10” can be used. So at least 3 digits must be absent, and we can start the search from 12 digits.
Here’s a neater version of my code:
from enigma import (enigma, irange, group, subsets, mlcm, Accumulator, join, printf) # the cards cards = list(irange(1, 12)) # map cards to their digit sum, and number of digits dsum = dict((x, enigma.dsum(x)) for x in cards) ndigits = dict((x, enigma.ndigits(x)) for x in cards) # find maximum arrangement of cards in ss def find_max(ss): d = mlcm(*ss) even = any(x % 2 == 0 for x in ss) # look for max rearrangement r = Accumulator(fn=max) fn = (lambda x: (lambda x: (-len(x), x))(str(x))) for s in subsets(sorted(ss, key=fn, reverse=1), size=len, select="P"): if even and s[-1] % 2 != 0: continue # done, if leading digits are less than current max if r.value and s[0] != r.data[0] and str(s[0]) < str(r.value): break # form the number n = int(join(s)) if n % d == 0: r.accumulate_data(n, s) return (r.value, r.data) # reject impossible subsets def check(ss): # look for impossible combinations if (5 in ss or 10 in ss) and (4 in ss or 8 in ss or 12 in ss): return False # calculate the sum of the digits ds = sum(dsum[x] for x in ss) # check for divisibility by 9 if (9 in ss) and ds % 9 != 0: return False # check for divisibility by 3 if (3 in ss or 6 in ss or 12 in ss) and ds % 3 != 0: return False # looks OK return True # sort subsets of cards into the total number of digits d = group(subsets(cards, min_size=1), st=check, by=(lambda ss: sum(ndigits[x] for x in ss))) r = Accumulator(fn=max) for k in sorted(d.keys(), reverse=1): printf("[considering {k} digits ...]") for ss in d[k]: rs = find_max(ss) if rs is None: continue r.accumulate_data(*rs) if r.value: break printf("max = {r.value} [{s}]", s=join(r.data, sep=","))LikeLike
GeoffR 2:30 pm on 10 December 2021 Permalink |
In this first solution, I assumed it was reasonable for the largest number to start with the digits 9,8,7 to minimise a solution run-time. It also found the seven possible solutions for Liam’s numbers from which the maximum can be found.
from enigma import Timer timer = Timer('ST2843', timer='E') timer.start() from itertools import permutations # assume number from cards is ABCDEFGHIJ, with A = 9, B = 8 and C = 7 # Also no digit in A..J is 5 or 10 - see previous postings cards = set((1, 2, 3, 4, 6, 7, 8, 9, 11, 12)) # Assume first three digits must be 9, 8 and 7 to maximise Liam's number A, B, C = 9, 8, 7 a, b, c = str(A), str(B), str(C) cards2 = cards.difference([A, B, C]) Liam_nums = [] # permute remainder of cards for p1 in permutations(cards2, 7): D, E, F, G, H, I, J = p1 d, e, f, g = str(D), str(E), str(F), str(G) h, i, j = str(H), str(I), str(J) num = int(a + b + c + d + e + f + g + h + i + j) if all(num % d == 0 for d in (A, B, C, D, E, F, G, H, I, J)): if num not in Liam_nums: Liam_nums.append(num) # find largest number in the list print (f"Largest possible number = { max(Liam_nums)}") timer.stop() timer.report() # Largest possible number = 987362411112 #[ST2843] total time: 0.0151168s (15.12ms) print(Liam_nums) # There are only seven possible numbers in Liam's list: # [987162411312, 987111312264, 987241136112, 987211614312, # 987341621112, 987362411112, 987113624112]In the second solution, I did a full permutation solution for the 12 cards, which had an expected longer run-time, as there were over 6,300 potential numbers in the list.
from enigma import Timer timer = Timer('ST2843', timer='E') timer.start() from itertools import permutations # Assume digits 5 & 10 not included (previous postings) # Assume 10-digit number is ABCDEFGHIJ cards = set((1, 2, 3, 4, 6, 7, 8, 9, 11, 12)) Liam_nums = [] for p1 in permutations(cards): A, B, C, D, E, F, G, H, I, J = p1 a, b, c = str(A), str(B), str(C) d, e, f, g = str(D), str(E), str(F), str(G) h, i, j = str(H), str(I), str(J) num = int(a + b + c + d + e + f + g + h + i + j) if all(num % d == 0 for d in (A, B, C, D, E, F, G, H, I, J)): if num not in Liam_nums: Liam_nums.append(num) # find largest number in the list print (f"Largest possible number = { max(Liam_nums)}") timer.stop() timer.report() #Largest possible number = 987362411112 #[ST2843] total time: 9.1977548s (9.20s)LikeLike