# Optimal Strategies for Static Black-Peg AB Game With Two and Three Pegs
prelim

Gerold Jäger<EMAIL_ADDRESS>Department of Mathematics and
Mathematical Statistics, University of Umeå, SE-901-87 Umeå, Sweden  Frank
Drewes<EMAIL_ADDRESS>Department of Computer Science, University of
Umeå, SE-901-87 Umeå, Sweden

###### Abstract

The AB Game is a game similar to the popular game Mastermind. We study a
version of this game called Static Black-Peg AB Game. It is played by two
players, the codemaker and the codebreaker. The codemaker creates a so-called
secret by placing a color from a set of $c$ colors on each of $p\leq c$ pegs,
subject to the condition that every color is used at most once. The
codebreaker tries to determine the secret by asking questions, where all
questions are given at once and each question is a possible secret. As an
answer the codemaker reveals the number of correctly placed colors for each of
the questions. After that, the codebreaker only has one more try to determine
the secret and thus to win the game.

For given $p$ and $c$, our goal is to find the smallest number $k$ of
questions the codebreaker needs to win, regardless of the secret, and the
corresponding list of questions, called a $(k+1)$-strategy. We present a
$(\lceil 4c/3\rceil-1)$-strategy for $p=2$ for all $c\geq 2$, and a
$\lfloor(3c-1)/2\rfloor$-strategy for $p=3$ for all $c\geq 4$ and show the
optimality of both strategies, i.e., we prove that no $(k+1)$-strategy for a
smaller $k$ exists.

###### keywords:

game theory Mastermind AB Game optimal strategy

††journal: Theoretical Computer Science

proofProof

[prelm] A preliminary version of a part of this paper appeared in the
proceedings of the 11th International Conference on Combinatorial Optimization
and Applications, COCOA 2017, Ed.: Gao, X., Du, H. Han, M., LNCS 10628, pp.
409-424.

##  1 Introduction

The AB Game (also known as “bulls and cows game”) is a game similar to the
popular game Mastermind. Whereas the first one dates back more than a century,
the latter was invented by Meirowitz in 1970. Mastermind has since turned out
to have interesting applications in fields such as cryptography FL12 ,
bioinformatics GET11  and privacy protection AG13 . In both games a
_codemaker_ and a _codebreaker_ play against each other. The codemaker chooses
a secret code by placing colors from a set of $c$ available colors on $p$
pegs. In the original version of the AB Game and Mastermind, respectively,
$p=4$, $c=6$ and $p=4$, $c=10$, respectively, are fixed, but to make the
computational and mathematical properties of the game interesting, at least
one of these parameters must be made variable. The goal of the codebreaker is
to discover the secret code by making a sequence of guesses until the secret
has been found. Each guess is a possible secret. The corresponding answers of
the codemaker consist of black and white pegs, a black one for each peg of the
question which is correct in both position and color, and a white one for each
peg which is correct in color but not in position. The goal of the codebreaker
is to minimize the number of questions needed to find the secret, i.e., to
receive $p$ black pegs as the last answer. We call games of this kind
_codebreaking games_.

Mastermind can be turned into a decision problem, Mastermind Satisfiability,
as follows: given a list of questions and corresponding answers, are these
answers compatible with at least one possible secret? Interestingly, in SZ06
this problem was shown to be $\mathcal{NP}$-complete. For further results on
(non-static) Mastermind see for example DDST16 ; JP09 ; MS18 .

The difference between Mastermind and the AB Game is that a possible secret or
question of the latter may contain repeated colors whereas the AB Game
requires the secret as well as each question to consist of $p$ _distinct_
colors. Thus, the distinction between the two games mirrors the well-known
distinction made in combinatorics between an ordered choice of $p$ items from
a set of $c$ elements either with or without replacement.

Both Mastermind and the AB Game also have a black-peg variant, where the
answers of the codebreaker contain only black pegs (i.e., in addition to how
many pegs are correct in both position and color, no further information about
correct colors placed on the wrong pegs is provided).

While strategies for the Black-Peg AB Game were previously studied in EGSS18 ;
JP15a ; KT86 , we continue our study of optimal strategies for the _static_
black-peg variant of codebreaking games which was started in GJSS17 ; GJSS21 ;
Jag16 ; JD18 ; JD20 . The static black-peg variant differs from the standard
version described as follows. The codebreaker is required to present all
questions except the last one (which reveals the secret) right at the
beginning of the game. Thus, the game is _static_ , meaning that the
codebreaker cannot adapt later questions to previous answers.

In DDST16  it was shown that the original and the static version of Mastermind
need $\mathcal{O}(n\log\log n)$ questions for the most prominent case $n=c=p$.
For the Static Black-Peg AB Game, for this case $n=p=c$, a lower bound of
$\Omega(n\log n)$ and an upper bound of $\mathcal{O}(n^{1.525})$ were
presented in GJSS21 , and this upper bond has recently been improved to
$\mathcal{O}(n\log n)$ LMS22 .

A _$(k+1)$ -strategy_ is a sequence of $k$ questions such that the answers to
these questions uniquely determine the secret (i.e., the codebreaker can win
the game with the $(k+1)$-th question). We are interested in optimal
strategies – $(k+1)$-strategies where $k+1$ is as small as possible. Let us
denote this optimal $k+1$ (depending on $p$ and $c$) by $s(p,c)$. Erdös and
Rényi ER:63  and Söderberg and Shapiro SS63  showed independently that
$s(p,c)\in\mathcal{O}(p/{\log p})$ for $c=2$, a result that was later
generalized to $c\leq p^{1-\epsilon}$ for $\epsilon>0$ by Chvátal Chv83 .
Goddard God03  developed a $(\left\lceil 2c/3\right\rceil+1)$-strategy for two
pegs and $c$-strategies for three and four pegs. For sufficiently large $c$,
these strategies are optimal.

In Jag16 , we presented an optimal $\left\lceil(4c-1)/3\right\rceil$-strategy
for Static Black-Peg Mastermind in the case of $p=2$ pegs and an arbitrary
number $c\geq 1$ of colors, and in JD20  an optimal $(\left\lfloor
3c/2\right\rfloor+1)$-strategy for Static Black-Peg Mastermind in the case of
$p=3$ pegs and an arbitrary number $c\geq 2$ of colors. We now continue this
line of research by considering the corresponding cases of the Static Black-
Peg AB Game with $p=2$ and $p=3$, respectively. We start with an investigation
of the simpler $p=2$ case and an arbitrary number $c$ of colors (where by
definition of the AB Game, $c\geq 2$ must hold) resulting in an optimal
$(\lceil 4c/3\rceil-1)$-strategy. This strategy improves an earlier optimal
strategy that was presented in GJSS17  without explicit proof of feasibility
and optimality. While our new strategy obviously has the same number of
questions as the earlier one, the improvement lies in its structural
simplicity.

Our main result of this work is an optimal $\lfloor(3c-1)/2\rfloor$-strategy
for the Static Black-Peg AB Game with $p=3$ and an arbitrary number $c\geq 4$
of colors. The strategies for both cases for the Static Black-Peg AB Game with
$p=2$ and $p=3$ have a similar structure. This structure can also be applied
to and simplify our earlier strategies for Static Black-Peg Mastermind with
$p=2$ and $p=3$ Jag16 ; JD20 . Our expectation is that extending and comparing
the strategies for Static Black-Peg Mastermind of Jag16 ; JD20  and of the AB
Game in this work will eventually make it possible to develop generic optimal
strategies for arbitrary $p$ for both of these codebreaking games.

Interestingly, there is also a graph-theoretic interpretation of strategies
for Static Black-Peg Mastermind to the so-called metric dimension. For an
undirected graph $G$, the metric dimension of $G$ is defined as the minimum
number of vertices in a subset $S$ of $G$ such that all other vertices are
uniquely determined by their distances to the vertices in $S$, see for example
FHHMS15 ; RKYS15 ; YKR11  for results on special graph classes. Furthermore,
the decision variant of this problem is $\mathcal{NP}$-complete GJ79

Concretely, Static Black-Peg Mastermind with $p$ pegs and $c$ colors needing
exactly $k$ questions is equivalent to the metric dimension of the graph
$\mathbb{Z}_{c}^{p}$ being $k$ (see JD20  for more details). Thus, the results
of Jag16 ; JD20  show that the metric dimension of
$\mathbb{Z}_{n}\times\mathbb{Z}_{n}$ is $\left\lceil(4c-1)/3\right\rceil-1$
and that of $\mathbb{Z}_{n}\times\mathbb{Z}_{n}\times\mathbb{Z}_{n}$ is
$\left\lfloor 3c/2\right\rfloor$. An open question is whether the results of
the present paper can also be connected to the metric dimension of other types
of graphs. In any case, our new way to assemble optimal strategies by
iterating color-shifted copies of a fixed block can similarly be used to
compose simpler optimal strategies for Static Black-Peg Mastermind than those
in Jag16 ; JD20 . In turn, this results in simplified proofs of the fact that
the metric dimensions of $\mathbb{Z}_{n}\times\mathbb{Z}_{n}$ and
$\mathbb{Z}_{n}\times\mathbb{Z}_{n}\times\mathbb{Z}_{n}$ are
$\left\lceil(4c-1)/3\right\rceil-1$ and $\left\lfloor 3c/2\right\rfloor$,
respectively.

This work is set up as follows. After giving some preliminaries in Section 2,
we present an optimal $(\lceil 4c/3\rceil-1)$-strategy for $p=2$ in Section 3
and an optimal $\lfloor(3c-1)/2\rfloor$-strategy for $p=3$ in Section 4.
Finally, we conclude and suggest possible future work in Section 5.

##  2 Preliminaries

Let $p\geq 1$ denote the number of pegs and $c\geq p$ the number of colors.
W.l.o.g., throughout the remainder of this paper, let the pegs be numbered by
$1,2\dots,p$, and the colors by $1,2,\dots,c$. We write the questions and
secrets in the form $Q=(q_{1}\,|\,q_{2}\,|\,\dots\,|\,q_{p})$. The possible
answers are written as $0$B, $1$B, $2$B, $\dots$, $p$B.

For $k\in\mathbb{N}$, a $(k+1)$-_strategy_ for Static Black-Peg AB Game
consists of $k$ questions which the codebreaker has to ask altogether at the
beginning of the game. These are the so-called _main questions._ Such a
strategy is _feasible_ if every secret $S$ is uniquely determined by the $k$
answers. Having received these answers, the codebreaker can ask the _final
question_ $S$ to win the game.

We use the letter $k$ to denote the number of main questions, excluding the
final question. Since we will only be concerned with the main questions, in
the following we will generally omit the term “main”, referring to the main
questions simply as questions. A $(k+1)$-strategy is called _optimal_ if there
is no feasible $k$-strategy. Clearly, all questions of an optimal strategy
must be distinct. Therefore, we shall in the following only consider
strategies in which all questions are distinct, without explicitly mentioning
this fact.

###### Remark 1

Determining an optimal strategy for the Static Black-Peg AB Game is trivial in
the case $p=1$ because the questions $(1),(2),\dots,(c-1)$ reveal the secret
and, obviously, no set consisting of fewer than $c-1$ questions does. Thus, in
the case $p=1$ this strategy is an optimal strategy for all $c$ (and so is any
other strategy consisting of $c-1$ questions). In other words, there is an
optimal $c$-strategy for $p=1$ and every $c\geq 1$.

We need the following definition.

###### Definition 1

Let $Q=(q_{1}\,|\,q_{2}\,|\,\dots\,|\,q_{p})$ and
$Q^{\prime}=(q_{1}^{\prime}\,|\,q_{2}^{\prime}\,|\,\dots\,|\,q_{p}^{\prime})$
be questions.

  1. (a)

$Q$ and $Q^{\prime}$ are called _neighboring_ , if $q_{i}=q_{i}^{\prime}$ for
some $i\in\\{1,2,\dots,p\\}$. We say that they _overlap_ in peg $i$ and call
peg $i$ an _overlapping peg_ (of $Q$ and $Q^{\prime}$).

  2. (b)

$Q$ and $Q^{\prime}$ are are _double neighboring_ if they overlap in at least
two distinct pegs.

  3. (c)

$Q$ and $Q^{\prime}$ are _disjoint_ , if $q_{i}\neq q_{j}^{\prime}$ for all
$i,j\in\\{1,2,\dots,p\\}$. More generally, we say that $Q$ and $Q^{\prime}$
are disjoint in pegs $i_{1},i_{2},\dots,i_{k}$ if
$\\{q_{i_{1}},q_{i_{2}},\dots,q_{i_{k}}\\}\cap\\{q_{i_{1}}^{\prime},q_{i_{2}}^{\prime}\dots,q_{i_{k}}^{\prime}\\}=\emptyset$.

  4. (d)

