umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0001-7349-7693
2019 (Engelska)Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, , s. 78Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2019. , s. 78
Nyckelord [en]
weighted tree automaton, N-best analysis, tropical semiring
Nationell ämneskategori
Datavetenskap (datalogi) Diskret matematik
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-159286OAI: oai:DiVA.org:umu-159286DiVA, id: diva2:1317608
Tillgänglig från: 2019-05-23 Skapad: 2019-05-23 Senast uppdaterad: 2019-05-23

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Jäger, GeroldDrewes, Frank

Sök vidare i DiVA

Av författaren/redaktören
Jäger, GeroldDrewes, Frank
Av organisationen
Institutionen för matematik och matematisk statistikInstitutionen för datavetenskap
I samma tidskrift
Theoretical Computer Science
Datavetenskap (datalogi)Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 219 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf