How to guess an n-digit number

Zilin Jiang, Nikita Polyanskii

Research output: Contribution to conferencePaperpeer-review


In a deductive game for two players, SF and PGOM, SF conceals an n-digit number x = x1, . . ., xn in base q, and PGOM, who knows n and q, tries to identify x by asking a number of questions, which are answered by SF. Each question is an n-digit number y = y1, . . ., yn in base q; each answer is the number of subscripts i such that xi = yi. Moreover, we require PGOM send all the questions at once. We show that the minimum number of questions required to determine x is (2+oq(1))n/logq n. Our result closes the gap between the lower bound attributed to Erdos and Rényi and the upper bounds developed subsequently by Lindström, Chvátal, Kabatianski, Lebedev and Thorpe. A more general problem is to determine the asymptotic formula of the metric dimension of Cartesian powers of a graph. We state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.

Original languageEnglish (US)
Number of pages6
StatePublished - 2019
Externally publishedYes
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019


Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'How to guess an n-digit number'. Together they form a unique fingerprint.

Cite this