Teaser 2979: Mischievous Sam
From The Sunday Times, 27th October 2019 [link] [link]
I set Sam a question, the answer to which was a 3-digit number, with the digits increasing by 1 from first to last (e.g. 789).
Sam eventually produced a 3-digit answer, but only 2 of his digits were correct and in the correct position. The third digit was wrong.
Investigating further I found that Sam had the correct answer but, for devilment, decided to change it into a different (single-digit) base.
If I were to tell you which of his 3 digits was the wrong one, you should be able to tell me:
(a) the correct answer, and;
(b) the base used by Sam.What are they?
[teaser2979]
Frits, 
GeoffR, and 
S2T2 
Jim Randell 10:36 pm on 25 October 2019 Permalink |
There are only 7 possible 3-digit decimal results, and each of these can only be expressed as a 3-digit number in a limited number of single digit integer bases, so the search space is very small.
The following Python program runs in 82ms.
Run: [ @repl.it ]
from enigma import (defaultdict, irange, tuples, nconcat, cbrt, intc, nsplit, int2base, printf) # record numbers by the position of the incorrect digit r = defaultdict(list) # consider sequences of 3 consecutive increasing digits for ds in tuples(irange(1, 9), 3): n = nconcat(ds) # consider the digits of n in other bases for b in irange(intc(cbrt(n)), 9): bs = nsplit(n, base=b) # find the positions of digits that differ ps = list(i for (i, (b, d)) in enumerate(zip(bs, ds)) if b != d) if len(ps) != 1: continue printf("[{n} = {m} (base {b}) -> {ps}]", m=int2base(n, b)) r[ps[0]].append((n, b)) # find unique solutions for (k, vs) in r.items(): if len(vs) != 1: continue # output solution (n, b) = vs[0] printf("incorrect {k} -> {n} = {m} (base {b})", m=int2base(n, b))Solution: (a) The correct answer is 123; (b) Sam used base 8.
The only possible solutions are:
The first and third of these differ from the decimal representation in the first (most significant) digit. Which leaves the second (which differs in the second digit) as the solution.
If we allow bases higher than 9 we find there is one further potential candidate solution:
But this differs from the decimal representation in the first digit, so would not change the answer to the puzzle.
LikeLike
GeoffR 7:54 pm on 28 October 2019 Permalink |
I used a number base calculator to give an assisted manual solution.
Link: https://www.rapidtables.com/convert/number/base-converter.html?x=456&sel1=10&sel2=9
LikeLike
GeoffR 11:34 am on 3 November 2019 Permalink |
from time import perf_counter_ns start = perf_counter_ns() def nbr_to_base(num, base): dgts = [] while num: num, r = divmod(num, base) dgts.append(r) return ''.join(str(x) for x in reversed(dgts)) def diff_pos(n1, n2): # Split each of two numbers into three digits a, b, c = n1 // 100, n1 // 10 % 10, n1 % 10 d, e, f = n2 // 100, n2 // 10 % 10, n2 % 10 # check 2 of the 3 digits are in correct position # and only one digit is in the wrong position in Sam's number # check if 1st and 2nd digits are in correct position if a == d and b == e and c != f: return 3 # check if 1st and 3rd digits are in correct position if a == d and c == f and b != e: return 2 # check if 2nd and 3rd digits are in correct position if b == e and c == f and a != d: return 1 return 0 # 3-digit numbers with digits increasing by 1 from first to last for num in (123, 234, 345, 456, 567, 678, 789): for nb in range(4, 10): N = nbr_to_base(num, nb) if 100 < int(N) < 1000: dp = diff_pos(num, int(N)) if dp: print(f"Answer {num} ({N} in base {nb}) differs in position {dp}", end='') print(f" (in {(perf_counter_ns() - start) / 1e6:.3f} milliseconds)") # Answer 123 (323 in base 6) differs in position 1 (in 8.936 milliseconds) # Answer 123 (173 in base 8) differs in position 2 (in 16.619 milliseconds) # Answer 456 (556 in base 9) differs in position 1 (in 35.507 milliseconds)The first and third solutions both give the incorrect digit as the first position, so we cannot tell the incorrect digit from these two solutions.
The second solution gives a single position for the incorrect digit position, so this is the answer i.e Answer 123 (173 in base 8) differs in position 2.
LikeLike
Frits 12:05 pm on 8 April 2021 Permalink |
I wanted to test the filter_unique function with a complex lambda function otherwise Jim’s line 16 approach could have been used. The “correct” function is taken from Mastermind puzzles.
# calculate the number of dead-right's correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys)) # ceil a positive number ceil = lambda n: int(n) if n == int(n) else int(n) + 1 # convert from integer to any base number def int2base(n, b, D="0123456789abcdefghijklmnopqrstuvwxyz"): return D[0] if not n else (int2base(n // b, b)).lstrip(D[0]) + D[n % b] # return all entries where f(x) occurs only once # or where f(x) occurs more than once def filter_unique(seq, f=lambda x: x, mode="unique"): d = dict() for s in seq: d[f(s)] = f(s) in d if mode == "unique": # occuring only once return [s for s in seq if not d[f(s)]] else: # occuring more than once return [s for s in seq if d[f(s)]] li = [] # 3-digit numbers with digits increasing by 1 from first to last for n in (123, 234, 345, 456, 567, 678, 789): # limit the used bases so they result in a 3 digit number for b in range(ceil(n ** (1 / 3)), int(n ** 0.5) + 1): N = int2base(n, b) # Sam eventually produced a 3-digit answer if not N.isdigit(): continue # if 2 digits are correct the other must be incorrect if correct(str(n), N) == 2: li.append((str(n), N, b)) f = filter_unique(li, lambda s: [i for i, x in enumerate(s[0]) if x not in s[1]][0]) if len(f) == 1: print(f"correct answer = {f[0][0]}, Sam's base = {f[0][-1]}")LikeLike