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 Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
2019 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, , p. 78Article in journal (Refereed) In press
Abstract [en]

In this work we determine the metric dimension of Zn × Zn × Zn as ⌊3n/2⌋ for all n ≥ 2. We prove this result by investigating a variant of Mastermind.

Mastermind is a famous two-player game that has attracted much attention in the literature in recent years. In particular we consider the static (also called non-adaptive) black-peg variant of Mastermind. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the principal rule is that the codemaker has to choose a secret by assigning colors to the pegs, i.e., the secret is a p-tuple of colors, and the codebreaker asks a number of questions all at once. Like the secret, a question is a p-tuple of colors chosen from the c available colors. The codemaker then answers all of those questions by telling the codebreaker how many pegs in each question are correctly colored. The goal is to find the minimal number of questions that allows the codebreaker to determine the secret from the received answers. We present such a strategy for this game for p = 3 pegs and an arbitrary number c ≥ 2 of colors using ⌊3c/2⌋ + 1 questions, which we prove to be both feasible and optimal.

The minimal number of questions required for p pegs and c colors is easily seen to be equal to the metric dimension of Zpc plus 1 which proves our main result.

Place, publisher, year, edition, pages
2019. , p. 78
Keywords [en]
weighted tree automaton, N-best analysis, tropical semiring
National Category
Computer Sciences Discrete Mathematics
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-159286OAI: oai:DiVA.org:umu-159286DiVA, id: diva2:1317608
Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2019-05-23

Open Access in DiVA

No full text in DiVA

Authority records BETA

Jäger, GeroldDrewes, Frank

Search in DiVA

By author/editor
Jäger, GeroldDrewes, Frank
By organisation
Department of Mathematics and Mathematical StatisticsDepartment of Computing Science
In the same journal
Theoretical Computer Science
Computer SciencesDiscrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 122 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