For $a_{1},a_{2},\dots,a_{p}\in\mathbb{N}$, $Q$ is a
_$(a_{1},a_{2},\dots,a_{p})$ -question_111Note the different notation in
comparison to the question itself, where we separate the numbers by the symbol
“$\,|\,$”. of a given strategy if the $i$-th color of $Q$ occurs exactly
$a_{i}$ times on the $i$-th peg of the questions of the strategy, for
$i=1,2,\dots,p$. Sometimes, for one or more $i\in\\{1,2,\dots,p\\}$, we do not
want to specify $a_{i}$, i.e., it is not relevant how often the $i$-th color
occurs on the $i$-th peg. Then “$a_{i}$” is replaced by the symbol “$\star$”.
Finally, “$a_{i}$” can be replaced by “$\geq a_{i}$” to express that $q_{i}$
occurs _at least_ $a_{i}$ times on the $i$-th peg.

In the remainder of the paper, we investigate the cases $p=2,3$. For both
cases, the feasible strategy starts with so-called base questions for a small
number of colors and then repeats a copy of a fixed block of questions,
shifting the colors in each copy appropriately. This structure makes the proof
of feasibility relatively easy. However, for the proof of optimality all
possible feasible strategies have to be considered, without making specific
assumptions regarding their structure, and it has to be excluded that they may
require fewer questions.

##  3 Two Pegs

In this section let $p=2$.

###  3.1 A $(\lceil 4c/3\rceil-1)$-Strategy

We introduce a $(\lceil 4c/3\rceil-1)$-strategy for each $c\geq 2$ which we
will later show to be feasible and optimal. We start with presenting such a
strategy explicitly for $c=2,3,4$ in Table 1. These three strategies have been
found by brute-force computer search.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $2$
(a) $c=2$, $k=1$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $2$
$Q_{2}$ | $3$ | $1$
(b) $c=3$, $k=2$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $3$
$Q_{2}$ | $3$ | $1$
$Q_{3}$ | $2$ | $3$
$Q_{4}$ | $3$ | $2$
(c) $c=4$, $k=4$.

Table 1: Feasible and optimal $(\lceil 4c/3\rceil-1)$-strategies for $p=2$ and
$2\leq c\leq 4$.

As mentioned, we create $(\lceil 4c/3\rceil-1)$-strategies for all $c\geq 2$
by starting with a block of so-called base questions and then repeatedly
adding copies of a fixed block of questions, shifting the colors in each copy
appropriately. As for the base questions, we start with one of the three
strategies of Table 1. The iterative step is based on the strategy of Table
1(c), which we repeat a suitable number of times (with shifted colors).

Concretely, let $c\geq p=2$ and $c=3s+t$, where $s\in\mathbb{N}_{0}$,
$t\in\\{2,3,4\\}$ are uniquely determined. For $t=2$ we start with the $k=1$
question of the strategy of Table 1(a), for $t=3$ with the $k=2$ questions of
the strategy of Table 1(b) and for $t=4$ with the $k=4$ questions of the
strategy of Table 1(c). As mentioned, we call this first group of questions
the _base questions_.

In all three cases the base questions are followed $s$ times by the $4$
questions of Table 1(c). For $l=1,2,\dots,s$, the number $t+3\left(l-1\right)$
is added to the colors of the questions of Table 1(c). We call this second
group of questions the _iterated questions_.

As examples, we present the corresponding $(\lceil 4c/3\rceil-1)$-strategies
for $5\leq c\leq 10$ explicitly in Table 2.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $2$
$Q_{2}$ | $3$ | $5$
$Q_{3}$ | $5$ | $3$
$Q_{4}$ | $4$ | $5$
$Q_{5}$ | $5$ | $4$
(a) $c=5$, $k=5$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $2$
$Q_{2}$ | $3$ | $1$
$Q_{3}$ | $4$ | $6$
$Q_{4}$ | $6$ | $4$
$Q_{5}$ | $5$ | $6$
$Q_{6}$ | $6$ | $5$
(b) $c=6$, $k=6$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $3$
$Q_{2}$ | $3$ | $1$
$Q_{3}$ | $2$ | $3$
$Q_{4}$ | $3$ | $2$
$Q_{5}$ | $5$ | $7$
$Q_{6}$ | $7$ | $5$
$Q_{7}$ | $6$ | $7$
$Q_{8}$ | $7$ | $6$
(c) $c=7$, $k=8$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $2$
$Q_{2}$ | $3$ | $5$
$Q_{3}$ | $5$ | $3$
$Q_{4}$ | $4$ | $5$
$Q_{5}$ | $5$ | $4$
$Q_{6}$ | $6$ | $8$
$Q_{7}$ | $8$ | $6$
$Q_{8}$ | $7$ | $8$
$Q_{9}$ | $8$ | $7$
(d) $c=8$, $k=9$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $2$
$Q_{2}$ | $3$ | $1$
$Q_{3}$ | $4$ | $6$
$Q_{4}$ | $6$ | $4$
$Q_{5}$ | $5$ | $6$
$Q_{6}$ | $6$ | $5$
$Q_{7}$ | $7$ | $9$
$Q_{8}$ | $9$ | $7$
$Q_{9}$ | $8$ | $9$
$Q_{10}$ | $9$ | $8$
(e) $c=9$, $k=10$.

Peg | $1$ | $2$
---|---|---
$Q_{1}$ | $1$ | $3$
$Q_{2}$ | $3$ | $1$
$Q_{3}$ | $2$ | $3$
$Q_{4}$ | $3$ | $2$
$Q_{5}$ | $5$ | $7$
$Q_{6}$ | $7$ | $5$
$Q_{7}$ | $6$ | $7$
$Q_{8}$ | $7$ | $6$
$Q_{9}$ | $8$ | $10$
$Q_{10}$ | $10$ | $8$
$Q_{11}$ | $9$ | $10$
$Q_{12}$ | $10$ | $9$
(f) $c=10$, $k=12$.

Table 2: Feasible and optimal $(\lceil 4c/3\rceil-1)$-strategies for $p=2$ and
$5\leq c\leq 10$.

In Subsections 3.2 and 3.3 we prove the following theorem.

###### Theorem 1

The presented strategy is a _feasible_ and _optimal_ $(\lceil
4c/3\rceil-1)$-strategy for $p=2$ and for the corresponding $c\geq 2$.

In the following let $h\equiv c\ \\!\;\textrm{mod}\;3$.

###### Remark 2

  1. (a)

For $h\in\\{0,2\\}$, our presented strategy for the Static Black-Peg AB Game
needs _one question less_ than the strategy of Jag16  for Static Black-Peg
Mastermind (see Strategies 1 and 3, respectively, in Jag16 ).

  2. (b)

For $h=1$, our presented strategy for the Static Black-Peg AB Game needs _the
same number of questions_ as the strategy of Jag16  for Static Black-Peg
Mastermind (see Strategy 2 in Jag16 ).

###  3.2 Feasibility of the $(\lceil 4c/3\rceil-1)$-Strategy

Analyzing the $(\lceil 4c/3\rceil-1)$-strategy, we observe the following:

###### Observation 1

  1. (a)

For $h=0$, the following holds:

The $(\lceil 4c/3\rceil-1)$-strategy contains only $(1,2)$-questions and
$(2,1)$-questions, except the first two questions $Q_{1}=(1\,|\,2)$ and
$Q_{2}=(3\,|\,1)$ which are both $(1,1)$-questions.

On the first peg only the color $2$ is missing (throughout the entire
strategy), and on the second peg only the color $3$ is missing.

  2. (b)

For $h=1$, the following holds:

The $(\lceil 4c/3\rceil-1)$-strategy contains only $(1,2)$-questions and
$(2,1)$-questions.

Both on the first and the second peg only the color $4$ is missing.

  3. (c)

For $h=2$, the following holds:

The $(\lceil 4c/3\rceil-1)$-strategy contains only $(1,2)$-questions and
$(2,1)$-questions, except the first question $Q_{1}=(1\,|\,2)$ which is a
$(1,1)$-question.

On the first peg only the color $2$ is missing, and on the second peg only the
color $1$ is missing.

Consider one fixed $(1,2)$-question or $(2,1)$-question, and assume that it
receives a non-empty answer $2$B or $1$B, respectively. Then the following
conclusions can be drawn.

  1. (I)

The answer is $1$B.

Here we have to find out which one of the two pegs is correct. This is
determined by the answer to the neighboring question: if that answer is also
non-empty, then the color of the overlapping peg is correct, otherwise the
color of the other peg is correct.

As an example, consider the strategy for $c=9$ in Table 2(e).

For the secret $(4\,|\,9)$, the answer to the question $Q_{3}=(4\,|\,6)$ is
$1$B. The neighboring question to $Q_{3}$ is $Q_{5}=(5\,|\,6)$. As $Q_{5}$
gives the answer $0$B, we know that color $4$ is correct on the first peg, but
we do not know yet the color of the second peg.

On the other hand, for the secret $(3,6)$, the answer to the question $Q_{3}$
is $1$B and to $Q_{5}$ also $1$B. Then we know that color $6$ is correct on
the second peg.

  2. (II)

The answer is $2$B.

The secret is found.

So as soon we have a non-empty answer to a $(1,2)$-question or to a
$(2,1)$-question, we know the color of one peg. However, having this
information about one peg, also the other peg can be determined from the
answers to all questions of the strategy, as by Observation 1) on each peg
only one color is missing.

So we have shown the feasibility for the case that at least one
$(1,2)$-question or at least one $(2,1)$-question receives a non-empty answer.
To show the feasibility also for the remaining case that all $(1,2)$-questions
and all $(2,1)$-questions receive an empty answer, we distinguish between
$h=0,1,2$.

  1. (I)

$h=0$:

Six possible secrets are consistent with answers $0$B to all $(1,2)$-questions
and $(2,1)$-questions. We list them and the combination of answers to the
$(1,1)$-questions $Q_{1}=(1\,|\,2)$ and $Q_{2}=(3\,|\,1)$:

    1. (i)

Secret $(1\,|\,2)$: Combination of answers $(2\mbox{B},0\mbox{B})$.

    2. (ii)

Secret $(1\,|\,3)$: Combination of answers $(1\mbox{B},0\mbox{B})$.

    3. (iii)

Secret $(2\,|\,1)$: Combination of answers $(0\mbox{B},1\mbox{B})$.

    4. (iv)

Secret $(2\,|\,3)$: Combination of answers $(0\mbox{B},0\mbox{B})$.

    5. (v)

Secret $(3\,|\,1)$: Combination of answers $(0\mbox{B},2\mbox{B})$.

    6. (vi)

Secret $(3\,|\,2)$: Combination of answers $(1B,1B)$.

  2. (II)

$h=1$:

Only one possible secret is consistent with the answer $0$B to all $(1,2)$\-
questions and $(2,1)$-questions, namely $(4\,|\,4)$.

  3. (III)

$h=2$:

Two possible secrets are consistent with the answer $0$B to all $(1,2)$\- and
$(2,1)$-questions, namely $(1\,|\,2)$ and $(2\,|\,1)$. However, these are
distinguished by the only $(1,1)$-question $Q_{1}=(1\,|\,2)$.

Thus, each possible secret is uniquely determined in all three cases, which
finishes the proof of feasibility.

###  3.3 Optimality of the $(\lceil 4c/3\rceil-1)$-Strategy

We need the following lemma.

###### Lemma 1

For the Static Black-Peg AB Game with $p=2$ the following statements hold:

  1. (a)

For each feasible strategy and for each peg there exists at most one color
which does not occur on this peg.

  2. (b)

A feasible strategy cannot contain two disjoint $(1,1)$-questions.

  3. (c)

If a feasible strategy contains three $(1,1)$-questions, by possibly permuting
the colors, these questions can be written in the form $(1\,|\,2)$,
$(2\,|\,3)$, $(3\,|\,1)$.

  4. (d)

If a feasible strategy contains three $(1,1)$-questions, then on at least one
of the two pegs of the questions, all $c$ colors must occur.

  5. (e)

A feasible strategy cannot contain four $(1,1)$-questions.

######  Proof 3.2.

  1. 1.

The assertion is clear for $c=2$. Thus, let $c\geq 3$. Assume without loss of
generality that there are two colors $a$ and $b$ which do not occur on the
first peg. Choose an arbitrary color $x$ which is neither $a$ nor $b$ ($x$
exists because $c\geq 3$). Then the possible secrets $(a\,|\,x)$ and
$(b\,|\,x)$ receive the same combination of answers. Thus, the two possible
secrets are indistinguishable, contradicting the feasibility of the strategy.

By symmetry, this also proves the corresponding statement for the second peg.

  2. (b)

