Teaser 3175: Blindfold roulette
From The Sunday Times, 30th July 2023 [link] [link]
Our roulette wheel has fewer than 100 equal-sized sectors. Before each game a fixed number (fewer than half) of the sectors are randomly designated winning ones and the others as losing. A player can see which are the winning sectors, then is blindfolded. A ball is then placed at random in a winning sector and the player chooses to spin (S) the wheel or move (M) the ball clockwise by one sector. The game continues from there (the player has the same choices) and ends when the ball lands in a losing sector.
Alf’s longest winning run was MMSM while Bert’s was SSS and Charlie’s was MMMS. Being expert logicians, they had always chosen the option that gave the better chance of the ball landing in a winning sector. Remarkably, the probabilities of achieving each run of success were the same.
How many sectors are there and how many are winning sectors?
[teaser3175]
Frits, 
Tony Brooke-Taylor are discussing. 
GeoffR, 
Hugo are discussing. 
Pete Good, and 
S2T2 
Jim Randell 6:55 pm on 28 July 2023 Permalink |
This is my first stab at a program that explores the solution space looking for viable solutions. It is not very fast (it runs in 1.31s), and it stops after the first viable solution is found. (A second viable solution is eliminated by rejecting situations where both plays have the same probability).
It works by considering possible the total number of sectors n, and the number of winning sectors w, and then dividing the winning sectors into contiguous clumps, and calculating the corresponding probabilities.
Run: [ @replit ]
from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf) Q = Rational() # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq> def prob(n, w, ws, seq): P = 1 # calculate probability of a good spin S = Q(w, n) # calculate probability of a good move zs = ws # winning zones for v in seq: z = sum(zs) zs = list(x - 1 for x in zs if x > 1) M = Q(sum(zs), z) # check the sequence if v == 'M' and M > S: P *= M elif v == 'S' and S > M: P *= S zs = ws else: return return P # with <n> sectors, <w> winning, collect common probabilities for sequences <ss> def solve(n, w, ss): # collect probabilities d = dict((k, set()) for k in ss) # break the sectors into k contiguous blocks for k in irange(1, w): for ws in decompose(w, k, increasing=1, sep=0, min_v=1): # calculate the probabilities for A, B, C for (k, v) in d.items(): P = prob(n, w, ws, k) if P is not None: v.add(P) # return common probabilities return intersect(d.values()) # solve the puzzle def main(): # consider number of sectors <n> for n in irange(9, 99): # consider number of winning sectors <w> for w in irange(4, divf(n - 1, 2)): # find common probabilities ps = solve(n, w, ['MMSM', 'SSS', 'MMMS']) if ps: printf("n={n} w={w} -> P={ps}", ps=seq2str(ps)) return # stop at the first solution main()Solution: There are 54 sectors in total, and 18 winning sectors.
In this case the probability of a good spin is:
So the probability of B’s run of SSS is:
And a configuration where each winning sector is isolated from the other winning sectors makes the probability of a good M move zero, so this is possible (although this is not the only viable configuration to permit this – there are 19 in total).
For A there are 2 possible configurations, one of them is:
Of the 18 winning sectors there are 9 that have a winning sector as a clockwise neighbour:
And of those 9 sectors only 4 of them have 2 neighbouring winning sectors going clockwise:
And there are no winning sectors with 3 neighbouring clockwise winning sectors:
So at this point A would choose S, which resets the situation back to the start, so the next choice (if he gets one) would be M.
Hence the overall probability of MMSM is:
which is the same as B’s run.
For C, with a configuration (chosen from 9 possibilities) of:
We get:
However if we permit situations where the probabilities of M and S are equal then there is a further solution with 64 total sectors and 16 winning sectors.
The probability of a good S is:
And choosing a configuration (of 12 the possible configurations) where each winning sector is isolated we get:
For A the only possible distribution is:
which gives:
And for C there are 14 possible distributions, we choose:
which gives:
So in order for the puzzle to have a unique answer, we have to eliminate scenarios where when choosing between M and S that calculated probabilities are the same
LikeLike
Jim Randell 10:55 am on 30 July 2023 Permalink |
By analysing the probabilities associated with the given sequences (which I will post later) we can eliminate a lot of the testing done by my program above.
Here it is adapted to include the conditions:
(This last condition is the same as suggested by Frits in his comment below).
It calculates the probability for B, and then finds example decompositions for A and C that give the same probability.
This Python program fully explores the solution space and runs in 92ms. (Internal runtime is 27ms).
Run: [ @replit ]
from enigma import (Rational, irange, divf, div, decompose, first, printf) Q = Rational() # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq> def prob(n, w, ws, seq): P = 1 # calculate probability of a good spin S = Q(w, n) # calculate probability of a good move (zs, d) = (ws, w) # winning zones for v in seq: # calculate new zones zs = list(x - 1 for x in zs if x > 1) n = sum(zs) M = Q(n, d) # check the sequence if v == 'M' and M > S: P *= M d = n elif v == 'S' and S > M: P *= S (zs, d) = (ws, w) else: return return P # with <n> sectors, <w> winning, sequence <seq> # find winning clumps <ws> that give probability <p> # subject to max(<ws>) >= <m> def solve(n, w, seq, m, p): for k in irange(1, w): for ws in decompose(w, k, increasing=1, sep=0, min_v=1): if ws[-1] < m: continue if prob(n, w, ws, seq) == p: yield ws # consider possible n, w values such that n^2 divides w^3 for n in irange(9, 99): for w in irange(4, divf(n - 1, 2)): k3 = div(w**3, n**2) if k3 is None: continue # calculate probability for B (SSS) # a split into <w> clumps of size 1 will do B = prob(n, w, [1] * w, "SSS") # find examples for C (MMMS) and A (MMSM): # for A we need at least one clump of size 3 or more As = first(solve(n, w, "MMSM", 3, B), 1) if not As: continue # for C we need at least one clump of size 4 or more Cs = first(solve(n, w, "MMMS", 4, B), 1) if not Cs: continue # output solution printf("n={n} w={w} -> P={B}, A={As} C={Cs}")Here is the analysis:
C was able to make 3 consecutive Ms, so there must have been a block of at least 4 contiguous winning sectors in that game. Hence the wheel must have at least 9 sectors in total.
Similarly in the game where A made 2 consecutive Ms, there must have been a block of at least 3 contiguous winning sectors.
If the wheel has n sectors in all, and w winning sectors, then the probability of winning on a spin is:
(which is less than 50% by definition).
So for B we have:
regardless of the configuration of the winning sectors.
Except we also require there to be some configuration where:
But if every winning sector is in a clump of 1 (which is possible as there are fewer than half winning sectors) we have:
so the inequality above can be satisfied.
Now if we consider a situation where k1 of the winning sectors are “good” (i.e. they are directly anti-clockwise from another winning sector), then we have:
For the next move suppose only k2 of the k1 sectors are “good”, we have:
and so on:
where: (w, k1, k2, k3) form a decreasing sequence.
And so for C we have:
And this must be the same as P(SSS) above:
So: n² must divide into w³ (as k3 is an integer).
This narrows us down to just 4 possible (n, w) pairs:
Which have give the following probabilities for B
And for C gives k3 values of:
For A we get:
Giving the following k1.k2 values:
So there are only 2 pairs to consider, and we need to find appropriate decompositions of the winning sectors for A and C that give the appropriate probability (same as B), and where the choice to play M or S is always that with the larger probability.
LikeLike
Frits 2:01 pm on 29 July 2023 Permalink |
Extra analysis:
for MMMS we have sum(x – 3 for x in ws if x > 3) * n^2 = w^3
for MMSM we have sum(x – 1 for x in ws if x > 1) * sum(x – 2 for x in ws if x > 2) *n^2 = w^4
This adaptation of Jim’s program checks the full solution space in 30ms.
from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf) Q = Rational() # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq> def prob(n, w, ws, seq): P = 1 # calculate probability of a good spin S = Q(w, n) # calculate probability of a good move zs = ws # winning zones for v in seq: z = sum(zs) zs = list(x - 1 for x in zs if x > 1) M = Q(sum(zs), z) # check the sequence if v == 'M' and M > S: P *= M elif v == 'S' and S > M: P *= S zs = ws else: return return P if P == S**3 else None # with <n> sectors, <w> winning, collect common probabilities for sequences <ss> def solve(n, w, ss): # collect probabilities d = dict((k, set()) for k in ss) w3byn2, w4byn2 = w**3 // n**2, w**4 // n**2 # break the sectors into k contiguous blocks for k in irange(1, w): for ws in decompose(w, k, increasing=1, sep=0, min_v=1): # we have a solution if P = (w/n)^3 has been found for both MMSM and MMMS if d[ss[0]] and d[ss[2]]: return d[ss[0]] fn = lambda s, y: sum(x - y for x in s if x > y) # check if P can be calculated as (w/n)^3 if (fn(ws, 3) != w3byn2 or d[ss[2]]) and \ (fn(ws, 1) * fn(ws, 2) != w4byn2 or d[ss[0]]): continue # calculate only the probabilities for MMSM and MMMS # (as P for SSS equals (w/n)^3 if ws = [1, 1, ..., 1, 1]) for s in [ss[0], ss[2]]: P = prob(n, w, ws, s) if P: d[s] = {P} # return common probabilities return intersect(d.values()) # solve the puzzle def main(): # consider number of sectors <n> for n in irange(9, 99): # consider number of winning sectors <w> for w in irange(4, divf(n - 1, 2)): # skip early if probability for MMSM and MMMS can't be (w/n)^3 if w**4 % n**2 or w**3 % n**2: continue # find common probabilities ps = solve(n, w, ['MMSM', 'SSS', 'MMMS']) if ps: printf("n={n} w={w} -> P={ps}", ps=seq2str(ps)) # continue to check the full solution space main()LikeLike
Frits 9:04 pm on 30 July 2023 Permalink |
Trying to perform decomposition with SubstitutedExpression().
In order to not use too many variables the maximum number of decomposition variables is calculated.
The programs runs in 185ms.
from enigma import SubstitutedExpression, divf, div # function used in probability formula for M fn = lambda s, y: sum(x - y for x in s if x > y) symbols = "ABCDEFGHIJKLMNOPQRabcdefghijklmopqrtuvxyx" syms2 = ["ST", "UV", "WX", "YZ"] # consider possible n, w values such that n^2 divides w^3 for n in range(9, 100): for w in range(4, divf(n - 1, 2) + 1): if w**3 % n**2: continue # try to decompose <w> into A, B, .. , xx # maximum number of elements to decompose <w> mx = (w + 1) - (w**2 // n + 2) # maximum number of 2-digit variables needed n2 = w // 10 # invalid digit / symbol assignments d2i = {d: set() for d in range(10)} for i in range(n2 - 1): for d in range((w // (n2 - i)) // 10 + 1, 10): d2i[d].add(syms2[i][0]) # build expressions exprs = [] for i in range(mx - 1): j = mx - n2 - i cur = symbols[i] if j > 0 else syms2[-j] nxt = symbols[i + 1] if j > 1 else syms2[0] if j == 1 else syms2[(1 - j)] if i < mx - 2: exprs.append(f"{{{cur}}} <= {{{nxt}}}") else: exp = f"{{{cur}}} <= {{{nxt}}}" # save for later # restrict values of single digit variables if len(cur) == 1: for d in range(w // (mx - i) + 1, 10): d2i[d].add(cur) else: # restrict values by adding an expression exprs.append(f"{{{cur}}} <= {w // (mx - i)} ") vars = [f"{{{s}}}" for s in symbols[:mx - n2]] vars += [f"{{{s}}}" for s in syms2[:n2]] svars = ','.join(vars) # direct assignment of last variable exprs.append(f"{w} - sum([{','.join(vars[:-1])}]) = {vars[-1]}",) exprs.append(exp) exp = "" # for MMMS we have sum(x – 3 for x in ws if x > 3) * n^2 = w^3 exp += f"(c1 := (fn(svars:= [{svars}], 3) * {n**2} == {w**3}) and " exp += f"{n} * fn([{svars}], 1) > {w**2} and " exp += f"{n} * fn([{svars}], 2) > {w} * fn([{svars}], 1) and " exp += f"{n} * fn([{svars}], 3) > {w} * fn([{svars}], 2) and " exp += f"{n} * fn([{svars}], 4) < {w} * fn([{svars}], 3)) or " # for MMSM we have sum(x – 1 for x in ws if x > 1) * # sum(x - 2 for x in ws if x > 2) * n^2 = w^4 exp += f"(c2 := (fn([{svars}], 1) * fn([{svars}], 2) * {n**2} == {w**4}) " exp += f"and {n} * fn([{svars}], 1) > {w**2} and " exp += f"{n} * fn([{svars}], 2) > {w} * fn([{svars}], 1) and " exp += f"{n} * fn([{svars}], 3) < {w} * fn([{svars}], 2))" exprs.append(exp) # the alphametic puzzle p = SubstitutedExpression( exprs, answer="c1, c2, vars", d2i=d2i, distinct="", env=dict(fn=fn), reorder=0, verbose=0, # use 256 to see the generated code ) # print answers cnts = [0, 0] for ans in p.answers(): #print(f"{ans}") if ans[0]: cnts[0] = 1 if ans[1]: cnts[1] = 1 if cnts == [1, 1]: print(f"answer: n={n}, w={w}") breakLikeLike
Tony Brooke-Taylor 7:11 pm on 3 August 2023 Permalink |
You can do a lot with Frits’ MMMS result and the limits for n and w, to constrain the search space. I used a slightly different paradigm from Jim’s, considering numbers of winning segments with clockwise winning neighbours, so my nomenclature is a bit different. Also I am coding in Rust now so won’t reproduce my solution here. However, I have written up a solution which can be applied manually in the comments of my code at:
https://github.com/TuonyBT/teaser3175/blob/master/src/main.rs
LikeLike
Frits 9:52 pm on 8 August 2023 Permalink |
There is a different answer (n=64, w=16) when a winning run is supposed to be followed by a loss.
from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf) fn = lambda s, y: sum(x - y for x in s if x > y) Q = Rational() # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq> def prob(n, w, ws, seq, target): P = 1 # calculate probability of a good spin S = Q(w, n) # calculate probability of a good move zs = ws # winning zones for v in seq: z = sum(zs) zs = list(x - 1 for x in zs if x > 1) M = Q(sum(zs), z) # check the sequence if v == 'M' and M > S: P *= M elif v == 'S' and S > M: P *= S zs = ws else: return P *= (1 - fn(ws, 1) / w) if seq[-1] == 'S' else (1 - fn(ws, 2) / fn(ws, 1)) return P if P == S**3 * (n - w) / n else None # with <n> sectors, <w> winning, collect common probabilities for sequences <ss> def solve(n, w, ss): # collect probabilities d = dict((k, set()) for k in ss) # probability for winning run SSS F = (n - w) * w**4 / n**3 # maximum number of elements to decompose <w> mx = (w + 1) - (w**2 // n + 2) # break the sectors into k contiguous blocks for k in irange(1, mx): for ws in decompose(w, k, increasing=1, sep=0, min_v=1): # we have a solution if P = (w/n)^3 has been found for both MMSM and MMMS if d[ss[0]] and d[ss[2]]: return d[ss[0]] # check if P can be calculated as F if (fn(ws, 3) * w - fn(ws, 1) * fn(ws, 3) != F or d[ss[2]]) and \ (fn(ws, 1) * fn(ws, 2) - fn(ws, 2)**2 != F or d[ss[0]]): continue # calculate only the probabilities for MMSM and MMMS # (as P for SSS equals F if ws = [1, 1, ..., 1, 1]) for s, t in [(ss[0], (w/n)**3 ), (ss[2], (w/n)**3)]: P = prob(n, w, ws, s, t) if P: d[s] = {P} # return common probabilities return intersect(d.values()) # fn(a, b) = sum(x – b for x in a if x > b) # for SSS we have probablility (w/n)**3 * (n - w) / n # for MMMS we have fn(ws, 3) * w - fn(ws, 1) * fn(ws, 3) = (n - w) * w**4 / n**3 # for MMSM we have fn(ws, 1) * fn(ws, 2) - fn(ws, 2)**2 = (n - w) * w**4 / n**3 # solve the puzzle def main(): # consider number of sectors <n> for n in irange(9, 99): # consider number of winning sectors <w> for w in irange(4, divf(n - 1, 2)): # skip if probability for MMSM and MMMS can't be (w/n)^3 * (n - w) / n if (w**4 * n - w**5) % n**2: continue # find common probabilities ps = solve(n, w, ['MMSM', 'SSS', 'MMMS']) if ps: printf("\nn={n} w={w} -> P={ps}\n", ps=seq2str(ps)) # continue to check the full solution space main()LikeLike
Jim Randell 10:08 pm on 9 August 2023 Permalink |
I interpreted the probabilities as being those of achieving the sequences given, and not being concerned about what happened on the next play.
But I augmented my program to include the probability of a loss on the next play of each run and I got 4 answers to the puzzle:
For example, with the first of these we have 27 sectors and 9 of them are winning, so:
The probability of a good spin is 9/27 = 1/3 (and the probability of a bad spin is 2/3).
So for B the probability of (S=win, S=win, S=win, S=lose) is:
For A the configuration could be (1, 2, 3, 3), giving the probability of (M=win, M=win, S=win, M=win, M=lose) as:
For C the configuration could be (1, 4, 4), giving the probability of (M=win, M=win, M=win, S=win, M=lose) as:
LikeLike
Frits 10:57 am on 10 August 2023 Permalink |
@Jim, you are right. Using rational numbers class Q in line 28/29 also yields 4 answers.
LikeLike