How to guess an n-digit number

In a deductive game for two players, SF and PGOM, SF conceals an n-digit number $x = x_1, ..., x_n,$ and PGOM, who knows n, tries to identify x by asking a number of questions, which are answered by SF. Each question is an n-digit number $y = y_1, ..., y_n$; each answer is a number a(x, y), the number of subscripts i such that $x_i = y_i$. Moreover we require the questions from PGOM are predetermined.

In this talk, I will show that the minimum number of questions required to determine x is (2+o(1))n / log n. A more general problem is to determine the asymptotic formula of the metric dimension of Cartesian powers of a graph.

I will state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.

Joint work with Nikita Polyanskii.