Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes

DOI10.1016/S0012-365X(00)00109-6MaRDI QIDQ1586758zbMATH OpenOpenAlexWikidataFDO

Authors Christian Deppe

Publication date 29 August 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00109-6

zbMATH Keywords

transmitting messagesUlam's game

Mathematics Subject Classification ID

Combinatorial games (91A46)

Review text

In Ulam's game, player 1 thinks of a number from 1 to \(N\). Player 2 asks yes or no questions to player 1 who is allowed to lie up to \(\ell\) times. This is equivalent to the problem of transmitting messages over a noisy binary channel with noiseless feedback. The author solves the game for \(\ell=3\) and makes considerable progress in general. The author's solution requires \(N>265\). (If \(N\leq 265\) then an exhaustive computer search is feasible.) The solution is in three parts. A fixed ``opening book is used for the first three questions. Then an algorithm is given for calculating the next question in a general ``mid-game position. At this point, we are at most 15 questions away from victory, and can apply Guzicki's algorithm for the ``end-game.

Recommendations

• scientific article; zbMATH DE number 782050
• Ulam's searching game with two lies
• Searching with lies: The Ulam problem
• Q-Ary Ulam-Renyi Game with Constrained Lies

Cited in

(19)

• Ulam's searching game with a fixed number of lies
• Solution of Ulam's problem on binary search with three lies
• Minimum number of queries for an adaptive liar search game with small sets
• Strategies for the Renyi--Ulam game with fixed number of lies
• Coding with noiseless feedback
• \(Q\)-ary search with one Lie and bi-interval queries
• Perfect minimally adaptive \(q\)-ary search with unreliable tests
• Searching for a counterfeit coin with two unreliable weighings
• The Rényi-Ulam pathological liar game with a fixed number of lies
• Search with noisy and delayed response
• scientific article; zbMATH DE number 1226239 (Why is no real title available?)
• scientific article; zbMATH DE number 512984 (Why is no real title available?)
• Noninteractive guessing games with lies in codes
• Searching games with errors -- fifty years of coping with liars
• Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies
• Correcting a single error in feedback channels
• \(Q\)-ary Rényi-Ulam pathological liar game with one lie
• Playing Guess Who with your kids: code-word strategy against adversaries
• An algorithm for ``Ulam's Game and its application to error correcting codes

This page was built for publication: Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586758)