{"entities":{"Q952012":{"pageid":953860,"ns":120,"title":"Item:Q952012","lastrevid":57234876,"modified":"2026-03-27T14:31:56Z","type":"item","id":"Q952012","labels":{"en":{"language":"en","value":"A simple solution to Ulam's liar game with one lie"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5362010"}},"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":"Q952012$9EAD5C13-6D38-4157-9DF6-E2E95257455C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d75257b5c7acf81b935257bda0d7cd2e1c751053","datavalue":{"value":{"text":"A simple solution to Ulam's liar game with one lie","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q952012$425F7DF5-C515-4EE1-9BF3-2340AF0E50D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4b2f3c3278052bf08c90ebfc5c94520d4354c93","datavalue":{"value":"1230.91004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952012$DF4FC305-82A6-4115-8FCA-667E5D0E8163","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f5b7bd86a4d13418d469f3bb16312578a5e608a","datavalue":{"value":"10.4171/EM/92","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952012$4B34B270-6927-4906-8DCC-EFBE3976CD2F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc86f1b81df45a93f566e4bce0d225a8746a087d","datavalue":{"value":{"entity-type":"item","numeric-id":256989,"id":"Q256989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$69784C2A-BBF8-4545-B8C1-EBE0EC07455F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4165d6e2a7d70e11b05d55e4c9f79513959d4d0","datavalue":{"value":{"entity-type":"item","numeric-id":952011,"id":"Q952011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$C8AD8D0E-401E-46BC-9652-6221FC27DC1C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"255223deab9a614645300983eff9e9b445f432d0","datavalue":{"value":{"entity-type":"item","numeric-id":207920,"id":"Q207920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$77FA1B00-5AD4-4596-9075-857F244DF811","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82c79b8a868479c39c5472830d24e23fa49d7c7b","datavalue":{"value":{"time":"+2008-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q952012$DB7998EB-6A21-4F64-80E8-9ECAB2885114","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f17d73b8314a27a393bb23eda016eeef3aad614","datavalue":{"value":"https://arxiv.org/abs/0705.1220","type":"string"},"datatype":"url"},"type":"statement","id":"Q952012$660193AB-50A0-4CDD-97B2-5B9F7828F540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f2cdb1fce14afb874c3d188f51e6c6a3099f2065","datavalue":{"value":"http://www.ems-ph.org/journals/show_pdf.php?issn=0013-6018&vol=63&iss=2&rank=4","type":"string"},"datatype":"url"},"type":"statement","id":"Q952012$0A83DDF4-0019-4C2C-9F09-19B70E11012E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"788e9a6d775c2b016a3913a7390c2b20379d02bd","datavalue":{"value":"In the general form of Ulam's liar game between a questioner and a responder, the responder thinks of an integer \\(x\\) in \\(\\{1, \\ldots,n\\}\\) and the questioner must determine \\(x\\) by asking questions the answers to which are ``yes'' or ``no''. The responder is allowed to lie on at most \\(k\\) of the responses. Let \\(q_k(n)\\) denote the maximum number of questions needed by the questioner, in an optimal strategy, to determine \\(x\\). Based on earlier work by \\textit{R. L. Rivest} et al. [J. Comput. Syst. Sci. 20, 396--404 (1980; Zbl 0443.68043)], \\textit{A. Pelc} [J. Comb. Theory, Ser. A 44, 129--140 (1987; Zbl 0621.68056)] determined \\(q_1(n)\\) for all \\(n\\).   The authors of the present paper give a relatively simple strategy and analysis for the game with \\(k=1\\) which implies the result of Pelc for many values of \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q952012$DE226C7C-00AC-4A4A-9396-0E1B3C1BF51B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6cd669872d281c67042af939aa0a07de1efaf0d9","datavalue":{"value":{"entity-type":"item","numeric-id":227634,"id":"Q227634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$37C8FC3C-72F5-4D7E-8C07-FBE88A5DAD17","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952012$D3DF391B-491E-4B3C-8D38-EEF58DDECC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bc7eb0f462deb89a5bf6af1abf9a96ba13c81d67","datavalue":{"value":"91A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952012$DF5E6C16-F064-4CD6-B1FA-1D34BB66DE3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8049aaf505238fd745e79486b10c636aad05a980","datavalue":{"value":"5362010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952012$E3545461-039E-4535-97E5-782596F8739B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b77075eb40a326d8ead02077a0da038e5fbe3377","datavalue":{"value":"Ulam's liar game","type":"string"},"datatype":"string"},"type":"statement","id":"Q952012$9E161804-D4B0-46BF-8F86-E45ED537802C","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":"Q952012$1BD20128-F86B-4A9D-AD47-05A4302BD140","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ce571509b1b0a4a2a086e9ea837905eca08d26d","datavalue":{"value":{"entity-type":"item","numeric-id":5568914,"id":"Q5568914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$2D7FC4B2-6B27-469E-8313-E33B96C57784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44d62f9b75758dfea06a7465c081df081245b87c","datavalue":{"value":{"entity-type":"item","numeric-id":625104,"id":"Q625104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$80C1ECB5-0973-44A8-BE08-857AE2E010EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"945a95c31317b07313f5d73aa313aa1cad194a9e","datavalue":{"value":{"entity-type":"item","numeric-id":4841306,"id":"Q4841306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$C8583D2B-A5C1-4C33-A8FB-9F1129B975B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb953e83005013fc04f127863b0565d2a756d106","datavalue":{"value":{"entity-type":"item","numeric-id":1090471,"id":"Q1090471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$4413CD35-02C8-482B-894F-9AF01EC05C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa6738f8836aa23af9dd43f5bd3c7e86dc1a985","datavalue":{"value":{"entity-type":"item","numeric-id":5958303,"id":"Q5958303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$A30FA073-A279-4DDE-B8A0-2AABD0EA9494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4d55e2805f215a7a35e3c231c9cfbc5b6ec954","datavalue":{"value":{"entity-type":"item","numeric-id":1144379,"id":"Q1144379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$0F77374C-460F-4896-839D-AA57AFF0B878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfa4c64477270a34e60163db3f94c231bcea10f9","datavalue":{"value":{"entity-type":"item","numeric-id":3325513,"id":"Q3325513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$B61A59EE-7DEB-441F-8E51-FD65653D9A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e48cb6a7885d7c9ab7f8fc4dfc25aaae46425156","datavalue":{"value":{"entity-type":"item","numeric-id":1184984,"id":"Q1184984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$1DBB37C0-F7F0-4F61-A288-9C3D9BBD5D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfc614df367014cf27e62a3682aa19350a52cebc","datavalue":{"value":{"entity-type":"item","numeric-id":4121861,"id":"Q4121861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952012$441C0784-93C6-46C8-8A80-F8B26928B82B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6507e91d8073c9f87d301c6641faa3388fefdc22","datavalue":{"value":{"entity-type":"item","numeric-id":1184984,"id":"Q1184984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01d1da012a18cb874bad854d794e707a8d0b3fd0","datavalue":{"value":{"amount":"+0.9111011624336244","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":"Q952012$AC9E6FB2-C18B-48B8-A7EE-C449CF20BF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a65b3d8b71a2a9a2f170b9a1adfb972e5b3c684","datavalue":{"value":{"entity-type":"item","numeric-id":3439260,"id":"Q3439260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f36bdb5d4f8a4c93de506777d1881fb444b1b872","datavalue":{"value":{"amount":"+0.91064190864563","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":"Q952012$50EDC0CB-5AB5-4D12-8976-DCF08EDFE2BB","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":"a57c1d6c89ad68cdd08b60ef4184a4ec63a7c131","datavalue":{"value":{"amount":"+0.8939377665519714","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":"Q952012$929E2452-B704-4649-8EA1-56AAD100ADAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b143223f2cb627c4e62bdec967e4a0dee8f59776","datavalue":{"value":{"entity-type":"item","numeric-id":998465,"id":"Q998465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a57c1d6c89ad68cdd08b60ef4184a4ec63a7c131","datavalue":{"value":{"amount":"+0.8939377665519714","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":"Q952012$68D9A96F-8973-411C-8196-F83F7E560D27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db350a1f47a34a0e4484b4c5f11239f695551ceb","datavalue":{"value":{"entity-type":"item","numeric-id":1978508,"id":"Q1978508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6f6b3db252d9991e3afa14667e1fab7040bee0e","datavalue":{"value":{"amount":"+0.8926092982292175","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":"Q952012$57CC2AB2-013C-4CC7-BA33-0516FDAA99D3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:952012","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:952012"}}}}}