## Abstract

In a deductive game for two players, SF and PGOM, SF conceals an n-digit number x = x_{1}, . . ., x_{n} 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 = y_{1}, . . ., yn in base q; each answer is the number of subscripts i such that x_{i} = 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+o_{q}(1))n/log_{q} 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 language | English (US) |
---|---|

Pages | 1215-1220 |

Number of pages | 6 |

DOIs | |

State | Published - 2019 |

Externally published | Yes |

Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019 |

### Conference

Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 1/6/19 → 1/9/19 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)