Combinatorics Seminar

When: Sunday, March 25, 10am

Where: Schreiber 309

Speaker: Zilin Jiang, Technion

Title: 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 / lg 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.