Access Restriction

Author Innes, D.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Computer science ♦ Statistics
Abstract S.M. Ulam (Adventures of Mathematician Scribner, New York, 1976) presented the following problem. If one person picks a number from one to one million and the other person could ask yes or no questions, how many questions would be required to find the number with certainty if the opponent were allowed to lie once or twice. J. Spencer (Mathematics Magazine vol.57, no.2, 1984) found that by using a weight balancing strategy, if n<or=5/8*2/sup k//(k+1) and there is only one lie, then a number in an interval of length n can be found with at most k questions. This still means either 25 or 26 questions will be needed when n=1,000,000 and only questions of the form 'Is x>c' are allowed. However, it will be shown that, by using a somewhat modified algorithm, if n<or=27/128*2/sup k//(k+1), then the number can be found in k-2 questions, no matter what the number or when the lie was told. This result means that the answer to Ulam's question, when only 1 lie is used and only comparison questions are allowed, is, in fact, twenty-five.<<ETX>>
Description Author affiliation: Dept. of Comput. Sci. & Stat., Rhode Island Univ., Kingston, RI, USA (Innes, D.)
ISBN 081862812X
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-05-28
Publisher Place Canada
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 239.38 kB
Page Count 4
Starting Page 92
Ending Page 95

Source: IEEE Xplore Digital Library