Counting the same thing twice — page 7
Probability
One coin, counted by runs and by wakings
Beauty is put to sleep and a fair coin is tossed. Heads, she is woken once; tails, twice, with the first waking erased from her memory. Each time she wakes she is asked how likely heads is. One half, say some; one third, say others; and unlike every earlier puzzle of this kind, stating the protocol exactly does not end the argument.
Topology
Every way to pair a polygon's edges
A hexagon's six edges can be paired in fifteen ways. Glue each pair head to tail and five of the fifteen give a sphere and ten give a torus; an octagon's 105 pairings give 14 spheres, 70 tori and 21 surfaces with two handles. The spheres are exactly the pairings whose chords never cross, and the whole table obeys one recurrence found in 1986.
Topology
The surface a random gluing makes
Pair the edges of a large polygon at random and glue each pair head to tail. The surface almost always has nearly as many handles as the polygon allows: a thousand edges leave about seven and a half vertices, and the genus is within four of its ceiling of 250. The vertices behave like the cycles of a random permutation, and their average is a harmonic number.
Algebra
Every power sum, from the coefficients alone
Raise the roots of a polynomial to the k-th power and add them. However the roots turn, the total is a whole number when the coefficients are, and Newton's identities produce it from the coefficients one step at a time — no root is ever found. Run the rule on x³ − x − 1 and out comes Perrin's sequence, whose terms know which numbers are prime, nearly.
Discrete
The streets a postman walks twice
A postman must walk every street of a district and come back. If every corner has an even number of streets, no street needs walking twice. If not, some must — and the ones repeated always join the odd corners in pairs. Pricing every way of pairing them finds the shortest round; pairing the nearest corners first does not.
Probability
The cells a permutation must miss
A derangement is a permutation that misses the diagonal of a square grid. Forbid any other set of cells instead and inclusion–exclusion still counts what is left — driven entirely by one list of numbers, the ways to place non-attacking rooks on the forbidden cells. Boards that look nothing alike can share that list, and rooks on a staircase turn out to count the ways to split a set.
Probability
A round table with no couple together
Seat n couples round a table, men and women alternating, so that nobody sits beside their partner. Once the women are placed the men face a board of forbidden cells that bends round a corner — and that corner is the whole difficulty. The forbidden cells form a cycle, a count of non-adjacent points on a cycle finishes the problem, and the chance of a good seating creeps towards e^(−2) far more slowly than the hat problem reaches 1/e.
Topology
Opposite labels that have to meet
Cut a square into triangles, label every corner +1, −1, +2 or −2, and insist only that opposite points of the edge get opposite labels. Somewhere inside, an edge must join a label to its negative. The proof counts quarter-turns round a diamond — an odd number on the boundary, zero in any triangle that avoids opposites — and making the triangles smaller turns the count back into the theorem about opposite points on the Earth.
Algebra
Twenty-four ways to set a cube down
Count the rotations of a cube from its corners and the answer is eight times three. Count from its edges and it is twelve times two; from its faces, six times four. Three different pictures give one number because each count is the same theorem — the places a thing can go, times the motions that leave it where it is — and the same theorem splits Cayley's sixteen trees into twelve and four and proves that a group of eight has a centre.
Algebra
Necklaces made of symmetries
Lagrange's theorem says a subgroup's size divides the group's, and the converse is false. One piece of the converse is true: every prime that divides the size is the order of some element. The proof threads the group's own elements onto a necklace whose product is nothing, turns it, and counts — the argument that proved Fermat's little theorem with beads, with the beads replaced by motions.
Computation
The rate a noisy channel allows
A channel that flips one bit in ten can still carry messages with as few errors as anyone likes — at up to 0.531 message bits per transmitted bit, and at no rate above that. The number is Shannon's capacity, 1 − H(p). Repetition reaches reliability only by sending nothing; a code chosen at random gets there at any rate below the limit; and the reason there is a limit at all is a count of how many flip patterns a block of noise can hold.
Computation
Erasures a code can see
If a channel loses bits instead of flipping them, and says which ones it lost, its limit rises from 1 − H(p) to 1 − p — and reaching it needs nothing cleverer than a random matrix and the solution of simultaneous equations. A random code needs, on average, 1.607 symbols more than the message it carries, whatever the message's length, and that number is a constant Erdős proved irrational.
Discrete
Every place changes back
A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.
Logic
Half the cube and √n neighbours
Choose more than half the corners of an n-dimensional cube, any way at all, and some chosen corner has at least √n chosen neighbours. That statement about a cube settled a thirty-year question about how sensitive a truth function must be to its inputs, and its proof is a matrix of plus and minus ones whose square is n times the identity. A search over every choice for the 4-cube finds the bound exactly: nine corners, and some corner always has two chosen neighbours.
Number
An order that proves a prime
Fermat's little theorem is a test that primes pass and composites mostly fail, and it can be fooled. Run backwards, it cannot. If some number a has order exactly n − 1 modulo n, then n is prime — because only a prime has n − 1 numbers to cycle through. Checking that takes the prime factors of n − 1, which need proofs of their own, and the proofs nest into a tree that anyone can check: Pratt's certificate, which shows every prime has a short proof of being one.
Probability
Fourteen people within a day
Twenty-three people probably include two with the same birthday. Fourteen probably include two whose birthdays are at most a day apart, and seven, two within a week. The near miss has an exact formula, found by a trick that takes k days away after every birthday and turns the question back into the plain one on a shorter year, and the pattern behind every threshold is a single square root: a window of k days either side makes each pair 2k + 1 times as likely to collide.
Probability
A room where nobody is alone
Twenty-three people probably include two who share a birthday. How many are needed before every single person shares a birthday with somebody else in the room? The answer is 3,064 — more than it takes for every day of the year to be somebody's birthday — and the reason is a count of loners, which rises as the room fills, peaks at 134 when the room is the size of the year, and then falls so slowly that the last loner lingers for thousands of arrivals.
Topology
Twelve pentagons, whatever the hexagons
A football has twelve pentagons and twenty hexagons. A molecule of sixty carbon atoms has the same pattern, a molecule of seventy has twelve pentagons and twenty-five hexagons, and a geodesic dome of any size has twelve places where the pattern of six breaks. None of this is a coincidence of design: Euler's formula, rearranged, says that faces meeting three at a corner must fall short of hexagons by exactly twelve in total, and the hexagons are free.
Topology
Zero in four dimensions
Corners minus edges plus faces is two for every solid. One dimension up, corners minus edges plus faces minus cells is zero for every one of the six regular four-dimensional solids, from the five-cell to the six-hundred-cell, and for every other convex solid in four dimensions. The alternating sum does not break when the dimension rises: it alternates, two in odd dimensions and zero in even ones, because it is measuring a sphere and not a solid.
Number
Two families of solutions, and a box that holds both
Replace the 1 in Pell's equation by 7 and x² − 2y² = 7 still has infinitely many solutions — but they fall into exactly two families, each one an orbit of the same multiplication, and every family has a member inside a box whose size is fixed in advance. How many families there are is then a count of factors, and 3 has none.
Number
Sixty needs two digits and sixty-one needs ten
The smallest solution of x² − 60y² = 1 is x = 31. For x² − 61y² = 1 it is x = 1,766,319,049. The jump is not an accident of 61: the solution is exactly the product of one period's complete quotients, so its size is set by how long the continued fraction takes to come home — and for the cattle problem Archimedes is said to have posed, that product has 103,273 digits.
Algebra
The sums of roots of unity that add to nothing
All n of the n-th roots of unity add to zero, and so does any regular polygon among them, turned. Those are not the only vanishing sums: six thirtieths of a turn close into a loop with no polygon in them. Which counts of roots can close at all is decided by the prime factors of n — no seven fifteenths ever add to zero — and the same question counts where the diagonals of a regular polygon cross.
Algebra
Three ways to pair four roots
Four roots can be split into two pairs in exactly three ways, and the three numbers r·r′ + r″·r‴ those pairings give are the roots of a cubic whose coefficients can be read straight off the quartic. That cubic is where Ferrari's formula gets its cube roots, and it is also a verdict: whether its roots are rational decides which of the twenty-four symmetries the quartic's roots actually have.
Discrete
Cars that park, and trees that grow
Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.