Suppose that the strategy contains two disjoint $(1,1)$-questions. So their
four colors are distinct, say $(1\,|\,2)$ and $(3\,|\,4)$, and thus $c\geq 4$.
Then the possible secrets $(1\,|\,4)$ and $(3\,|\,2)$ receive the same answer
($1$B) for both questions $(1\,|\,2)$ and $(3\,|\,4)$, and also the same
answer ($0$B) for all other questions. Thus, the two possible secrets are
indistinguishable, leading to a contradiction.

  3. (c)

Let a feasible strategy contain three $(1,1)$-questions, say
$(q_{1}\,|\,q_{1}^{\prime})$, $(q_{2}\,|\,q_{2}^{\prime})$ and
$(q_{3}\,|\,q_{3}^{\prime})$. Without loss of generality, we may permute
colors so that $q_{1}=1$, $q_{2}=2$, $q_{3}=3$. (Note that $q_{1},q_{2},q_{3}$
are distinct by the definition of $(1,1)$-questions, and so are
$q_{1}^{\prime},q_{2}^{\prime},q_{3}^{\prime}$.)

If some $q_{i}^{\prime}$, say $q_{1}^{\prime}$, differs from $1,2$ and $3$,
then not both $q_{2}^{\prime}$ and $q_{3}^{\prime}$ can be equal to $1$. Thus,
in this case $(1\,|\,q_{1}^{\prime})$ and $(2\,|\,q_{2}^{\prime})$, or
$(1\,|\,q_{1}^{\prime})$ and $(3\,|\,q_{3}^{\prime})$ would be disjoint. By
(b), this contradicts the feasibility of the strategy, thus showing that
$\\{q_{1}^{\prime},q_{2}^{\prime},q_{3}^{\prime}\\}=\\{1,2,3\\}$.

As $q_{i}=i$, the definition of the AB Game yields $q_{i}^{\prime}\neq i$,
which means that

$q_{1}^{\prime}\in\\{2,3\\},\ q_{2}^{\prime}\in\\{1,3\\},\
q_{3}^{\prime}\in\\{1,2\\},$

which leaves only two possibilities, namely the claimed

$(q_{1}\,|\,q_{1}^{\prime})=(1\,|\,2),\ (q_{2}\,|\,q_{2}^{\prime})=(2\,|\,3),\
(q_{3}\,|\,q_{3}^{\prime})=(3\,|\,1)$

or

$(q_{1}\,|\,q_{1}^{\prime})=(1\,|\,3),\ (q_{2}\,|\,q_{2}^{\prime})=(2\,|\,1),\
(q_{3}\,|\,q_{3}^{\prime})=(3\,|\,2).$

In the second case, the claimed situation is obtained by switching colors $2$
and $3$ and switching the second and the third question.

  4. (d)

By (c), a feasible strategy may be assumed to contain three $(1,1)$-questions
$(1\,|\,2)$, $(2\,|\,3)$, and $(3\,|\,1)$. Suppose that there is a color $a$
which does not occur on the first peg of the questions and a color $b$ which
does not occur on the second peg of the questions. Then the possible secrets
$(1\,|\,b)$ and $(a\,|\,2)$ receive the answer $1$B for the question
$(1\,|\,2)$, and $0$B for all other questions, i.e., the same combination of
answers. Thus, these possible secrets $(1\,|\,b)$ and $(a\,|\,2)$ are
indistinguishable – a contradiction.

  5. (e)

If a feasible strategy contains four $(1,1)$-questions, by (c) the first three
of them can be written in the form $(1\,|\,2)$, $(2\,|\,3)$, and $(3\,|\,1)$.
Adding a fourth $(1,1)$-question would automatically lead to two disjoint
$(1,1)$-questions. This contradicts (b). $\square$

Now we come to the final part of the optimality proof. Note that the presented
strategy uses $k=\lceil 4c/3\rceil-2$ questions.222Recall that $k$ does not
include the final question. In the following we prove that every feasible
strategy consists of at least $k$ questions. Thus, consider any feasible
strategy. Let $l_{i}$ be the number of colors which occur exactly once on the
$i$-th peg of this strategy for $i=1,2$. Furthermore, let $m$ be the number of
$(1,1)$-questions of the strategy. Observe that the total number of questions
is at least $l_{1}+l_{2}-m$. Again we distinguish between $h=0,1,2$.

  1. (I)

$h=0$.

We have

$\displaystyle k$ $\displaystyle=$ $\displaystyle\frac{4c}{3}-2.$

On the one hand, if $l_{i}\leq 2c/3$ for some $i\in\\{1,2\\}$, since at least
$c-1$ colors occur on peg $i$ (see Lemma 1(a)), we have at least

$\displaystyle\frac{2c}{3}+2\cdot\left(\frac{c}{3}-1\right)\;\geq\;\frac{4c}{3}-2\;=\;k$

questions.

If, on the other hand, $l_{i}\geq\frac{2c}{3}+1$ for $i=1,2$ it follows that
there are at least

$\displaystyle
l_{1}+l_{2}-m\;\geq\;2\cdot\left(\frac{2c}{3}+1\right)-3\;\geq\;\frac{4c}{3}-1\;=\;k+1$

questions, because we know from Lemma 1(e) that $m\leq 3$.

  2. (II)

$h=1$.

We have

$\displaystyle k$ $\displaystyle=$ $\displaystyle\frac{4c-1}{3}-1.$

We distinguish between two sub-cases.

    1. (i)

On both pegs only $c-1$ colors occur.

On the one hand, analogously to the case $h=0$, if $l_{i}\leq\frac{2c-2}{3}$
for some $i\in\\{1,2\\}$, we have at least

$\displaystyle\frac{2c-2}{3}+2\cdot\left(\frac{c-1}{3}\right)\;\geq\;\frac{4c-1}{3}-1\;=\;k$
(1)

questions.

If instead $l_{i}\geq\frac{2c+1}{3}$ for $i=1,2$, we have

$\displaystyle
l_{1}+l_{2}-m\;\geq\;2\cdot\left(\frac{2c+1}{3}\right)-2\;\geq\;\frac{4c}{3}+\frac{2}{3}-\frac{6}{3}\;=\;k,$

because we know from Lemma 1(d) that $m\leq 2$.

    2. (ii)

On at least one peg, say peg $1$, all $c$ colors occur.

If $l_{1}\leq\frac{2c+1}{3}$, then there are at least

$\displaystyle\frac{2c+1}{3}+2\cdot\left(\frac{c-1}{3}\right)\;\geq\;\frac{4c-1}{3}\;=\;k+1$

questions.

Recall also from Eq. (1) that we have at least $k$ questions if
$l_{2}\leq\frac{2c-2}{3}$, and assume thus that $l_{1}\geq\frac{2c+4}{3}$ and
$l_{2}\geq\frac{2c+1}{3}$. Since $m\leq 3$ by Lemma 1(e), it follows that

$\displaystyle
l_{1}+l_{2}-m\;\geq\;\frac{2c+4}{3}+\frac{2c+1}{3}-3\;=\;\frac{4c-1}{3}-1\;=\;k.$

  3. (III)

$h=2$.

We have

$\displaystyle k$ $\displaystyle=$ $\displaystyle\frac{4c-2}{3}-1.$

Analogously to the previous cases, if $l_{i}\leq\frac{2c-1}{3}$ for some
$i\in\\{1,2\\}$, then we have at least

$\displaystyle\frac{2c-1}{3}+2\cdot\left(\frac{c-2}{3}\right)\;\geq\;\frac{4c-2}{3}-1\;=\;k$

questions.

It remains to consider the case where $l_{i}\geq\frac{2c+2}{3}$ for $i=1,2$.
Again using the fact that $m\leq 3$ by Lemma 1(e), it follows that

$\displaystyle
l_{1}+l_{2}-m\;\geq\;2\cdot\left(\frac{2c+2}{3}\right)-3\;=\;\frac{4c+4}{3}-3\;=\;\frac{4c-2}{3}-1\;=\;k,$

which completes the last case and thus the proof. $\square$

##  4 Three Pegs

In this section let $p=3$.

###  4.1 A $\lfloor(3c-1)/2\rfloor$-Strategy

We introduce a $\lfloor(3c-1)/2\rfloor$-strategy for each $c\geq 4$ which we
will later show to be feasible and optimal. Interestingly, such a feasible
strategy does not exist for $c=3$, i.e., no feasible $4$-strategy exists
333Observe that $(\lfloor(3\cdot 3-1)/2\rfloor)=4$, but this includes the
final question. although there are only $3!=6$ possible secrets. One feasible
and optimal $5$-strategy for $c=3$ is shown in Table 3.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $3$
$Q_{2}$ | $1$ | $3$ | $2$
$Q_{3}$ | $2$ | $1$ | $3$
$Q_{4}$ | $2$ | $3$ | $1$
Table 3: Feasible and optimal strategy for $p=3$, $c=3$, $k=4$.

We start by explicitly presenting $\lfloor(3c-1)/2\rfloor$-strategies for
$c=4,5,6,7,8,9$ in Table 4. These six strategies have been found by brute-
force computer search.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $3$
$Q_{2}$ | $1$ | $3$ | $4$
$Q_{3}$ | $3$ | $2$ | $4$
$Q_{4}$ | $2$ | $4$ | $1$
(a) $c=4$, $k=4$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $3$ | $4$
$Q_{2}$ | $2$ | $3$ | $4$
$Q_{3}$ | $3$ | $1$ | $5$
$Q_{4}$ | $4$ | $2$ | $5$
$Q_{5}$ | $3$ | $5$ | $1$
$Q_{6}$ | $4$ | $5$ | $3$
(b) $c=5$, $k=6$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $3$
$Q_{2}$ | $1$ | $3$ | $2$
$Q_{3}$ | $2$ | $1$ | $3$
$Q_{4}$ | $2$ | $4$ | $1$
$Q_{5}$ | $3$ | $5$ | $2$
$Q_{6}$ | $5$ | $4$ | $6$
$Q_{7}$ | $6$ | $5$ | $4$
(c) $c=6$, $k=7$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $7$
$Q_{2}$ | $4$ | $1$ | $7$
$Q_{3}$ | $2$ | $7$ | $5$
$Q_{4}$ | $5$ | $7$ | $4$
$Q_{5}$ | $7$ | $3$ | $2$
$Q_{6}$ | $7$ | $4$ | $3$
$Q_{7}$ | $6$ | $5$ | $1$
$Q_{8}$ | $3$ | $6$ | $1$
$Q_{9}$ | $3$ | $5$ | $6$
(d) $c=7$, $k=9$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $6$ | $5$ | $4$
$Q_{2}$ | $3$ | $1$ | $5$
$Q_{3}$ | $7$ | $6$ | $4$
$Q_{4}$ | $8$ | $2$ | $6$
$Q_{5}$ | $2$ | $4$ | $6$
$Q_{6}$ | $2$ | $7$ | $5$
$Q_{7}$ | $4$ | $1$ | $3$
$Q_{8}$ | $8$ | $5$ | $2$
$Q_{9}$ | $1$ | $6$ | $7$
$Q_{10}$ | $4$ | $3$ | $8$
(e) $c=8$, $k=10$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $3$ | $1$ | $4$
$Q_{2}$ | $2$ | $1$ | $3$
$Q_{3}$ | $4$ | $2$ | $3$
$Q_{4}$ | $1$ | $2$ | $4$
$Q_{5}$ | $5$ | $7$ | $8$
$Q_{6}$ | $5$ | $6$ | $7$
$Q_{7}$ | $6$ | $8$ | $7$
$Q_{8}$ | $7$ | $5$ | $8$
$Q_{9}$ | $7$ | $3$ | $1$
$Q_{10}$ | $7$ | $3$ | $5$
$Q_{11}$ | $8$ | $9$ | $2$
$Q_{12}$ | $8$ | $4$ | $9$
(f) $c=9$, $k=12$.

Table 4: Feasible and optimal $(\lfloor(3c-1)/2\rfloor)$-strategies for $p=3$
and $4\leq c\leq 9$.

Then we create $\lfloor(3c-1)/2\rfloor$-strategies for all $c\geq 4$ in a way
similar to the case $p=2$. We start with one of the six strategies of Table 4
and append the strategy of Table 5 a suitable number of times, shifting the
colors of each such block of questions appropriately.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $5$ | $6$
$Q_{2}$ | $4$ | $1$ | $6$
$Q_{3}$ | $4$ | $5$ | $1$
$Q_{4}$ | $2$ | $6$ | $4$
$Q_{5}$ | $5$ | $2$ | $4$
$Q_{6}$ | $5$ | $6$ | $2$
$Q_{7}$ | $3$ | $4$ | $5$
$Q_{8}$ | $6$ | $3$ | $5$
$Q_{9}$ | $6$ | $4$ | $3$
Table 5: Feasible (but not optimal) strategy for $p=3$, $c=6$, $k=9$.

Concretely, let $c=6s+t$, where $s\in\mathbb{N}_{0}$, $t\in\\{4,5,6,7,8,9\\}$
are uniquely determined. For $t=4,5,\dots,9$ we start with the questions of
the strategies in Tables 4(a)–4(f), respectively. Again we call this first
group of questions the _base questions_.

