Table of Contents
Preface and acknowledgments xi
1 Hat colors and hamming codes 1
1.1 The Game 1
1.2 How Well Can a Strategy Work? 3
1.3 Some Mathematics: Hamming Codes 6
1.4 Solution 9
1.5 Hamming Codes in Higher Dimensions 12
1.6 Short History 14
1.7 Practical Advice 14
2 Twenty boxes and permutations 17
2.1 The Game 17
2.2 How Well Can a Strategy Work? 20
2.3 Solution 21
2.4 Some Mathematics: Permutations and Cycles 21
2.5 Understanding the Solution 23
2.6 Short History 31
2.7 Practical Advice 31
3 The dovetail trick and rising Sequences 33
3.1 The Trick 33
3.2 Riffle Shuffling Cards 34
3.3 Some Mathematics: Permutations 37
3.4 Solution 41
3.5 More Mathematics: Shuffling Distributions 43
3.6 Measuring the Goodness of a Shuffle 50
3.7 Short History 52
3.8 Practical Advice 53
4 Animal stickers and cyclic groups 55
4.1 The Game 55
4.2 Solution for 3 Animals 57
4.3 Some Mathematics: Cyclic Groups 61
4.4 Variation: Colored Hats in a Line 64
4.5 Short History 70
4.6 Practical Advice 70
5 Opera singers and information theory 73
5.1 The Game 73
5.2 How Well Can a Strategy Work? 76
5.3 Solution for 5 Singers 77
5.4 Some Mathematics: Information Theory 79
5.5 Variation: Ball Weighing 88
5.6 Random Strategies 89
5.7 Short History 91
5.8 Practical Advice 92
6 Animal matching and projective geometry 93
6.1 The Game 93
6.2 Solution 96
6.3 Fano Planes 96
6.4 Some Mathematics: Projective Geometry 98
6.5 Short History 106
6.6 Practical Advice 106
7 The earth and an eigenvalue 109
7.1 The Game 109
7.2 Solution 113
7.3 Some Mathematics: Linear Algebra 114
7.4 Short History 120
7.5 Practical Advice 120
8 The fallen picture and algebraic topology 123
8.1 The Fallen Picture 123
8.2 Solution for 2 Nails 125
8.3 Dancing 125
8.4 Some Mathematics: Algebraic Topology 127
8.5 Solution, Continued 134
8.6 Short History 137
8.7 Practical Advice 137
A What do we mean when we write …? 139
B What is … 143
B.1 …a Binary Number? 143
B.2 …a Converging Sequence or Series? 144
B.3 …an Exponential Function? 146
B.4 …a Binomial Coefficient? 148
B.5 …a Probability? 150
B.6 …an Expectation? 152
B.7 …a Matrix? 153
B.8 …a Complex Number? 154
C Chapter-Specific details 157
C.1 Chapter 1: Hat Colors and Hamming Codes 157
C.2 Chapter 4: Animal Stickers and Cyclic Groups 162
C.3 Chapter 5: Opera Singers and Information Theory 164
C.4 Chapter 6: Animal Matching and Projective Geometry 167
C.5 Chapter 8: The Fallen Picture and Algebraic Topology 169
References 171
Index 175