login
Table of maximal number of guesses required to solve a Mastermind variant, read by columns.
0

%I #48 Nov 23 2023 10:46:22

%S 0,1,1,2,1,2,3,2,2,3,4,2,5

%N Table of maximal number of guesses required to solve a Mastermind variant, read by columns.

%C The table is the maximum number of guesses required to absolutely identify a code from n colored pegs in k slots with no repetition, where marking is ordered and uses 3 types of peg - gray indicating the color isn't present, white indicating the color is present but in the wrong position and black indicating the color is present and in the right position.

%C Ordered marking means the codemaker marks from left to right and places a marking peg in the corresponding slot in the answer grid.

%C Note that the sequence only gives the number of guesses required, not the number of turns required. If for example we have 2 colors and 2 slots, and we guess RG and get marked ww, we now know the answer is GR, and this is not counted as necessary to guess.

%C T(3,2)=1 because with 3 colors, say c1, c2 and c3, then any answer to, say, the guess c1|c2 tells you the answer - if it's ww the answer is c2|c1, bb -> c1|c2, gw -> c2|c3, wg -> c3|c1, gb -> c3|c2 and bg -> c1|c3. The answers bw, wb and gg are all impossible.

%C T(4,3)=2 because the worst case scenario involves the 1st guess returning www or some form of wwg.

%H Mastermind Optimal Strategy, <a href="https://supermastermind.github.io/playonline/optimal_strategy.html">Reference for a(13)</a>

%H Web Games Online, <a href="http://www.web-games-online.com/mastermind/">Online MasterMind</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Mastermind.html">MasterMind</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Mastermind_(board_game)">MasterMind</a>.

%F T(n,1)=n-1.

%F T(n,2)=floor(n/2).

%F T(n,n)=n-1.

%e With 6 colors (RGYBOP) and 4 slots, say the code is YBRG. The guess BORP should be marked wgbg.

%e The table starts:

%e Colors

%e Slots | 1 2 3 4 5 6

%e -------------------------------

%e 1 | 0 1 2 3 4 5

%e 2 | x 1 1 2 2

%e 3 | x x 2 2 5

%e 4 | x x x 3

%e 5 | x x x x 4

%e 6 | x x x x x 5

%Y Cf. A004523.

%K nonn,tabl,more

%O 1,4

%A _Jon Perry_, Nov 05 2013

%E a(13) from _David Consiglio, Jr._, Oct 24 2023