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.