In all six cases the base questions are followed $s$ times by the $9$
questions of Table 5. For $l=1,2,\dots,s$, the $l$-th of these $s$ blocks is
obtained by adding the number $t+6(l-1)$ to the colors in Table 5. Again we
call this second group of questions the _iterated questions_.

As examples, we present the corresponding
$(\lfloor(3c-1)/2\rfloor)$-strategies for $10\leq c\leq 15$ explicitly in
Table 6.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $3$
$Q_{2}$ | $1$ | $3$ | $4$
$Q_{3}$ | $3$ | $2$ | $4$
$Q_{4}$ | $2$ | $4$ | $1$
$Q_{5}$ | $5$ | $9$ | $10$
$Q_{6}$ | $8$ | $5$ | $10$
$Q_{7}$ | $8$ | $9$ | $5$
$Q_{8}$ | $6$ | $10$ | $8$
$Q_{9}$ | $9$ | $6$ | $8$
$Q_{10}$ | $9$ | $10$ | $6$
$Q_{11}$ | $7$ | $8$ | $9$
$Q_{12}$ | $10$ | $7$ | $9$
$Q_{13}$ | $10$ | $8$ | $7$
(a) $c=10$, $k=13$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $3$ | $4$
$Q_{2}$ | $2$ | $3$ | $4$
$Q_{3}$ | $3$ | $1$ | $5$
$Q_{4}$ | $4$ | $2$ | $5$
$Q_{5}$ | $3$ | $5$ | $1$
$Q_{6}$ | $4$ | $5$ | $3$
$Q_{7}$ | $6$ | $10$ | $11$
$Q_{8}$ | $9$ | $6$ | $11$
$Q_{9}$ | $9$ | $10$ | $6$
$Q_{10}$ | $7$ | $11$ | $9$
$Q_{11}$ | $10$ | $7$ | $9$
$Q_{12}$ | $10$ | $11$ | $7$
$Q_{13}$ | $8$ | $9$ | $10$
$Q_{14}$ | $11$ | $8$ | $10$
$Q_{15}$ | $11$ | $9$ | $8$
(b) $c=11$, $k=15$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $3$
$Q_{2}$ | $1$ | $3$ | $2$
$Q_{3}$ | $2$ | $1$ | $3$
$Q_{4}$ | $2$ | $4$ | $1$
$Q_{5}$ | $3$ | $5$ | $2$
$Q_{6}$ | $5$ | $4$ | $6$
$Q_{7}$ | $6$ | $5$ | $4$
$Q_{8}$ | $7$ | $11$ | $12$
$Q_{9}$ | $10$ | $7$ | $12$
$Q_{10}$ | $10$ | $11$ | $7$
$Q_{11}$ | $8$ | $12$ | $10$
$Q_{12}$ | $11$ | $8$ | $10$
$Q_{13}$ | $11$ | $12$ | $8$
$Q_{14}$ | $9$ | $10$ | $11$
$Q_{15}$ | $12$ | $9$ | $11$
$Q_{16}$ | $12$ | $10$ | $9$
(c) $c=12$, $k=16$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $2$ | $7$
$Q_{2}$ | $4$ | $1$ | $7$
$Q_{3}$ | $2$ | $7$ | $5$
$Q_{4}$ | $5$ | $7$ | $4$
$Q_{5}$ | $7$ | $3$ | $2$
$Q_{6}$ | $7$ | $4$ | $3$
$Q_{7}$ | $6$ | $5$ | $1$
$Q_{8}$ | $3$ | $6$ | $1$
$Q_{9}$ | $3$ | $5$ | $6$
$Q_{10}$ | $8$ | $12$ | $13$
$Q_{11}$ | $11$ | $8$ | $13$
$Q_{12}$ | $11$ | $12$ | $8$
$Q_{13}$ | $9$ | $13$ | $11$
$Q_{14}$ | $12$ | $9$ | $11$
$Q_{15}$ | $12$ | $13$ | $9$
$Q_{16}$ | $10$ | $11$ | $12$
$Q_{17}$ | $13$ | $10$ | $12$
$Q_{18}$ | $13$ | $11$ | $10$
(d) $c=13$, $k=18$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $6$ | $5$ | $4$
$Q_{2}$ | $3$ | $1$ | $5$
$Q_{3}$ | $7$ | $6$ | $4$
$Q_{4}$ | $8$ | $2$ | $6$
$Q_{5}$ | $2$ | $4$ | $6$
$Q_{6}$ | $2$ | $7$ | $5$
$Q_{7}$ | $4$ | $1$ | $3$
$Q_{8}$ | $8$ | $5$ | $2$
$Q_{9}$ | $1$ | $6$ | $7$
$Q_{10}$ | $4$ | $3$ | $8$
$Q_{11}$ | $9$ | $13$ | $14$
$Q_{12}$ | $12$ | $9$ | $14$
$Q_{13}$ | $12$ | $13$ | $9$
$Q_{14}$ | $10$ | $14$ | $12$
$Q_{15}$ | $13$ | $10$ | $12$
$Q_{16}$ | $13$ | $14$ | $10$
$Q_{17}$ | $11$ | $12$ | $13$
$Q_{18}$ | $14$ | $11$ | $13$
$Q_{19}$ | $14$ | $12$ | $11$
(e) $c=14$, $k=19$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $3$ | $1$ | $4$
$Q_{2}$ | $2$ | $1$ | $3$
$Q_{3}$ | $4$ | $2$ | $3$
$Q_{4}$ | $1$ | $2$ | $4$
$Q_{5}$ | $5$ | $7$ | $8$
$Q_{6}$ | $5$ | $6$ | $7$
$Q_{7}$ | $6$ | $8$ | $7$
$Q_{8}$ | $7$ | $5$ | $8$
$Q_{9}$ | $7$ | $3$ | $1$
$Q_{10}$ | $7$ | $3$ | $5$
$Q_{11}$ | $8$ | $9$ | $2$
$Q_{12}$ | $8$ | $4$ | $9$
$Q_{13}$ | $10$ | $14$ | $15$
$Q_{14}$ | $13$ | $10$ | $15$
$Q_{15}$ | $13$ | $14$ | $10$
$Q_{16}$ | $11$ | $15$ | $13$
$Q_{17}$ | $14$ | $11$ | $13$
$Q_{18}$ | $14$ | $15$ | $11$
$Q_{19}$ | $12$ | $13$ | $14$
$Q_{20}$ | $15$ | $12$ | $14$
$Q_{21}$ | $15$ | $13$ | $12$
(f) $c=15$, $k=21$.

Table 6: Feasible and optimal $(\lfloor(3c-1)/2\rfloor)$-strategies for $p=3$
and $10\leq c\leq 15$.

In Subsections 4.2 and 4.3 we prove the following theorem.

######  Theorem 4.3.

The presented strategy is a _feasible_ and _optimal_
$\lfloor(3c-1)/2\rfloor$-strategy for $p=3$ and for the corresponding $c\geq
4$.

######  Remark 4.4.

  1. (a)

For even $c$, our presented strategy for the Static Black-Peg AB Game needs
_two questions less_ than the strategy from JD20  for Static Black-Peg
Mastermind (see Strategies 1 and 3 in JD20 ).

  2. (b)

For odd $c$, our presented strategy for the Static Black-Peg AB Game needs
_one question less_ than the strategy from JD20  for Static Black-Peg
Mastermind (see Strategies 2 and 4 in JD20 ).

###  4.2 Feasibility of the $\lfloor(3c-1)/2\rfloor$-Strategy

We start with the following observations.

###### Observation 2

For the $10$-strategy for $c=6$ of Table 5 the following statements hold:

  1. (a)

It consists entirely of $(1,2,2)$-questions, $(2,1,2)$-questions and
$(2,2,1)$-questions.

  2. (b)

It contains neighboring pairs of questions, but no double neighboring pairs.

  3. (c)

No color is missing on any of the pegs.

  4. (d)

It consists of three blocks of three questions each, all having the same
structure, namely one $(1,2,2)$-question, one $(2,1,2)$-question and one
$(2,2,1)$-question. Each two of them are neighboring, but not double
neighboring, and they are not neighboring to any other question.

###### Observation 3

On each peg of the six $\lfloor(3c-1)/2\rfloor$-strategies of Table 4, at most
one color is missing

Now we start with the proof of feasibility. Consider one fixed
$(1,2,2)$-question, $(2,1,2)$-question or $(2,2,1)$-question which lies in one
of the copies of the $9$-strategy of Table 5. We begin our reasoning by
discussing which conclusions can be drawn if the question receives a non-empty
answer $1$B, $2$B or $3$B.

  1. (I)

The answer is $1$B.

Here it is not clear which peg is correct. Again, this can be decided by the
answers to the two neighboring questions. If _both_ answers to the neighboring
questions are empty, then the color of the non-overlapping peg is the correct
one. Otherwise the color of the peg which overlaps with the neighboring
question whose answer contains the larger number of blacks is the correct one.

As an example, consider the strategy for $c=12$ in Table 6(c). For the secret
$(7\,|\,9\,|\,2)$, the answer to the question $Q_{8}=(7\,|\,11\,|\,12)$ is
$1$B. The two neighboring questions to $Q_{8}$ are $Q_{9}=(10\,|\,7\,|\,12)$
and $Q_{10}=(10\,|\,11\,|\,7)$. As the answers to $Q_{9}$ and $Q_{10}$ are
both empty, we know that color $7$ is correct on the first peg.

On the other hand, for the secret $(5\,|\,11\,|\,9)$, the answer to both the
questions $Q_{8}$ and $Q_{10}$ is $1$B and the answer to $Q_{9}$ is empty.
Consequently, color $11$ must be correct on the second peg.

  2. (II)

The answer is $2$B.

Here it is not clear which two pegs are correct. However, this can be decided
by the answers to the two neighboring questions (which lie in the same block)
because _at least_ one of the answers to these neighboring questions is also
non-empty. If _both_ answers are non-empty, then the colors of both
overlapping pegs are correct. Otherwise the color of the peg which overlaps
with the neighboring question that received the empty answer is the
_incorrect_ one.

As an example, consider again the strategy for $c=12$ in Table 6(c). For the
secret $(7\,|\,11\,|\,3)$, the answer to the question $Q_{8}$ is $2$B. As
$Q_{9}$ gives the empty answer and $Q_{10}$ gives the answer $1$B, we know
that color $12$ is _not_ correct on the third peg, so that color $7$ is
correct on the first peg and color $11$ is correct on the second peg.

On the other hand, for the secret $(8\,|\,11\,|\,12)$, the answer to the
question $Q_{8}$ is $2$B, and the answers to $Q_{9}$, $Q_{10}$ are $1$B. Then
we know that color $11$ is correct on the second peg and that color $12$ is
correct on the third peg.

  3. (III)

The answer is $3$B.

The secret is found.

So as soon we have a non-empty answer $i$B to a $(1,2,2)$-question, a
$(2,1,2)$-question or a $(2,2,1)$-question from one of the copies of the
$9$-strategy of Table 5, we can determine the $i$ pegs which gave rise to the
non-empty answers, and thus we know their colors.

So assume that we start with the iterated questions _before_ we ask the base
questions. Then we have four cases after having seen the resulting answers:

  1. (I)

No colors of any of the three pegs have been determined.

By Observation 2(c), this means that the correct colors are those occurring in
the base questions. Thus, they are uniquely determined by the answers to those
questions, thanks to the feasibility of the strategies for $c=4,5,6,7,8,9$ in
Table 4. Their feasibility has been checked by a computer program using brute-
force search SC22 ·

  2. (II)

One peg has been determined.

Then the colors of two pegs are unknown. To prove that they can be determined
from the answers to the base questions, it has to be shown that the
$\lfloor(3c-1)/2\rfloor$-strategies for $c=4,5,6,7,8,9$ in Table 4 remain
feasible if we remove one arbitrary column (corresponding to the already found
peg). The feasibility of these three sub-strategies was again checked by the
computer program SC22 ·

For motivation, in Table 7 we present an example of a feasible
$\lfloor(3c-1)/2\rfloor$-strategy for $c=4$, where adding one copy of the
iterated questions leads to an infeasible $\lfloor(3c-1)/2\rfloor$-strategy
for $c=10$. For the latter, the two possible secrets $(1\,|\,4\,|\,5)$ and
$(2\,|\,3\,|\,5)$ lead to the same combination of answers, namely $1$B, $1$B,
$1$B, $0$B, $0$B, $0$B, $1$B, $0$B, $\dots$, $0$B which shows that the
strategy is not feasible. The reason is that the sub-strategy consisting of
the first two columns for $c=4$ is not feasible, as the secrets $(3\,|\,1)$
and $(4\,|\,2)$ are indistinguishable.

  3. (III)

