Teaser 2674: Roll model
From The Sunday Times, 22nd December 2013 [link] [link]
My new board game has squares numbered from 1 to 100 and has two unusual dice. The first die is 10-sided with numbers from 1 to 10, and the second is 4-sided with a prime number on each side. A move consists of throwing the two dice and then choosing either one of the numbers or their sum and moving that number of squares in either direction. I found myself on one square and realised that there were just two squares which it would be impossible for me to reach with my next move. Both of those squares had prime numbers that did not appear on the dice.
(a) Which particular square was I on?
(b) What are the four numbers on the second die?
[teaser2674]
Lise Andreasen, 
Frits, 
GeoffR and 
S2T2 
Jim Randell 10:10 am on 26 March 2024 Permalink |
There are (10 + 4 + 10×4) = 54 possible scores, and we can move in either direction.
So, when we start on a square the reachable squares spread out from it in both directions. If we have 56 consecutive numbers, and we can make 54 of them using the dice, this would be the maximum possible. And so the largest possible square we can be on is 57 and the smallest possible is 44. And we can’t afford more than 6 non-usable scores.
We cannot afford more than 1 gap in the scores from 1 to 43 (as any gaps will be mirrored on the other side), or more than 2 gaps overall (if they are close to the end, the gaps could be on the same side – although this seems improbable if they are both primes).
This Python program considers possible sets of primes on the second die, and let looks for an appropriate starting square. (We could just consider all possible combinations of primes, but it is a bit faster check we don’t introduce too many gaps or overlaps as we build up the sets).
It runs in 58ms. (Internal runtime is 1.3ms).
Run: [ @replit ]
from enigma import (irange, primes, printf) # squares on the board squares = set(irange(1, 100)) # die 1 d1 = list(irange(1, 10)) # fill out die 2 def die2(ns, d1, ds, d2=list()): k = len(d2) if k == 4: yield (d2, ds) else: # choose the next number on die 2 for (i, n) in enumerate(ns): # update the set of deltas ds_ = ds.union([n], (n + x for x in d1)) m = 11 * k + 10 # check for overlaps and gaps if len(ds_) < m + 5: continue if len(set(irange(1, m)).difference(ds_)) > (1 if k < 3 else 2): continue # fill out the remaining faces yield from die2(ns[i:], d1, ds_, d2 + [n]) # die 2 has 4 [different] primes ps = list(primes.between(5, 50)) # consider possible die 2 and deltas for (d2, ds) in die2(ps, d1, set(d1)): n = len(ds) # consider starting on square i for i in irange(98 - n, 5 + n): # find unreachable squares missing = squares.difference((i - x for x in ds), (i + x for x in ds), [i]) # there are exactly 2 primes missing, that are not on d2 if len(missing) != 2: continue if any(x in d2 or x not in primes for x in missing): continue # output solution printf("die2={d2}; square={i}; missing={missing}", missing=sorted(missing))Solution: (a) You were on square 51; (b) The numbers on the second die are: 11, 23, 31, 41.
And the squares that cannot be reached are 29 and 73.
Manually we can adopt a “greedy” strategy to maximise the reach of the dice while minimising the gaps:
Die 10 will cover deltas 1..10 on either side, and if 11 is not on die 2, then both deltas of 11 and 12 are unreachable, which would make at least 4 unreachable squares (2 on each site). So 11 must be on die 2 and we can cover deltas 1..21.
The next missing delta is now 22 (which is not prime), so we either leave 22 as unreachable, or we put a prime less than 22 on die 2.
If we leave 22 as unreachable, and put 23 on die 2 then we can cover deltas 1..33, our unreachable values are at ±22, and we can’t have any more gaps.
The next missing delta is 34, which is not a prime, so the largest prime we can add to die 2 is 31, which means we can cover deltas 1..41 (except 22).
The next missing delta is 42, so the largest prime we can add is 41, and so with die 2 = (11, 23, 31, 41) we can cover deltas 1..51 (except 22).
Starting on squares 49..52 we have the following unreachable squares:
So we have found a single candidate solution, but we can continue and confirm this is the only candidate:
If we choose to cover 22, by placing the largest possible prime (i.e. 19) on die 2, then we can cover deltas 1..29.
The next missing delta is now 30, we could choose to leave ±30 unreachable, and place 31 on die 2, so we can cover 1..41 (except 30).
And then we place 41 on die 2, and we can cover 1..51 (except 30).
This gives the following unreachable squares with die 2 = (11, 19, 31, 41):
This gives no solutions.
So we need to cover 30, so we place 29 on die 2, we can then cover deltas 1..39.
We can leave 40 as unreachable and place 41 on die 2, and we cover 1..51 (except 40).
This gives the following unreachable squares with die 2 = (11, 19, 29, 41):
This gives no solutions.
So we need to cover 40, so we place 37 on die 2, and we cover 1..47, and this is not enough to leave just 2 unreachable squares.
And we have found no further candidate solutions.
LikeLike
Hugo 11:39 am on 26 March 2024 Permalink |
A ten-sided die is not very practical, and a tetrahedron doesn’t roll.
I suggest using an icosahedron and an octahedron, with each number occurring twice
(for example, on opposite faces).
LikeLike
Jim Randell 12:23 pm on 26 March 2024 Permalink |
@Hugh: I think I have seen 10 sided dice based on a pentagonal trapezohedron [@wikipedia]. You could also roll a long dodecahedral prism. A square prism might not be so good though.
LikeLike
Lise Andreasen 4:34 pm on 4 April 2024 Permalink |
There are standard 4 and 10 sided easily available, among other things for paper RPG.
LikeLike
Frits 10:47 pm on 26 March 2024 Permalink |
# primes up to 100 P = [3, 5, 7] P = [2] + P + [x for x in range(11, 100, 2) if all(x % p for p in P)] # this program tries to follow Jim's manual solution. # for delta's 1 - 43 we can afford to miss one delta # add a new prime allowing only 1 gap for the first 43 delta's def solve(d, ds=[], skip=0): if len(ds) == 4: # check number of possible reachable squares if 2 *(ds[-1] + 10 - (skip > 0)) > 96: yield (ds, skip) else: # try to make delta <d> or ... if d in P: yield from solve(d + 11, ds + [d], skip) else: # largest prime we can add to die 2 lp = [p for p in P if p < d and p != skip][-1] yield from solve(lp + 11, ds + [lp], skip) # ... leave delta <d> as unreachable if not skip: yield from solve(d + 1, ds, d) # deltas 1-10 will be covered by the first die for d2, skip in solve(11): # we can cover deltas 1..r except possible <skip> r = d2[-1] + 10 # one delta must have been skipped, otherwise the number of possible # reachable squares is too low # consider starting on square <pos> for pos in range(100 - r, r + 2) : # non-reachables nr = [pos - skip, pos + skip] if any(x for x in nr if x not in P or x in d2): continue print(f"answer: Peter was on square {pos}, " f"the four numbers on the second die are: {d2}")LikeLike