| 1. |
- Glazik, Christian, et al.
(författare)
-
Bounds for Static Black-Peg AB Mastermind
- 2017
-
Ingår i: COCOA 2017. - Cham : Springer Berlin/Heidelberg. - 9783319711461 - 9783319711478 ; , s. 409-424
-
Konferensbidrag (refereegranskat)abstract
- Mastermind is a famous two-player game introduced by M. Meirowitz (1970). Its combinatorics has gained increased interest over the last years for different variants.In this paper we consider a version known as the Black-Peg AB Game, where one player creates a secret code consisting of c colors on p <= c pegs, where each color is used at most once. The second player tries to guess the secret code with as few questions as possible. For each question he receives the number of correctly placed colors. In the static variant the second player doesn't receive the answers one at a time, but all at once after asking the last question. There are several results both for the AB and the static version, but the combination of both versions has not been considered so far. The most prominent case is n:=p=c, where the secret code and all questions are permutations. The main result of this paper is an upper bound of O(n^{1.525}) questions for this setting. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of \Omega(n\log n). Furthermore, we complement the upper bound for p=c by an optimal (\lceil 4c/3 \rceil -1)-strategy for the special case p=2 and arbitrary c >= 2 and list optimal strategies for six additional pairs (p,c) .
|
|
| 2. |
- Glazik, Christian, et al.
(författare)
-
Bounds for the Static Permutation Mastermind game
- 2021
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 344:3
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper' we introduce a variant of Mastermind, which we call Static Permutation Mastermind and which is defined as follows. One player creates a secret code, called secret, consisting of n colors on n pegs, where each color is used exactly once. The second player tries to determine the secret with as few questions as possible, where each question is a possible secret and all questions are asked at once. After having asked all questions, he receives for each question the number of correctly placed colors and has one more try to determine the secret. The main result of this paper is an upper bound of O(n1.525) questions. It is proved by a distinction of pairs of possible secrets with low and high Hamming distance. For pairs with a low Hamming distance we construct questions using certain arithmetic progressions. For pairs with a high Hamming distance we estimate the size of a vertex cover in a suitable hypergraph. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of Ω(nlogn).
|
|