Two pegs have been determined.

Only the color of one peg is still unknown. This peg is determined by the
answers to the base questions as by Observation 3) on each peg only one color
is missing.

  4. (IV)

Three pegs have been determined.

The secret is found without making use of the base questions.

So we have shown the feasibility of the $\lfloor(3c-1)/2\rfloor$-strategy in
all cases.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $3$ | $2$
$Q_{2}$ | $1$ | $3$ | $4$
$Q_{3}$ | $2$ | $4$ | $3$
$Q_{4}$ | $4$ | $1$ | $3$
(a) $c=4$, $k=4$.

Peg | $1$ | $2$ | $3$
---|---|---|---
$Q_{1}$ | $1$ | $3$ | $2$
$Q_{2}$ | $1$ | $3$ | $4$
$Q_{3}$ | $2$ | $4$ | $3$
$Q_{4}$ | $4$ | $1$ | $3$
$Q_{5}$ | $5$ | $9$ | $10$
$Q_{6}$ | $8$ | $5$ | $10$
$Q_{7}$ | $8$ | $9$ | $5$
$Q_{8}$ | $6$ | $10$ | $8$
$Q_{9}$ | $9$ | $6$ | $8$
$Q_{10}$ | $9$ | $10$ | $6$
$Q_{11}$ | $7$ | $8$ | $9$
$Q_{12}$ | $10$ | $7$ | $9$
$Q_{13}$ | $10$ | $8$ | $7$
(b) $c=10$, $k=13$.

Table 7: Example strategy for $p=3$ and $c=4$ and $c=10$, respectively.

###  4.3 Optimality of the $\lfloor(3c-1)/2\rfloor$-Strategy

We use the following lemma, which in parts (a)-(e) is a generalization of
Lemma 1, and which holds only for $c\geq 5$.

######  Lemma 4.5.

For Static Black-Peg AB Game with $p=3$ and $c\geq 5$ the following statements
hold:

  1. (a)

For each feasible strategy and for each peg there exists at most one color
which does not occur on this peg.

  2. (b)

A feasible strategy cannot contain two $(1,1,\star)$-questions which are
disjoint in the first two pegs. 444Recall that $(q_{1}\,|\,q_{2}\,|\,q_{3})$
and $(q_{1}^{\prime}\,|\,q_{2}^{\prime}\,|\,q_{3}^{\prime})$ are said to be
disjoint in the first two pegs if
$\\{q_{1},q_{2}\\}\cap\\{q_{1}^{\prime},q_{2}^{\prime}\\}=\emptyset$.

  3. (c)

If a feasible strategy contains three $(1,1,\star)$-questions, by possibly
permuting the colors, these questions can be written in the form
$(1\,|\,2\,|\,\star_{1})$, $(2\,|\,3\,|\,\star_{2})$,
$(3\,|\,1\,|\,\star_{3})$, for suitable colors $\star_{1}$, $\star_{2}$,
$\star_{3}$.

  4. (d)

If a feasible strategy contains three $(1,1,\star)$-questions, then on at
least one of the first two pegs of the questions, all $c$ colors must occur.

  5. (e)

A feasible strategy cannot contain four $(1,1,\star)$-questions.

  6. (f)

Let a feasible strategy have a $(1,1,\star)$-question
$(q_{1}\,|\,q_{2}\,|\,\star_{1})$, for a suitable color $\star_{1}$, and let
$q_{3}$ not occur on the first peg and $q_{4}$ not occur on the second peg.
Then $q_{3}\neq q_{4}$ holds and, furthermore, $q_{1}=q_{4}$ or $q_{2}=q_{3}$.

  7. (g)

Let a feasible strategy have two $(1,1,\star)$-questions, and let $q_{1}$ not
occur on the first peg and $q_{2}$ not occur on the second peg. Then, by
permuting colors and reordering questions, we can assume that $q_{1}=3$ and
$q_{2}=1$, and the two $(1,1,\star)$-questions can be written in the form
$(1\,|\,2\,|\,\star_{1})$, $(2\,|\,3\,|\,\star_{2})$, for suitable colors
$\star_{1}$, $\star_{2}$.

By symmetry, statements analogous to (b)-(g) hold for the first and the third
peg, and for the second and the third peg.

######  Proof 4.6.

  1. (a)

Suppose that there are two colors $a$ and $b$ which do not occur on the first
peg. Choose arbitrary colors $x$, $y$ with $x\neq y$ which are neither $a$ nor
$b$, where $x$, $y$ exist because of $c\geq 5$. Then the possible secrets
$(a\,|\,x\,|\,y)$ and $(b\,|\,x\,|\,y)$ are indistinguishable, contradicting
the feasibility of the strategy.

  2. (b)

Suppose that the strategy contains two $(1,1,\star)$-questions. By permuting
colors and using the definition of a $(1,1,\star)$-question, we can assume
that these questions are $(1\,|\,2\,|\,\star_{1})$ and
$(3\,|\,4\,|\,\star_{2})$, for suitable colors $\star_{1}$, $\star_{2}$. Let
$x$ be a color which is different from $1,2,3,4$, where $x$ exists because of
$c\geq 5$. Then the possible secrets $(1\,|\,4\,|\,x)$ and $(3\,|\,2\,|\,x)$
receive the same answers ($1$B or $2$B) for the first two questions and the
same answer (0$B$ or 1$B$) for all other questions, i.e., they are
indistinguishable.

  3. (c)-(e)

The proofs work analogously to the proofs of Lemma 1(c)-(e), respectively, if
we add arbitrary entries on the third peg.

  4. (f)

Let $x$ be an arbitrary color not in $\\{q_{1},q_{2},q_{3},q_{4}\\}$. Again,
$x$ exists because of $c\geq 5$.

First, suppose that $q_{3}=q_{4}$. By assumption, $q_{1}\neq q_{3}=q_{4}\neq
q_{2}$ holds, and thus $(q_{1}\,|\,q_{3}\,|\,x)$ and $(q_{3}\,|\,q_{2}\,|\,x)$
are different and well-defined secrets that lead to the same combination of
answers. Thus, $q_{3}\neq q_{4}$ holds.

Second, suppose that $q_{1}\neq q_{4}$ and $q_{2}\neq q_{3}$. Then the
possible secrets $(q_{1}\,|\,q_{4}\,|\,x)$ and $(q_{3}\,|\,q_{2}\,|\,x)$ lead
to the same combination of answers. Thus, $q_{1}=q_{4}$ or $q_{2}=q_{3}$.

Note that for $c=4$ this statement does not hold. (See the strategy of Table
7(a), where the question $Q_{4}$ is a $(1,1,\star$)-question and where the
four numbers $q_{1}=4$, $q_{2}=1$, $q_{3}=3$, $q_{4}=2$ are disjoint.
Nevertheless the strategy is feasible.)

  5. (g)

Using (b), permuting colors, and possibly switching the two
$(1,1,\star)$-questions, we can assume that these questions are
$(1\,|\,2\,|\,\star_{1})$ and $(2\,|\,a\,|\,\star_{2})$, for suitable colors
$\star_{1}$, $\star_{2}$. The color $a$ cannot be equal to $1$ because then
$q_{1},q_{2}\notin\\{1,2\\}$ would hold and that would make the possible
secrets $(1\,|\,q_{2}\,|\,q_{4})$ and $(q_{1}\,|\,2\,|\,q_{4})$
indistinguishable (where $q_{4}$ is an arbitrary color with
$q_{4}\notin\\{1,2,q_{1},q_{2}\\}$). Hence, we can assume that $a=3$, as
claimed. Applying (f) to the questions $(1\,|\,2\,|\,\star_{1})$ and
$(2\,|\,3\,|\,\star_{2})$, it follows that $q_{1}=2\vee q_{2}=1$ _and_
$q_{1}=3\vee q_{2}=2$. As not both $q_{1}$ and $q_{2}$ can be equal to $2$, it
follows that $q_{1}=3,q_{2}=1$. $\square$

######  Lemma 4.7.

For Static Black-Peg AB Game with $p=3$ and $c\geq 5$, the following
statements hold:

  1. (a)

Let a feasible strategy contain two $(1,1,1)$-questions. Then it contains no
additional $(\star,1,1)$-question, $(1,\star,1)$-question or
$(1,1,\star)$-question.

  2. (b)

A feasible strategy contains at most two $(1,1,1)$-questions.

  3. (c)

Let a feasible strategy contain one $(1,1,1)$-question and let there be one
color for each peg which does not occur on this peg. Then the strategy
contains no further $(\star,1,1)$-questions, $(1,\star,1)$-questions or
$(1,1,\star)$-questions.

  4. (d)

A feasible strategy, where for each peg there exists one color which does not
occur on this peg, contains at most one $(1,1,1)$-question.

######  Proof 4.8.

  1. (a)

Let $Q_{1}$, $Q_{2}$ be the two $(1,1,1)$-questions.

Suppose that $Q_{3}$ is a $(1,1,\star)$-question in the strategy. By Lemma
4.5(c), we can assume that the three questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{1}\\\ \hline\cr Q_{2}&2&3&\star_{2}\\\ \hline\cr Q_{3}&3&1&\star_{3}\end{array}\hskip 5.0pt,$ (6)

where $\star_{1}$, $\star_{2}$, $\star_{3}$ are suitable colors and
$\star_{1}\neq\star_{2}$ (since $Q_{1}$ and $Q_{2}$ are $(1,1,1)$-questions).

By applying Lemma 4.5(b) to $Q_{1}$ and $Q_{2}$ twice, namely to the first and
third peg, and to the second and third peg, the form can be assumed to be

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&3\\\ \hline\cr Q_{2}&2&3&1\\\ \hline\cr Q_{3}&3&1&\star_{3}\end{array}\hskip 5.0pt.$ (11)

Then the possible secrets $(2\,|\,1\,|\,3)$ and $(3\,|\,2\,|\,1)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{2}$, $Q_{3}$ and
$0$B for the remaining questions. This is a contradiction, and so the strategy
contains no additional $(1,1,\star)$-question.

By symmetry, the strategy contains no additional $(1,\star,1)$-question or
$(\star,1,1)$-question either.

  2. (b)

This follows directly from (a).

  3. (c)

Let $Q_{1}^{\prime}$ be the $(1,1,1)$-question and $Q_{2}^{\prime}$ be the
question consisting of the colors which do not occur on the first, second and
third peg, respectively.

Suppose that $Q_{3}^{\prime}$ is a $(1,1,\star)$-question in the strategy. By
Lemma 4.5(g), we can assume that the three questions have the form (6). By
Lemma 4.5(f), we get the form (11).

Then the possible secrets $(2\,|\,1\,|\,3)$ and $(3\,|\,2\,|\,1)$ receive the
same combination of answers, namely $1$B for $Q_{1}^{\prime}$ and
$Q_{3}^{\prime}$, and $0$B for the remaining questions. This is a
contradiction, and so the strategy contains no additional
$(1,1,\star)$-question.

Symmetrically, it follows that the strategy contains no $(1,\star,1)$-question
and no $(\star,1,1)$-question either.

  4. (d)

This follows directly from (c). $\square$

######  Lemma 4.9.

For Static Black-Peg AB Game with $p=3$ and $c\geq 5$, the following
statements hold:

  1. (a)

If a feasible strategy contains a $(1,1,1)$-question, then the strategy
contains in total at most three questions which are
$({\geq\,}2,1,1)$-questions, $(1,{\geq\,}2,1)$-questions or
$(1,1,{\geq\,}2)$-questions.

  2. (b)

If a feasible strategy is such that, for each peg, there exists one color
which does not occur on this peg, then the strategy contains in total at most
three questions which are $({\geq\,}2,1,1)$-questions,
$(1,{\geq\,}2,1)$-questions or $(1,1,{\geq\,}2)$-questions.

######  Proof 4.10.

  1. (a)

Let $Q_{1}$ be a $(1,1,1)$-question of the strategy. We prove two assertions,
which together prove part (a).

    1. (I)

The strategy cannot have two $(1,1,{\geq\,}2)$-questions and two
$(1,{\geq\,}2,1)$-questions at the same time.

Suppose that $Q_{2}$, $Q_{3}$ are two $(1,1,{\geq\,}2)$-questions and $Q_{4}$,
$Q_{5}$ are two $(1,{\geq\,}2,1)$-questions in the strategy. We present two
indistinguishable possible secrets, thus contradicting the assumed feasibility
of the strategy.

By the definition of the AB Game, Definition 1(d) and Lemma 4.5(c) applied to
the first and the second peg and applied to the first and the third peg, we
can assume that the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&4\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{1}\\\ \hline\cr Q_{3}&3&1&\star_{2}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&5\\\ \hline\cr Q_{5}&5&\star_{4}&1\end{array}$

