umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The worst case number of questions in Generalized AB game with and without white-peg answers
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Institute of Informatics, University of Warsaw, Poland.
2015 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 184, 20-31 p.Article in journal (Refereed) Published
Abstract [en]

The AB game is a two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. It is a variant of the famous Mastermind game, with the only difference that all pegs in both, the secret and the questions must have distinct colors. In this work, we consider the Generalized AB game, where for given arbitrary numbers p, c with p <= c the secret code consists of p pegs each having one of c colors and the answer consists of a number of black and white pegs. There the number of black pegs equals the number of pegs matching in the corresponding question and the secret in position and color, and the number of white pegs equals the additional number of pegs matching in the corresponding question and the secret only in color. We consider also a variant of the Generalized AB game, where the information of white pegs is omitted. This variant is called Generalized Black-peg AB game. Let ab(p, c) and abb(p, c) be the number of questions in the worst case needed by the codebreaker to guess the secret for Generalized AB game and Generalized Black-peg AB game, respectively. Combining a computer program with theoretical considerations, we confirm known exact values of ab(2, c) and ab(3, c) and prove tight bounds for ab(4, c). Furthermore, we present exact values for abb(2, c) and abb(3, c) and tight bounds for abb(4, c)

Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 184, 20-31 p.
Keyword [en]
Combinatorial problem, Logic game, Mastermind, Computer-aided proof
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-100106DOI: 10.1016/j.dam.2014.10.032ISI: 000352174700003OAI: oai:DiVA.org:umu-100106DiVA: diva2:790213
Note

Available online 22 November 2014

Available from: 2015-02-23 Created: 2015-02-23 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jäger, Gerold

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete Applied Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 93 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf