The Art of Mathematics Can a Christian escape from a lion? How quickly can a rumour spread? Can you fool an airline into accepting oversize baggage? Recreational mathematics is full of frivolous questions in which the mathematician's art can be brought to bear. But play often has a purpose, whether it's bear cubs in mock fights, or war games. In mathematics, it can sharpen skills, or provide amusement, or simply surprise, and collections of problems have been the stock-in-trade of mathematicians for centuries. Two of the twentieth century's greatest players of problem posing and solving, Erdos and Littlewood, are the inspiration for this collection, which is designed to be sipped from, rather than consumed in one sitting. The questions themselves range in difficulty: the most challenging offer a glimpse of deep results that engage mathematicians today; even the easiest are capable of prompting read ers to think about mathematics. All come with solutions, most with hints, and many with illustrations. Whether you are an expert, or a beginner or an amateur, this book will delight for a lifetime. BELA BOLLOBAS is a Senior Research Fellow at Trinity College, Cambridge and holds the Jabie Hardin Chair of Excellence in Combinatorics at the University of Memphis. He has held visiting positions from Seattle to Singapore, from Brazil to Zurich. This is his tenth book. GABRIELLA BOLLOBAS is an eminent portraitist. She has sculpted busts of many outstanding scientists, including Dirac, von Neumann, Hardy, Littlewood, Erdos and Hawking. She lives in Cambridge with her husband. In re mathematica ars proponendi quaestionem pluris facienda est quam solvendi. Georg Cantor Coffee Time in Memphis The Art of Mathematics Coffee Time in Memphis Bela Bollobas University of Memphis and University of Cambridge CAMBRIDGE UNIVERSITY PRESS CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 2RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521872286 © Cambridge University Press 2006 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2006 Printed in the United Kingdom at the University Press, Cambridge A catalog record for this publication is available from the British Library ISBN-13 978-0-521-87228-7 hardback ISBN-10 0-521-87228-6 hardback ISBN-13 978-0-521-693950 paperback ISBN -10 0-521-693950 paperback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. To J.E. Littlewood ( 1885-1977) and Paul Erdos ( 1913-1996) Contents Preface xiii 1 The Problems 1 2 The Hints 36 3 The Solutions 45 1. The Lion and The Christian 45 2. Integer Sequences: Erdos Problems for Epsilons 48 3. Points on a Circle 50 4. Partitions into Closed Sets 52 5. Triangles and Squares 53 6. Polygons and Rectangles 55 7. African Rally 56 8. Fixing Convex Domains 58 9. Nested Subsets 61 10. Almost Disjoint Subsets 63 11. Loaded Dice 64 12. An Unexpected Inequality 65 13. Colouring Lines: the Erdos-Selfridge Theorem 66 14. Independent Sets 68 15. Expansion into Sums 2i 3j 69 16. A Tennis Match 70 17. A Triangle Inequality: Another Erdos Problem for Epsilons 71 18. Planar Domains of Diameter 1 73 19. Orienting Graphs 74 20. A Simple Clock 75 21. Neighbours in a Matrix 76 22. Separately Continuous Functions 77 23. Boundary Cubes 78 24. Lozenge Tilings 79 vii viii Contents 25. A Continuum Independent Set 83 26. Separating Families of Sets 84 27. Bipartite Covers of Complete Graphs 86 28. Convexity and Intersecting Simplices: the Theorems of Radon and Caratheodory 88 29. Intersecting Convex Sets: Helly's Theorem 90 30. Judicious Partitions of Points 92 31. Further Lozenge Tilings 93 32. Two Squares in a Square 95 33. Lines Through Points: the Sylvester-Gallai Theorem 98 34. The Spread of Infection on a Square Grid 104 35. The Spread of Infection in ad-dimensional Box 106 36. Sums of Integers: an Easy Erdos Problem for Epsilons 110 37. Normal Numbers: the Champemowne Number 111 38. Random Walks on Graphs 113 39. Simple Tilings of Rectangles 114 40. L-tilings 116 41. Antipodal Points and Maps: Borsuk's Theorem 117 42. Bodies of Diameter 1: Borsuk's Problem 120 43. Equilateral Triangles: Napoleon's Theorem 124 44. Trisectors of Angles: Morley's Theorem 126 45. Connected Subgraphs 129 46. Subtrees of an Infinite Tree 133 47. Two-distance Sets 134 48. Gossiping Dons 136 49. Exact Covers: the de Bruijn-Erdos Theorem 140 50. Constant Intersections: an Extension of the de Bruijn-Erdos Theorem 142 51. Bell Numbers 144 52. Circles Touching a Square 147 53. Gambling 149 54. Complex Sequences 151 55. Partitions of Integers 153 56. Emptying Glasses 157 57. Distances in Planar Sets 159 58. Monic Polynomials 161 59. Odd Clubs 163 60. A Politically Correct Town 164 61. Lattice Paths 165 62. Triangulations of Polygons 168 Contents IX 63. A Converse of Cauchy's Inequality: Zagier's Inequality 169 64. Squares Touching a Square 170 65. Infection with Three Neighbours 171 66. The Spread of Infection on a Torus 173 67. Dominating Sequences 174 68. Sums of Reciprocals 175 69. Absent-minded Passengers 176 70. Airline Luggage 177 71. Intersecting Sets: the Erd6s-Ko-Rado Theorem 179 72. Spemer Families: the MYBL Inequality 180 73. Five Points in Space 183 74. Triads 184 75. Colouring Complete Graphs 186 76. Symmetric Convex Domains: a Theorem of Besicovitch 187 77. Independent Random Variables 190 78. Triangles Touching a Triangle 192 79. Even and Odd Graphs 193 80. Packing Squares: the Moon-Moser Theorem 194 81. Filling a Matrix 197 82. An Inequality Concerning Triangles: the Erd6s-Mordell Theorem 199 83. Perfect Difference Sets 203 84. Difference Bases 205 85. Satisfied Cricketers: the Hardy-Littlewood Maximal Theorem 208 86. Random Words 212 87. Crossing a Chess Board 214 88. Powers of Paths and Cycles 216 89. Powers of Oriented Cycles 217 90. Perfect Trees 218 91. Circular sequences 220 92. Infinite Sets with Integral Distances 222 93. Finite Sets with Integral Distances 223 94. Cube-free Words: Thue's Theorem 224 95. Square-free Words: the Thue-Morse Theorem 226 96. Addition of Residue Classes: the Cauchy-Davenport Theorem 229 97. Sums Congruent to Zero: the Erd6s-Ginzburg-Ziv Theorem 232 98. Subwords of Distinct Words 237