where $\star_{1},\star_{2}\notin\\{1,4,5\\}$ and
$\star_{3},\star_{4}\notin\\{1,2,3\\}$ are colors which occur at least twice
on their peg.

Then the possible secrets $(3\,|\,2\,|\,1)$ and $(5\,|\,1\,|\,4)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{3}$, $Q_{5}$ and
$0$B for the remaining questions.

Symmetrically, it follows that the strategy cannot have two
$(1,1,{\geq\,}2)$-question and two $({\geq\,}2,1,1)$-questions at the same
time, or $(1,{\geq\,}2,1)$-question and two $({\geq\,}2,1,1)$-questions at the
same time.

    2. (II)

The strategy cannot have one $(1,{\geq\,}2,1)$-question, one
$({\geq\,}2,1,1)$-question, and two $(1,1,{\geq\,}2)$-questions at the same
time.

Suppose that $Q_{2}$, $Q_{3}$ are the two $(1,1,{\geq\,}2)$-questions, $Q_{4}$
is the $(1,{\geq\,}2,1)$-question and $Q_{5}$ is the
$({\geq\,}2,1,1)$-question of the strategy. In each case or sub-case we
present two indistinguishable possible secrets, thus contradicting the assumed
feasibility of the strategy.

By the definition of the AB Game, Definition 1(d) and Lemma 4.5(c) applied to
the first and the second peg, we can assume that the five questions have the
form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&b\\\ \hline\cr Q_{2}&2&3&\star_{3}\\\ \hline\cr Q_{3}&3&1&\star_{4}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&d\\\ \hline\cr\hline\cr Q_{5}&\star_{1}&a&e\end{array}\hskip 5.0pt,$

where $\star_{1}$, $\star_{2}$, $\star_{3}$, $\star_{4}$ are colors which
occur at least twice on their peg, and $a$, $b$, $d$, $e$ are colors555Note
that the parameter $c$ is reserved for the number of colors. So we use the
parameters $a,b,d,e,\dots$ here. which occur only once on their peg.

By Lemma 4.5(b) applied to the first and third peg of questions $Q_{1}$ and
$Q_{4}$, and to the second and third peg of questions $Q_{1}$ and $Q_{5}$, we
have

$\displaystyle b=4$ $\displaystyle\vee$ $\displaystyle d=1,$

and

$\displaystyle e=2$ $\displaystyle\vee$ $\displaystyle a=b.$

This leads to the following four cases:

      1. (i)

$a=b=4$.

Here the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&4\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{3}\\\ \hline\cr Q_{3}&3&1&\star_{4}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&d\\\ \hline\cr\hline\cr Q_{5}&\star_{1}&4&e\end{array}\hskip 5.0pt.$

We have three sub-cases:

        1. (1)

All combinations of $(d,e)$ except $d=3$ and except $e=1$.

Here the possible secrets $(3\,|\,4\,|\,d)$ and $(4\,|\,1\,|\,e)$ receive the
same combination of answers, namely $1$B for $Q_{3}$, $Q_{4}$, $Q_{5}$ and
$0$B for the remaining questions. (Note that $d\neq 4$ and $e\neq 4$ as
$Q_{4}$ and $Q_{5}$ are questions in the AB Game.)

        2. (2)

$d=3$.

Here the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&4\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{3}\\\ \hline\cr Q_{3}&3&1&\star_{4}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&3\\\ \hline\cr\hline\cr Q_{5}&\star_{1}&4&e\end{array}\hskip 5.0pt.$

Then the possible secrets $(2\,|\,4\,|\,3)$ and $(4\,|\,3\,|\,e)$ receive the
same combination of answers, namely $1$B for $Q_{2}$, $Q_{4}$, $Q_{5}$ and
$0$B for the remaining questions. (Note that $e\neq 3,4$, as $Q_{5}$ is a
$({\geq\,}2,1,1)$-question having the color $e$ on the last peg.)

        3. (3)

$e=1$.

Here the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&4\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{3}\\\ \hline\cr Q_{3}&3&1&\star_{4}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&d\\\ \hline\cr\hline\cr Q_{5}&\star_{1}&4&1\end{array}\hskip 5.0pt.$

Then the possible secrets $(1\,|\,4\,|\,d)$ and $(4\,|\,2\,|\,1)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{4}$, $Q_{5}$ and
$0$B for the remaining questions. (Note that $d\neq 1,4$, analogously to the
case $d=3$.)

      2. (ii)

$a\neq b=4\wedge e=2$.

Here the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&4\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{3}\\\ \hline\cr Q_{3}&3&1&\star_{4}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&d\\\ \hline\cr\hline\cr Q_{5}&\star_{1}&a&2\end{array}\hskip 5.0pt.$

Then the possible secrets $(1\,|\,3\,|\,2)$ and $(2\,|\,a\,|\,4)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{2}$, $Q_{5}$ and
$0$B for the remaining questions. (Note that $a\neq 2,4$.)

      3. (iii)

$d=1\wedge e=2$.

Here the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&b\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{1}\\\ \hline\cr Q_{3}&3&1&\star_{2}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&1\\\ \hline\cr\hline\cr Q_{5}&\star_{4}&a&2\end{array}\hskip 5.0pt.$

Then the possible secrets $(3\,|\,a\,|\,1)$ and $(4\,|\,1\,|\,2)$ receive the
same combination of answers, namely $1$B for $Q_{3}$, $Q_{4}$, $Q_{5}$ and
$0$B for the remaining questions. (Note that $a\neq 1,3$.)

      4. (iv)

$a=b\neq 4\wedge d=1$.

Here the five questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&a\\\ \hline\cr Q_{2}&2&3&\star_{3}\\\ \hline\cr Q_{3}&3&1&\star_{4}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&1\\\ \hline\cr\hline\cr Q_{5}&\star_{1}&a&e\end{array}\hskip 5.0pt.$

Then the possible secrets $(3\,|\,2\,|\,1)$ and $(4\,|\,1\,|\,a)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{3}$, $Q_{4}$ and
$0$B for the remaining questions. (Note that $a\neq 1,4$.)

Symmetrically, it follows that the strategy cannot have one
$(1,1,\allowbreak{\geq\,}2)$-question, one $({\geq\,}2,1,1)$-question and two
$(1,{\geq\,}2,1)$-questions, or one $(1,1,{\geq\,}2)$-question, one
$(1,{\geq\,}2,1)$-question and two $({\geq\,}2,1,1)$-questions at the same
time.

  2. (b)

Consider a feasible strategy such that there are colors $q_{1}$, $q_{2}$, and
$q_{3}$ which do not occur on pegs 1, 2, and 3, respectively. Let
$Q_{1}=(q_{1}\,|\,q_{2}\,|\,q_{3})$. We aim to apply Lemma 4.9(a) by adding
the question $Q_{1}$ to the given strategy. To be able to do so, we have to
verify that it is a valid question, i.e., the three colors are distinct. For
doing so, we can assume that the strategy contains four questions which are
$({\geq\,}2,1,1)$-questions, $(1,{\geq\,}2,1)$-questions or
$(1,1,{\geq\,}2)$-questions (because otherwise the conclusion of Lemma 4.9(a)
is fulfilled).

By Lemma 4.5(d) and possibly switching the questions, we can assume that there
are two $(1,1,{\geq\,}2)$-questions $Q_{2}$ and $Q_{3}$, a
$(1,{\geq\,}2,1)$-question $Q_{4}$, and a question $Q_{5}$ which is either
also a $(1,{\geq\,}2,1)$-question or a $({\geq\,}2,1,1)$-question. This yields
two cases.

Consider first the case where both $Q_{4}$ and $Q_{5}$ are
$(1,{\geq\,}2,1)$-questions. Applying Lemma 4.5(g), applied once to $Q_{2}$,
$Q_{3}$ and once to $Q_{4}$, $Q_{5}$, yields the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{2}&q_{2}&\star_{1}&\star_{2}\\\ \hline\cr Q_{3}&\star_{1}&q_{1}&\star_{3}\\\ \hline\cr\hline\cr Q_{4}&q_{3}&\star_{5}&\star_{4}\\\ \hline\cr Q_{5}&\star_{4}&\star_{6}&q_{1}\end{array}$

where $q_{1}\neq q_{2}$ and $q_{1}\neq q_{3}$, and $\star_{2}$, $\star_{3}$,
$\star_{5}$, $\star_{6}$ are colors which occur at least twice on their peg,
and $\star_{1}$, $\star_{4}$ are colors occurring only once on their peg.
However, we also know that $Q_{2}$ is a $(1,1,{\geq\,}2)$-question, which
implies that $q_{2}\neq q_{3}$. Hence, all three colors are distinct.

If $Q_{5}$ is a $({\geq\,}2,1,1)$-question, the reasoning is easier: applying
Lemma 4.5(f) thrice, namely to $Q_{2}$, $Q_{4}$, and $Q_{5}$ proves
immediately that $q_{1}\neq q_{2}$, $q_{1}\neq q_{3}$, and $q_{2}\neq q_{3}$,
respectively. Hence, again, all three colors $q_{1}$, $q_{2}$, and $q_{3}$ are
distinct.

Thus, in either case $Q_{1}$ is a valid question. It follows that the strategy
obtained by adding question $Q_{1}$ to the already feasible strategy is
feasible. In this extended strategy, $Q_{1}$ is a $(1,1,1)$-question. Hence,
Lemma 4.9(a) applies, the conclusion being that the modified strategy (and
thus the original one) contains in total at most three questions which are
$({\geq\,}2,1,1)$-questions, $(1,{\geq\,}2,1)$-questions or
$(1,1,{\geq\,}2)$-questions. This completes the proof. $\square$

######  Lemma 4.11.

For Static Black-Peg AB Game with $p=3$ and $c\geq 5$, the following
statements hold:

  1. (a)

If a feasible strategy contains no $(1,1,1)$-question, then it contains in
total at most six questions that are $(1,1,{\geq\,}2)$-questions,
$(1,{\geq\,}2,1)$-questions or $({\geq\,}2,1,1)$-questions.

  2. (b)

If a feasible strategy contains no $(1,1,1)$-question, and for each of two
pegs there is one color which does not occur on this peg, then the strategy
contains in total at most five questions that are $(1,1,{\geq\,}2)$-questions,
$(1,{\geq\,}2,1)$-questions or $({\geq\,}2,1,1)$-questions.

######  Proof 4.12.

  1. (a)

We prove two assertions, which together prove part (a).

    1. (I)

The strategy cannot have three $(1,1,{\geq\,}2)$-questions, three
$(1,{\geq\,}2,1)$-questions and one $({\geq\,}2,1,1)$-question at the same
time.

Suppose that $Q_{1}$, $Q_{2}$, $Q_{3}$ are $(1,1,{\geq\,}2)$-questions,
$Q_{4}$, $Q_{5}$, $Q_{6}$ are $(1,{\geq\,}2,1)$-questions and $Q_{7}$ is a
$({\geq\,}2,1,1)$-question of the strategy.

By Lemma 4.5(c) applied to the first and the second peg and applied to the
first and the third peg, we can assume that the seven questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{5}\\\ \hline\cr Q_{2}&2&3&\star_{6}\\\ \hline\cr Q_{3}&3&1&\star_{7}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{2}&5\\\ \hline\cr Q_{5}&5&\star_{3}&6\\\ \hline\cr Q_{6}&6&\star_{4}&4\\\ \hline\cr\hline\cr Q_{7}&\star_{1}&a&b\end{array}\hskip 5.0pt,$

where $\star_{1}$, $\star_{2}$, $\star_{3}$, $\star_{4}$, $\star_{5}$,
$\star_{6}$, $\star_{7}$ are colors which occur at least twice on their peg,
and $a$, $b$ are colors occurring only once on their peg. In particular,
$a\notin\\{1,2,3\\}$ and $b\notin\\{4,5,6\\}$. Note that the appearance of a
$7$-th color $\star_{1}$ in the questions already proves the assertion for
$c=5,6$ (or, expressed differently, that the assumptions imply $c\geq 7$).

Choose a question $Q=(q_{1}\,|\,q_{2}\,|\,q_{3})$ from the set
$S_{1}:=\\{Q_{1},Q_{2},Q_{3}\\}$ so that $b\neq q_{2}$. (Note that at least
two questions in $S_{1}$ fulfill this condition.)

Similarly, choose a question $Q^{\prime}=(q_{4}\,|\,q_{5}\,|\,q_{6})$ from the
the set $S_{2}:=\\{Q_{4},Q_{5},Q_{6}\\}$ so that $a\neq q_{6}$.

By construction, the possible secrets $(q_{1}\,|\,a\,|\,q_{6})$ and
$(q_{4}\,|\,q_{2}\,|\,b)$ receive the same combination of answers, namely $1$B
for $Q$, $Q^{\prime}$, $Q_{7}$ and $0$B for the remaining questions,
contradicting the feasibility of the strategy.

