Papers › On the Rényi-Ulam Game with Restricted Size Queries
On the Rényi-Ulam Game with Restricted Size Queries
Ádám Fraknói, Dávid Márton, Dániel Simon, Dániel Lenger
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We investigate the following version of the well-known R\'enyi-Ulam game. Two players - the Questioner and the Responder - play against each other. The Responder thinks of a number from the set {1,…,n}, and the Questioner has to find this number. To do this, he can ask whether a chosen set of at most k elements contains the thought number. The Responder answers with YES or NO immediately, but during the game, he may lie at most ℓ times. The minimum number of queries needed for the Questioner to surely find the unknown element is denoted by RU_ℓᵏ(n). First, we develop a highly effective tool that we call Convexity Lemma. By using this lemma, we give a general lower bound of RU_ℓᵏ(n) and an upper bound which differs from the lower one by at most 2ℓ+1. We also give its exact value when n is sufficiently large compared to k. With these, we managed to improve and generalize the results obtained by Meng, Lin, and Yang in a 2013 paper about the case ℓ=1.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections