VIⅢ Table of Contents 23.A theorem of Polya on polynomials ...........................159 24.On a lemma of Littlewood and Offord.........................165 25.Cotangent and the Herglotz trick..............................169 26.Buffon's needle problem.....................................175 Combinatorics 179 27.Pigeon-hole and double counting............................. 181 28.Tiling rectangles............................................ 193 29.Three famous theorems on finite sets..........................199 30.Shuffing cards.............................................205 31.Lattice paths and determinants................................215 32.Cayley's formula for the number of trees...................... 221 33.Identities versus bijections...................................227 34.The finite Kakeya problem...................................233 35.Completing Latin squares 239 Graph Theory 245 36.The Dinitz problem........................................247 37.Permanents and the power of entropy .253 38.Five-coloring plane graphs ................................ 261 39.How to guard a museum.........265 40.Turan's graph theorem...................................... .269 41.Communicating without errors...............................275 42.The chromatic number of Kneser graphs.......................285 43.Of friends and politicians....................................291 44.Probability makes counting(sometimes)easy..................295 About the lllustrations 304 Index 305VIII Table of Contents 23. A theorem of Pólya on polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 24. On a lemma of Littlewood and Offord . . . . . . . . . . . . . . . . . . . . . . . . . 165 25. Cotangent and the Herglotz trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 26. Buffon’s needle problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Combinatorics 179 27. Pigeon-hole and double counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 28. Tiling rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 29. Three famous theorems on finite sets . . . . . . . . . . . . . . . . . . . . . . . . . . 199 30. Shuffling cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 31. Lattice paths and determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 32. Cayley’s formula for the number of trees . . . . . . . . . . . . . . . . . . . . . . 221 33. Identities versus bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 34. The finite Kakeya problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 35. Completing Latin squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Graph Theory 245 36. The Dinitz problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .247 37. Permanents and the power of entropy . . . . . . . . . . . . . . . . . . . . . . . . . .253 38. Five-coloring plane graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 39. How to guard a museum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 40. Turán’s graph theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 41. Communicating without errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 42. The chromatic number of Kneser graphs . . . . . . . . . . . . . . . . . . . . . . . 285 43. Of friends and politicians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 44. Probability makes counting (sometimes) easy . . . . . . . . . . . . . . . . . . 295 About the Illustrations 304 Index 305