As an example for $a=4$, $b=3$ choose $Q=Q_{3}$ and $Q^{\prime}=Q_{5}$. Then
the possible secrets $(3\,|\,4\,|\,6)$ and $(5\,|\,1\,|\,3)$ receive the same
combination of answers, namely $1$B for $Q_{3}$, $Q_{5}$, $Q_{7}$ and $0$B for
the remaining questions.

Symmetrically, it follows that the strategy cannot have three
$(1,1,\allowbreak{\geq\,}2)$-questions, three $({\geq\,}2,1,1)$-questions and
one $(1,{\geq\,}2,1)$-question, or three $(1,{\geq\,}2,1)$-questions, three
$({\geq\,}2,1,1)$-questions and one $(1,1,\allowbreak{\geq\,}2)$-question at
the same time.

    2. (II)

The strategy cannot have three $(1,1,{\geq\,}2)$-questions, two
$(1,{\geq\,}2,1)$-questions and two $({\geq\,}2,1,1)$-questions at the same
time.

Suppose that $Q_{1}$, $Q_{2}$ and $Q_{3}$ are $(1,1,{\geq\,}2)$-questions,
$Q_{4}$ and $Q_{5}$ are $(1,{\geq\,}2,1)$-questions and $Q_{6}$ and $Q_{7}$
are $({\geq\,}2,1,1)$-questions of the strategy. Below, we consider an
exhaustive set of cases, presenting in each of them two indistinguishable
possible secrets, thus contradicting the feasibility of the strategy.

By Lemma 4.5(b), applied to the first and the third peg and applied to the
second and the third peg, by possibly switching questions $Q_{4}$ and $Q_{5}$,
and questions $Q_{6}$ and $Q_{7}$, and by applying Lemma 4.5(c) to the first
and the second peg, we can assume that the seven questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{5}\\\ \hline\cr\hline\cr Q_{2}&2&3&\star_{6}\\\ \hline\cr Q_{3}&3&1&\star_{7}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&d\\\ \hline\cr Q_{5}&5&\star_{4}&4\\\ \hline\cr\hline\cr Q_{6}&\star_{1}&a&e\\\ \hline\cr Q_{7}&\star_{2}&b&a\end{array}\hskip 5.0pt,$

where $\star_{1}$, $\star_{2}$, $\star_{3}$, $\star_{4}$, $\star_{5}$,
$\star_{6}$, $\star_{7}$ are colors which occur at least twice on their peg.
and $a$, $b$, $d$, $e$ are colors occurring only once on their peg.

Here the appearance of a $6$-th color $\star_{1}$ in the questions already
proves the assertion for $c=5$ (or, expressed differently, that the
assumptions imply $c\geq 6$).

We consider the following four cases:

      1. (i)

$a\neq 5\wedge b\neq 4$.

Then the possible secrets $(1\,|\,b\,|\,4)$ and $(5\,|\,2\,|\,a)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{5}$, $Q_{7}$ and
$0$B for the remaining questions. (Note that $a\not=2,5$ and $b\not=1,4$.)

      2. (ii)

$a=5\wedge e\neq 3$.

Here the seven questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{5}\\\ \hline\cr Q_{2}&2&3&\star_{6}\\\ \hline\cr Q_{3}&3&1&\star_{7}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&d\\\ \hline\cr Q_{5}&5&\star_{4}&4\\\ \hline\cr\hline\cr Q_{6}&\star_{1}&5&e\\\ \hline\cr Q_{7}&\star_{2}&b&5\end{array}\hskip 5.0pt,$

Then the possible secrets $(2\,|\,5\,|\,4)$ and $(5\,|\,3\,|\,e)$ receive the
same combination of answers, namely $1$B for $Q_{2}$, $Q_{5}$, $Q_{6}$ and
$0$B for the remaining questions. (Note that $e\not=3,5$.)

      3. (iii)

$a=5\wedge e=3$.

Here the seven questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{5}\\\ \hline\cr Q_{2}&2&3&\star_{6}\\\ \hline\cr Q_{3}&3&1&\star_{7}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&d\\\ \hline\cr Q_{5}&5&\star_{4}&4\\\ \hline\cr\hline\cr Q_{6}&\star_{1}&5&3\\\ \hline\cr Q_{7}&\star_{2}&b&5\end{array}\hskip 5.0pt,$

Then the possible secrets $(1\,|\,5\,|\,4)$ and $(5\,|\,2\,|\,3)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{5}$, $Q_{6}$ and
$0$B for the remaining questions.

      4. (iv)

$a\neq 5\wedge b=4\wedge d\neq 1$.

Here the seven questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{5}\\\ \hline\cr Q_{2}&2&3&\star_{6}\\\ \hline\cr Q_{3}&3&1&\star_{7}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&d\\\ \hline\cr Q_{5}&5&\star_{4}&4\\\ \hline\cr\hline\cr Q_{6}&\star_{1}&a&e\\\ \hline\cr Q_{7}&\star_{2}&4&a\end{array}\hskip 5.0pt,$

Then the possible secrets $(1\,|\,4\,|\,d)$ and $(4\,|\,2\,|\,a)$ receive the
same combination of answers, namely $1$B for $Q_{1}$, $Q_{4}$, $Q_{7}$ and
$0$B for the remaining questions. (Note that $a\not=2,4$ and $d\not=1,4$.)

      5. (v)

$a\neq 5\wedge b=4\wedge d=1$.

Here the seven questions have the form

$\displaystyle\begin{array}[]{c || c | c | c}\mbox{Peg}&1&2&3\\\ \hline\cr\hline\cr Q_{1}&1&2&\star_{5}\\\ \hline\cr Q_{2}&2&3&\star_{6}\\\ \hline\cr Q_{3}&3&1&\star_{7}\\\ \hline\cr\hline\cr Q_{4}&4&\star_{3}&1\\\ \hline\cr Q_{5}&5&\star_{4}&4\\\ \hline\cr\hline\cr Q_{6}&\star_{1}&a&e\\\ \hline\cr Q_{7}&\star_{2}&4&a\end{array}\hskip 5.0pt,$

Then the possible secrets $(3\,|\,4\,|\,1)$ and $(4\,|\,1\,|\,a)$ receive the
same combination of answers, namely $1$B for $Q_{3}$, $Q_{4}$, $Q_{7}$ and
$0$B for the remaining questions. (Note that $a\not=1,4$.)

Again, symmetric arguments prove that the strategy cannot simultaneously have
three $(1,{\geq\,}2,1)$-questions, two $({\geq\,}2,1,1)$-questions and two
$(1,1,\allowbreak{\geq\,}2)$-questions, or three $({\geq\,}2,1,1)$-questions,
two $(1,{\geq\,}2,1)$-questions and two $(1,1,{\geq\,}2)$-questions.

This completes the proof of (a).

  2. (b)

Similarly to the proof of Lemma 4.9(b), this case can be proved by modifying
the strategy in order to be able to apply Lemma 4.11(a). Let $q_{1},q_{2}$ be
the colors which do not occur on the first and second peg, respectively. By
Lemma 4.5(f), $q_{1}\neq q_{2}$ holds. Now, let
$Q_{1}=(q_{1}\,|\,q_{2}\,|\,q_{3})$, where the third color $q_{3}$ is chosen
in such a way that it appears at least once on the third peg of another
question but is different from $q_{1}$ and $q_{2}$. Such a color $q_{3}$
exists because by Lemma 4.5(a) there are at least $c-1\geq 4$ distinct colors
on the third peg, so we have at least two to choose from (as we have to
exclude $q_{1}$ and $q_{2}$).

We have thus shown that we can add $Q_{1}$ to the given strategy, where it
becomes a $(1,1,{\geq\,}2)$-question. The extended strategy fulfills the
assumptions of Lemma 4.11(a), which completes the proof. $\square$

Now we come to the actual proof of optimality. For $c=4$ it can be easily
checked by brute-force search that there is no
$(\lfloor(3c-1)/2\rfloor-1)$-strategy, i.e., no strategy with
$k=\lfloor(3\cdot 4-1)/2\rfloor-2=3$ questions. Thus, assume in the following
that $c\geq 5$. The presented $\lfloor(3c-1)/2\rfloor$-strategy has
$k=\lfloor(3c-1)/2\rfloor-1$ questions. We show that this is optimal by
considering any feasible strategy and proving that it must contain at least
$k$ questions.

In the following let $e$ be the number of $(1,1,1)$-questions and $f$ be the
total number of $(1,1,{\geq\,}2)$-questions, $(1,{\geq\,}2,1)$-questions and
$({\geq\,}2,1,1)$-questions of this assumed strategy. Further, for $i=1,2,3$
let $l_{i}$ be the number of colors which occur exactly once on the $i$-th peg
of the strategy.

We will need the following observation, which is easy to see.

###### Observation 4

Every feasible strategy contains at least

$l_{1}+l_{2}+l_{3}-2e-f$

questions. Hence, we can establish optimality of our strategy by showing that
$l_{1}+l_{2}+l_{3}-2e-f\geq k$.

We distinguish between even and odd numbers of colors.

  1. (I)

$c$ even.

We have

$\displaystyle k$ $\displaystyle=$ $\displaystyle\frac{3c}{2}-2.$

By Lemma 4.5(a) for each peg there exists at most one color which does not
occur throughout the entire strategy. We start by proving two claims which
verify optimality in two restricted cases.

######  Claim 1.

If $l_{i}\leq\frac{c}{2}$ for some peg $i\in\\{1,2,3\\}$ on which not all
colors occur, then the strategy contains at least $k$ questions.

This is clear because $l_{i}\leq\frac{c}{2}$ means that $\frac{c}{2}-1$ colors
appear at least twice on peg $i$, yielding at least

$\displaystyle\frac{c}{2}+2\cdot\left(\frac{c}{2}-1\right)\;=\;\frac{3c}{2}-2\;=\;k$

questions.

######  Claim 2.

If $l_{i}\leq\frac{c}{2}+2$ for some peg $i\in\\{1,2,3\\}$ on which all colors
occur, then the strategy contains at least $k$ questions.

Here, the assumption $l_{i}\leq\frac{c}{2}+2$ implies that we have at least

$\displaystyle\frac{c}{2}+2+2\cdot\left(\frac{c}{2}-2\right)\;=\;\frac{3c}{2}-2\;=\;k$

questions.

Now we finish the case (I) of the proof by considering two sub-cases.

    1. (i)

For each of the three pegs there exists one color which does not occur
throughout the entire strategy.

By Claim 1, the situation which remains to be considered is when
$l_{i}\geq\frac{c}{2}+1$ for every $i\in\\{1,2,3\\}$. In this case,

$\displaystyle
l_{1}+l_{2}+l_{3}\;\geq\;3\cdot\left(\frac{c}{2}+1\right)\;=\;\frac{3c}{2}+3\;=\;k+5.$

By Observation 4, it thus remains to be shown that

$\displaystyle 2e+f$ $\displaystyle\leq$ $\displaystyle 5.$

By Lemma 4.7 (b), at most two $(1,1,1)$-questions exist.

      1. (1)

If we have two $(1,1,1)$-questions, then Lemma 4.7 (a) yields

$\displaystyle 2e+f\;=\;2\cdot 2+0\;=\;4.$

      2. (2)

If we have one $(1,1,1)$-question, then Lemma 4.9 (a) yields

$\displaystyle 2e+f\;\leq\;2\cdot 1+3\;=\;5.$

      3. (3)

If we have no $(1,1,1)$-question, then Lemma 4.9 (b) yields

$\displaystyle 2e+f\;\leq\;2\cdot 0+3\;=\;3.$

So we have finished the optimality proof for case (I)(i).

    2. (ii)

For at most two of the three pegs there exists one color which does not occur
throughout the entire strategy.

By Claims 1 and 2, it remains to consider the situation where
$l_{i}\geq\frac{c}{2}+1$ for at most two $i\in\\{1,2,3\\}$ and
$l_{i}\geq\frac{c}{2}+3$ for the remaining ones, i.e.,

$\displaystyle l_{1}+l_{2}+l_{3}$ $\displaystyle\geq$
$\displaystyle\left(\frac{c}{2}+3\right)+2\cdot\left(\frac{c}{2}+1\right)$
$\displaystyle=$ $\displaystyle\frac{3c}{2}+5$ $\displaystyle=$ $\displaystyle
k+7.$

Again using Observation 4, we thus have established that there are at least
$k$ questions if we can show that

$\displaystyle 2e+f$ $\displaystyle\leq$ $\displaystyle 7.$

Again we have at most two $(1,1,1)$-questions.

      1. (1)

If we have two $(1,1,1)$-questions, as in case (I)(i)(I)((i))(1)

$\displaystyle 2e+f\;=\;2\cdot 2+0\;=\;4.$

      2. (2)

If we have one $(1,1,1)$-question, as in case (I)(i)(I)((i))(2)

