adrianN.github.io/guessing_games.html at master · adrianN/adrianN.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <link href="https://adriann.github.io/feed.rss" rel="alternate" type="application/rss+xml" title="What's new on adriann.github.io" />
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <meta http-equiv="Content-Style-Type" content="text/css" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <meta name="generator" content="pandoc" />
  <meta name="author" content="Adrian Neumann (adrian_neumann@gmx.de)" />
  <title>Guessing Games</title>
  <style type="text/css">
  .displayequation{margin-left:auto;margin-right:auto;}
  </style>
  <style>
  .caption{font-size:66%;text-align:right;}
  .figure{float:right;padding-bottom:1em;padding-left:1em;}
  .figure>img{display:block;margin:0 auto;}
  .footnotes{font-size:80%;}
  .block{border-left:1ex solid gray;padding-left:2em;}
  li{padding:0.25em;}
  a:hover{text-shadow: 0 0 5px;}
  body{font-family:sans-serif;max-width:100ex;padding-left:3em;padding-right:2em;}
  code{font-family:Consolas, Inconsolata, Monaco, monospace;}
  p{text-align:justify;}
  </style>
</head>
<body>
<div id="header">
<h1 class="title">Guessing Games</h1>
</div>
<div class="figure">
<img src="pictures/alice_cards.jpg" title="copyright expired" alt="Art by Arthur Rackham" />
<p class="caption">Art by Arthur Rackham</p>
</div>
<p>The Cheshire Cat thinks of a number between <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mn>1</mn><annotation encoding="application/x-tex">1</annotation></semantics></math> and <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> and asks Alice to guess the number as quickly as possible using arbitrary yes/no questions. From her experience in cryptography, Alice has learnt about binary search and is thus confident that she can solve the challenge with <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false" form="prefix">⌈</mo><mo>log</mo><mi>n</mi><mo stretchy="false" form="postfix">⌉</mo></mrow><annotation encoding="application/x-tex">\lceil\log n\rceil</annotation></semantics></math> questions.</p>
<p>However, the Cheshire Cat is known to interpret ‘truthfulness’ a little unconventionally and might lie up to once during the game.</p>
<p>Now Alice could ask every question twice to force the cat into answering correctly, however she’d rather not risk annoying the cat by consuming <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn><mo>log</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">2\log n</annotation></semantics></math> of its time steps.</p>
<p>But is there a better strategy?</p>
<p><br style="clear:both"/> <!--more--></p>
<h2 id="a-strategy-for-alice">A Strategy for Alice</h2>
<p>As it is often the case with these riddles, it turns out there is such a strategy and in fact it is very simple.</p>
<p>Alice begins by determining the bits of the secret number using <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>log</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">\log n</annotation></semantics></math> questions. Next she finds out whether the cat lied already by asking some constant number of times whether this is the correct number. If the cat wants to play as long as possible, it will of course have lied and one of the bits Alice has is wrong. However, it is now very easy for Alice to figure out which bit is wrong by performing a binary search on the bits. Note that it is not very difficult to generalise this for the case where <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>k</mi><annotation encoding="application/x-tex">k</annotation></semantics></math> lies are allowed.</p>
<p>This strategy needs</p>
<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>log</mo><mi>n</mi><mo>+</mo><mo>log</mo><mo>log</mo><mi>n</mi><mo>+</mo><mi>O</mi><mo stretchy="false" form="prefix">(</mo><mn>1</mn><mo stretchy="false" form="postfix">)</mo></mrow><annotation encoding="application/x-tex">\log n + \log \log n + O(1)</annotation></semantics></math></p>
<p>questions. A proof by hand-waving shows this to be a lower bound too.</p>
<h2 id="further-remarks">Further Remarks</h2>
<p>This game is known as Rényi-Ulam’s game and got some attention in coding theory. Apparently it is rather difficult to find the exact number of questions needed or rigorously show lower bounds. There is <a href="http://en.wikipedia.org/wiki/Ulam&#39;s_game">a wikipedia article</a> with further references.</p>
<hr/>
<div style="display:inline-flex;flex-wrap:wrap;justify-content:space-between;font-size:80%">
<p style="margin-right:2ex">CC-BY-SA <a href="mailto:adrian_neumann@gmx.de">Adrian Neumann</a> (PGP Key <a href="https://adriann.github.io/ressources/pub.asc">A0A8BC98</a>)</p>
<p style="margin-left:1ex;margin-right:1ex"><a href="http://adriann.github.io">adriann.github.io</a></p>
<p style="margin-left:2ex"><a href="https://adriann.github.io/feed.rss">RSS</a></p>
</div>
</body>
</html>