Teaser 2666: Multiple calls
From The Sunday Times, 27th October 2013 [link] [link]
In my office each of the 100 employees has a different two-digit phone number, from 00 to 99. Recently my phone was rewired so that each number button generated an incorrect digit. Trying to phone four of my colleagues resulted in me calling double the intended number, and, for more than ten of my colleagues, trying to phone their number resulted in me calling triple the intended number. Also if I tried to phone any colleague and then asked for their phone number, then phoned that number and asked that person for their number, then phoned that number … and so on, it always took ten calls to contact the person I intended.
If I tried to phone the numbers 01, 23, 45, 67 and 89 respectively, which numbers would I actually get?
[teaser2666]
Frits are discussing. 
S2T2 
Jim Randell 3:09 pm on 15 January 2024 Permalink |
Numbers that map to their double must be in the range 01 – 49, and numbers that map to their triple in the range 01 – 33, and we need more than 10 of them.
If start with any number we always get a chain of 10 numbers before we reach the intended number. So the reassignment of digits must form a complete (length 10) cycle.
We could generate all possible complete cycles and look for any that meet the remaining conditions, but this is a slow approach (although quite short to program).
This Python program considers possible mappings that give 11 or more numbers that map to their triple, and then attempts to fill out the remaining values such that a complete cycle is formed.
It runs in 73ms. (Internal runtime is 9.9ms).
Run: [ @replit ]
from enigma import (irange, diff, subsets, peek, map2str, printf) digits = list(irange(0, 9)) # check a mapping is a complete cycle def is_cycle(m): if not m: return k = peek(m.keys()) (v, n) = (m[k], 1) while v != k: v = m[v] n += 1 return n == len(m.keys()) # update a mapping def update(m, ks, vs): m = m.copy() for (k, v) in zip(ks, vs): # must be a derangement if k == v: return # existing key if k in m: if m[k] != v: return else: # new key if v in m.values(): return # make the update m[k] = v return m # construct mappings with more than 10 triples def solve(k=0, m=dict(), ts=set()): # are we done? if k > 33: if len(ts) > 10: yield m else: # consider mapping k -> 3k m_ = update(m, divmod(k, 10), divmod(3 * k, 10)) if m_: yield from solve(k + 1, m_, ts.union({k})) # or not if m_ != m: yield from solve(k + 1, m, ts) # look for potential mappings for r in solve(): # map remaining keys to remaining values ks = diff(digits, r.keys()) vs = diff(digits, r.values()) for ss in subsets(vs, size=len, select='P'): m = update(r, ks, ss) # the map must form a complete cycle if not is_cycle(m): continue # find doubles and triples (ds, ts) = (list(), list()) for k in irange(0, 49): (a, b) = divmod(k, 10) v = 10 * m[a] + m[b] if v == 2 * k: ds.append(k) if v == 3 * k: ts.append(k) # we need exactly 4 doubles and more than 10 triples if not (len(ds) == 4 and len(ts) > 10): continue # output solution printf("{m}", m=map2str(m, arr="->", enc="")) printf("doubles = {ds}") printf("triples = {ts}") printf()Solution: 01 → 13; 23 → 69; 45 → 20; 67 → 84; 89 → 57.
So the 4 numbers that map to their doubles are:
and the 11 numbers that map to their triples are:
LikeLike
Frits 2:34 pm on 19 January 2024 Permalink |
Nice solution.
I also tried the same setup starting with mappings of exactly 4 doubles but that was a lot slower.
I can’t find the “Run” button anymore when using the replit link.
LikeLike
Jim Randell 5:38 pm on 19 January 2024 Permalink |
It looks like replit have changed their interface so you can no longer directly run someone else’s code. Now you need to fork it to your own account before you can run it.
It seems like this means you can no longer use replit to share code as easily as before, which is a bit annoying.
LikeLike