Meng–Lin–Yang's optimal-query conjecture for the Rényi-Ulam game

About 5 years old · traced to

Let k≥1k\ge 1 and a,b≥0a,b\ge 0 satisfy 2k>a2k>a and a+b≥2a+b\ge 2. Define

ch(a,b)≔min⁡{q:(q+1)a+b≤2q}.ch(a,b)\coloneqq\min\big\{q:(q+1)a+b\le 2^q\big\}.

Set

C≔max⁡{ch(a,b),RU0k(2a+b)},C\coloneqq\max\big\{ch(a,b),RU_0^k(2a+b)\big\}, χ0≔max⁡{x:RU1k(x,a−x)≤C−1, x≤a, x≤k},\chi_0\coloneqq\max\big\{x:RU_1^k(x,a-x)\le C-1,\ x\le a,\ x\le k\big\}, χ1≔max⁡{y:RU1k(χ0,y+a−χ0)≤C−1, y≤b, y≤k−χ0}.\chi_1\coloneqq\max\big\{y:RU_1^k(\chi_0,y+a-\chi_0)\le C-1,\ y\le b,\ y\le k-\chi_0\big\}.

Meng–Lin–Yang's conjecture. With these definitions,

RU1k(a,b)=max⁡{C,1+RU1k(a−χ0,b−χ1+χ0)}.RU_1^k(a,b)=\max\big\{C,1+RU_1^k(a-\chi_0,b-\chi_1+\chi_0)\big\}.

This conjecture concerns the optimal query in the Rényi-Ulam game with restricted-size queries, where RU1k(a,b)RU_1^k(a,b) denotes the relevant one-lie query complexity and the parameters describe the current state. The paper presents it as a conjecture about optimal play; no resolution is given in the supplied text.

References

Primary source

Ádám Fraknói, Dávid Márton, Dániel Simon and Dániel Lenger, “On the Rényi-Ulam Game with Restricted Size Queries”, arXiv:2104.01664 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.