{"entities":{"Q1114408":{"pageid":1125157,"ns":120,"title":"Item:Q1114408","lastrevid":49238362,"modified":"2026-01-06T20:11:26Z","type":"item","id":"Q1114408","labels":{"en":{"language":"en","value":"Solution of Ulam's problem on binary search with two lies"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4082990"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114408$7D7E85D1-0602-409A-AC61-6625CECD763D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5caba1464e99eaeb0f583b3bc5456ef388f7622e","datavalue":{"value":{"text":"Solution of Ulam's problem on binary search with two lies","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114408$829B6678-C111-4E50-A5EB-81ED66389C7A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"734467273a360ba331a0b6b98a049e8324e8305e","datavalue":{"value":"0662.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114408$F395F611-6443-43B8-87E9-57A26F002972","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2c68ecfecff3c8fa55b12516bc62c26146efa8cc","datavalue":{"value":"10.1016/0097-3165(88)90065-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114408$47B148CA-4099-4E2E-8DFC-98745BAFC1DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f70bd5d665b09e37810d29837066cb82ce58a25","datavalue":{"value":{"entity-type":"item","numeric-id":203739,"id":"Q203739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114408$A0C900F4-DFEA-4B4A-9F8F-085A283AD98F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"685bde8c367f18365d551a594d09a5ad87b8d248","datavalue":{"value":{"entity-type":"item","numeric-id":235631,"id":"Q235631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114408$3A39906F-D2CC-4F92-9D8E-3BB9958AE28B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8059b8b5e7d67e2c7a1c512c2a2acd219f0f77d3","datavalue":{"value":{"entity-type":"item","numeric-id":186051,"id":"Q186051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114408$8EFA1206-566B-499A-A4C8-6A204B5AF946","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114408$7E1B197B-0876-4FFD-9D17-39DD015F729F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1114408$AA957911-8AF5-495E-A2EF-CA85B654FE37","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e58b5e2a0e3cf2ccb823bbe81b17330c3b16fb3","datavalue":{"value":"Someone thinks of a number between one and one million (which is just less than \\(2^{20})\\). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half million ? then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than \\(\\log_ 2(1,000,000)\\). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer ? [\\textit{S. M. Ulam}, ``Adventures of a mathematician'' (Scribner's (New York, 1976; Zbl 0352.01009), p. 281)].    We prove that Ulam's problem has the following solution:    Theorem. Twenty-nine is the least number of yes-no questions sufficient to find an integer between one and one million, if up to two lies are allowed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114408$B5999DF8-CA35-41AA-B504-7F34D7874FE5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114408$CF211460-95F9-400C-A996-5AFBB2323114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114408$433B1E9D-2B99-4B7E-BD5E-EBD5E539A53E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8fcb38a53f3a9010219b69cc8d1559e46bf9fe35","datavalue":{"value":"4082990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114408$4C47CD1A-6A15-4B33-9FA3-A39DA7B34F71","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d0f36026d334cd68fd5a9914245428075baafbe","datavalue":{"value":"binary search with two lies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114408$46076898-2840-4395-AD8C-2DF3A2D0DF67","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114408$A6C8289C-26FD-4EB1-B267-EC0CA30ACB78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"05052ab5a847b9d7dcf8e08621923307f9279801","datavalue":{"value":"https://doi.org/10.1016/0097-3165(88)90065-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114408$4A3FCD1F-A810-4863-B3AA-870C0780965C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2a0a950c3a1a2a93168ee1432441b3310410a131","datavalue":{"value":"W2031876674","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114408$0A7F6B46-A0ED-429F-80F1-B66AA8639EDD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ccdd460d69b882b62f704391818af0c3b773589","datavalue":{"value":{"entity-type":"item","numeric-id":1090471,"id":"Q1090471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e47186aecb3cf9520c7f4814f710d992ca97014","datavalue":{"value":{"amount":"+0.9586450457572936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114408$C2F020C8-6034-4C60-B164-043A3A2B46C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5022f442fe7bcf38374475e679bb22685f4c2d57","datavalue":{"value":{"entity-type":"item","numeric-id":4841306,"id":"Q4841306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeac95c39804f73940254efa7dd5d0a7413ed4d1","datavalue":{"value":{"amount":"+0.9531168341636658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114408$1B7024B9-93C4-4472-903C-C7B32B233908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb69d2ec1ef412435cc742c77a596f180791a6c7","datavalue":{"value":{"entity-type":"item","numeric-id":1884914,"id":"Q1884914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeac95c39804f73940254efa7dd5d0a7413ed4d1","datavalue":{"value":{"amount":"+0.9531168341636658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114408$F960393D-B32E-4152-B171-A30EF4CA26DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33d5b9a2ccbb64c9ce26dd8694474a8edf1cc857","datavalue":{"value":{"entity-type":"item","numeric-id":749204,"id":"Q749204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdfa5342290610fd9d39c699e85377a03ac37f66","datavalue":{"value":{"amount":"+0.9331386089324952","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114408$886FC274-4623-4270-B3C7-2D0F72690D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f2795f98d934464c70ea42b662944e23971cbb2","datavalue":{"value":{"entity-type":"item","numeric-id":1199612,"id":"Q1199612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03caa201e0e190846efb0cf2321cbdcfa07cb6a4","datavalue":{"value":{"amount":"+0.908279836177826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114408$22A19193-B3D6-406D-B3E5-25FF0B51208B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114408","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114408"}}}}}