$\displaystyle 2e+f\;\leq\;2\cdot 1+3\;=\;5.$

      3. (3)

If we have no $(1,1,1)$-question, then by Lemma 4.11 (a)

$\displaystyle 2e+f\;\leq\;2\cdot 0+6\;=\;6.$

So we have finished the optimality proof for case (I)(ii) and thus for case
(I).

  2. (II)

$c$ odd.

We have

$\displaystyle k$ $\displaystyle=$ $\displaystyle\frac{3c}{2}-\frac{3}{2}.$

We proceed similarly to case (I)(i), starting by proving two claims.

######  Claim 3.

If $l_{i}\leq\frac{c-1}{2}$ for some peg $i\in\\{1,2,3\\}$ on which not all
colors occur, then the strategy contains at least $k$ questions.

Clearly, if $l_{i}\leq\frac{c-1}{2}$, then we have at least

$\displaystyle\frac{c-1}{2}+2\cdot\left(\frac{c-1}{2}\right)\;=\;\frac{3c}{2}-\frac{3}{2}\;=\;k$

questions, which verifies the claim.

######  Claim 4.

If $l_{i}\leq\frac{c+1}{2}+1$ for some peg $i\in\\{1,2,3\\}$ on which all
colors occur, then the strategy contains at least $k$ questions.

This is clear as well, because the assumption $l_{i}\leq\frac{c+1}{2}+1$,
together with the fact that all colors occur on peg $i$, implies that we have
at least

$\displaystyle\frac{c+1}{2}+1+2\cdot\left(\frac{c-1}{2}-1\right)\;\geq\;\frac{3c}{2}-\frac{3}{2}\;=\;k$

questions.

Now we finish the part (II) of the proof by considering three sub-cases.

    1. (i)

For each of the three pegs there exists one color which does not occur
throughout the entire strategy.

By Claim 3, we only need to consider the situation where
$l_{i}\geq\frac{c-1}{2}+1$ for every $i\in\\{1,2,3\\}$, which means that

$\displaystyle
l_{1}+l_{2}+l_{3}\;\geq\;3\cdot\left(\frac{c+1}{2}\right)\;=\;\frac{3c}{2}+\frac{3}{2}\;=\;k+3.$

By Observation 4, we thus have to show that

$\displaystyle 2e+f$ $\displaystyle\leq$ $\displaystyle 3.$

By Lemma 4.7 (d), at most one $(1,1,1)$-questions exists, which yields two
cases:

      1. (1)

If we have one $(1,1,1)$-question, then by Lemma 4.7 (c)

$\displaystyle 2e+f\;=\;2\cdot 1+0\;=\;2.$

      2. (2)

If we have no $(1,1,1)$-question, then by Lemma 4.9 (b)

$\displaystyle 2e+f\;\leq\;2\cdot 0+3\;=\;3.$

So we have completed case (II)(i).

    2. (ii)

For exactly two of the three pegs there exists one color which does not occur
throughout the entire strategy.

By Claims 3 and 4, we need to consider the case where
$l_{i}\geq\frac{c-1}{2}+1$ for exactly two pegs $i\in\\{1,2,3\\}$ and
$l_{i}\geq\frac{c+1}{2}+2$ for the remaining peg, which yields

$\displaystyle l_{1}+l_{2}+l_{2}$ $\displaystyle\geq$
$\displaystyle\left(\frac{c+1}{2}+2\right)+2\cdot\left(\frac{c+1}{2}\right)$
$\displaystyle=$ $\displaystyle\frac{3c}{2}+\frac{7}{2}$ $\displaystyle=$
$\displaystyle k+5.$

Again using Observation 4, this means that we have to show that

$\displaystyle 2e+f$ $\displaystyle\leq$ $\displaystyle 5.$

By Lemma 4.7 (b), at most two $(1,1,1)$-questions exist, and so we have the
following cases:

      1. (1)

If there are two $(1,1,1)$-questions, then by Lemma 4.7 (a)

$\displaystyle 2e+f\;=\;2\cdot 2+0\;=\;4.$

      2. (2)

If there is one $(1,1,1)$-question, then by Lemma 4.9 (a)

$\displaystyle 2e+f\;\leq\;2\cdot 1+3\;=\;5.$

      3. (3)

If there is no $(1,1,1)$-question, then by Lemma 4.11(b)

$\displaystyle 2e+f\;\leq\;2\cdot 0+5\;=\;5.$

So we have finished the proof for case (II)(ii).

    3. (iii)

For at most one of the three pegs there exists a color which does not occur
throughout the entire strategy.

Again using Claims 3 and 4, the case to be studied is the one where

$\displaystyle l_{1}+l_{2}+l_{3}$ $\displaystyle\geq$ $\displaystyle
2\cdot\left(\frac{c+1}{2}+2\right)+\left(\frac{c+1}{2}\right)$
$\displaystyle=$ $\displaystyle\frac{3c}{2}+\frac{11}{2}$ $\displaystyle=$
$\displaystyle k+7.$

By Observation 4 we thus need to show that

$\displaystyle 2e+f$ $\displaystyle\leq$ $\displaystyle 7.$

Again we have at most two $(1,1,1)$-questions, and thus the following cases:

      1. (1)

If there are two $(1,1,1)$-questions, then by Lemma 4.7 (a)

$\displaystyle 2e+f\;=\;2\cdot 2+0\;=\;4.$

      2. (2)

If there is one $(1,1,1)$-question, then by Lemma 4.9 (a)

$\displaystyle 2e+f\;\leq\;2\cdot 1+3\;=\;5.$

      3. (3)

If there is no $(1,1,1)$-question, then by Lemma 4.11 (a)

$\displaystyle 2e+f\;\leq\;2\cdot 0+6\;=\;6.$

So the proof for case (II)(iii) is complete, and so is the optimality proof in
its entirety. $\square$

##  5 Conclusions and Future Work

We have introduced a new game, called Static Black-Peg AB Game, a variant of
the AB Game for which, to the best of our knowledge, only the case of equal
number of pegs and colors (called “Static Permutation Mastermind”) has been
studied before GJSS21 ; LMS22 . We have developed optimal strategies for this
game for two and three pegs, extending similar results for Static Black-Peg
Mastermind with two and three pegs Jag16 ; JD18 ; JD20 .

Some of the methods and strategies used in this work would also simplify the
earlier strategies Jag16 ; JD20  of the related Static Black-Peg Mastermind,
which makes them easier to read and reason about. In particular, the iterated
questions of Table 1(c) and 5 can be used in optimal strategies for Static
Black-Peg Mastermind with two and three pegs, respectively.

It would be an interesting task to extend the strategies to more than three
pegs. However, even though such strategies obviously exist, the optimality
proofs will likely be quite challenging. An attempt to do so should probably
aim at developing a schema for constructing optimal strategies for an
arbitrary numbers of pegs $p$. The fact that our strategies for $p=2$ and
$p=3$ pegs clearly share some structural characteristics may provide clues. A
definition of optimal strategies parameterized with $p$ may also facilitate an
optimality proof that works for all of them.

Further, solving Static Black-Peg Mastermind is equivalent to the well-studied
problem of determining the metric dimension of undirected graphs, in our case
the graph $\mathbb{Z}_{c}^{p}$. Thus, the fact that the strategy construction
principle of iterated blocks used in this paper applies to Static Black-Peg
Mastermind as well yields simplified proofs of the metric dimension of
$\mathbb{Z}_{c}^{2}$ and $\mathbb{Z}_{c}^{3}$. We believe that our methods can
furthermore be applied to Static Black-Peg Mastermind for constant $p>3$, and
also to the situation where the pegs have independent numbers of colors. This
would lead to new discoveries regarding the metric dimension of
$\mathbb{Z}_{c}^{p}$ for $p>3$ and of
$\mathbb{Z}_{c_{1}}\times\mathbb{Z}_{c_{2}}\times\times\mathbb{Z}_{c_{3}}$,
where $c_{1},c_{2},c_{3}$ may differ.

## References

  * [1] A.U. Asuncion and M.T. Goodrich.  Nonadaptive Mastermind algorithms for string and vector databases, with case studies.  IEEE Transactions on Knowledge and Data Engineering, 25(1):131–144, 2013.
  * [2] V. Chvátal.  Mastermind.  Combinatorica, 3:325–329, 1983.
  * [3] B. Doerr, C. Doerr, R. Spöhel, and H. Thomas.  Playing Mastermind with many colors.  Journal of the ACM, 63(5):42:1–42:23, 2016.
  * [4] C. El Ouali, M. Glazik, V. Sauerland, and A. Srivastav.  On the query complexity of black-peg AB-Mastermind.  Games, 9(1):2, 2018.
  * [5] P. Erdös and A. Rényi.  On two problems of information theory.  Publ. Math. Inst. Hung. Acad. Sci., 8:241–254, 1963.
  * [6] H. Fernau, P. Heggernes, P. van’t Hof, D. Meister, and R. Saei.  Computing the metric dimension for chain graphs.  Inform. Process. Lett., 115(9):671–676, 2015.
  * [7] R. Focardi and F.L. Luccio.  Guessing bank pins by winning a Mastermind game.  Theory Comput. Syst., 50(1):52–71, 2012.
  * [8] J. Gagneur, M.C. Elze, and A. Tresch.  Selective phenotyping, entropy reduction and the Mastermind game.  BMC Bioinformatics (BMCBI), 12:406, 2011.
  * [9] M.R. Garey and D.S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W.H. Freeman & Co., New York, 1979.
  * [10] C. Glazik, G. Jäger, J. Schiemann, and A. Srivastav.  Bounds for Static Black-Peg AB Mastermind.  In X. Gao, H. Du, and M. Han, editors, Proc. 11th Annual Intl. Conf. Combinatorial Optimization and Applications (COCOA 2017), Part II, volume 10628 of Lecture Notes in Computer Science, pages 409–424, 2017.
  * [11] C. Glazik, G. Jäger, J. Schiemann, and A. Srivastav.  Bounds for the Static Permutation Mastermind Game.  Discrete Math., 344(3):112253, 2021.
  * [12] W. Goddard.  Static Mastermind.  J. Combin. Math. Combin. Comput., 47:225–236, 2003.
  * [13] G. Jäger.  An optimal strategy for Static Black-Peg Mastermind with two pegs.  In T-H. H. Chan, M. Li, and L. Wang, editors, Proc. 10th Annual Intl. Conf. Combinatorial Optimization and Applications (COCOA 2016), volume 10043 of Lecture Notes in Computer Science, pages 670–682, 2017\.
  * [14] G. Jäger and F. Drewes.  An optimal strategy for Static Black-Peg Mastermind with three pegs.  In X. Deng, editor, Proc. 11th International Symposium on Algorithmic Game Theory (SAGT 2018), volume 11059 of Lecture Notes in Comput. Sci., pages 261–266, 2018.
  * [15] G. Jäger and F. Drewes.  The metric dimension of $\mathbb{Z}_{n}\times\mathbb{Z}_{n}\times\mathbb{Z}_{n}$ is $\lfloor 3n/2\rfloor$.  Theoret. Comput. Sci., 806:344–362, 2020.
  * [16] G. Jäger and M. Peczarski.  The number of pessimistic guesses in Generalized Mastermind.  Inform. Process. Lett., 109(12):635–641, 2009.
  * [17] G. Jäger and M. Peczarski.  The worst case number of questions in generalized AB game with and without white-peg answers.  Discrete Appl. Math., 184:20–31, 2015.
  * [18] Ker-I Ko and Shia-Chung Teng.  On the number of queries necessary to identify a permutation.  J. Algorithms, 7(4):449–462, 1986.
  * [19] M. Larcher, A. Martinsson, and A. Steger.  Solving static permutation mastermind using $\mathcal{O}(n\log n)$ queries.  Electron. J. Combin., 29(1):1.20, 2022.
  * [20] A. Martinsson and P. Su.  Mastermind with a linear number of queries.  arXiv:2011.05921, 2018.
  * [21] J.A. Rodríguez-Velázquez, D. Kuziak, I.G. Yero, and J.M. Sigarreta.  The metric dimension of strong product graphs.  Carpathian J. Math., 31(2):261–268, 2015.
  * [22] S. Söderberg and H.S. Shapiro.  A combinatory detection problem.  The American Mathematical Monthly, 70(10):1066–1070, 1963.
  * [23] J. Stuckman and G.Q. Zhang.  Mastermind is NP-complete.  INFOCOMP J. Comput. Sci., 5:25–28, 2006.
  * [24] I.G. Yero, D. Kuziak, and J.A. Rodríguez-Velázquez.  On the metric dimension of corona product graphs.  Comput. Math. Appl., 61(9):2793–2798, 2011.
  * [25] Source code of the computer program of this article.  Available from http://abel.math.umu.se/~gerold/source_code_static_ab_game_23.tar.gz.