One of these things is not like the others

Here’s a puzzle I came across a few days ago (thanks, Mom!):

Which of the following does not belong?

Large green square

Large red circle

Large green circle

Small green circle

Take your time. The answer requires exercising your brainpower in an uncommon way.

The source seems to be Marilyn vos Savant’s Ask Marilyn column in Parade, January 19, 2014, according to this forum and this newsletter and some other sources.

The answer that’s given is 3. 1 is the only square, 2 is the only red, 4 is the only small – so 3 is the only one that’s not the only somethi9ng (that is, it shares its size, its color, and its shape with at least one other of each option).

The natural question for me became: are there other similar puzzles? We can think of this puzzle as picking out four points on a cube. The three dimensions are large/small, green/red, and circle/square. So the original puzzle, abstracted away, looks something like this:

(original version picture goes here)

The four filled-in circles represent the four shapes named in the puzzle. The one that “does not belong” is the one that’s adjacent to the other three, indicated in blue.

Now, let’s consider how many ways there are to pick four vertices of a cube. There are ${8 \choose 4} = 70$ ways to do that, but how many of those are essentially different? I find six, illustrated below:

The top left one represents the puzzle we were given. But in each of the others there’s no way to distinguish one of the four vertices from the other three. Here they are, in turn:

This is the original puzzle. There are eight ways to pick our four vertices that look like this one – pick the blue point (the central one, which will turn out to be distinguished from the rest) to be any of the eight vertices.

This is the “tetrahedral” version. The four chosen vertices form a tetrahedron, so there’s no way to distinguish them from each other; there are two ways to do this.

The four chosen vertices form a rectangle, and are all indistinguishable. There are six such rectangles (each of the twelve edges of the cube is in exactly one, and there are two edges of the cube in each rectangle)

The four chosen vertices form a square face of the cube. The vertices are all indistinguishable. There are six of them.

You can play connect-the-dots with this “twisted” arrangement; there are two central vertices (blue) and two outer vertices (orange), but there’s no way to distinguish between the two blues or between the two oranges. There are 24 such arrangements – pick the central edge (connecting the blues) and then there are two ways to complete.

This “three-on-one” arrangement is the most complicated case. Three vertices form an L (on the bottom of the cube), and the two outer ones (black) can be distinguished from the middle one (orange). The blue one is the one outside of the L. There are twenty-four such arrangements – they’re determined by the L, which is determined by choosing a face (six ways) and a vertex within that face (four ways).

But this doesn’t make a good puzzle: out of a large red circle, a large red square, a large green square, and a small green circle, which one is distinct? You could argue for the small green circle (it’s the only small, corresponding to the blue vertex) but there’s a more convoluted argument for the large red square (of the three larges, it’s the “central” one).

These six families exhaust all the possible ways to pick four vertices from a cube – their sizes add up to 8 + 2 + 6 + 6 + 24 + 24 = 70. (This is the number of orbits of a certain group action and should follow from the Polya enumeration theorem but it was easier to just work these out individually.)

Of these, I believe the puzzle as given is the best one, but this is a matter of taste.

Links for December 22

Emma Pierson on how likely is someone accused of assault by multiple people to be innocent?

A simulation of Buffon’s needle by Eric Wika, writing for Significance magazine.

David Mumford and John Tate wrote an obituary of Grothendieck that Nature wouldn’t accept.

Ben Blatt at Slate complains that dreidel is too slow a game (and shows just how slow), and suggests some ways to speed it up.

Alex Bellos wrote a beginner’s guide to the Game of Life

Ben Schmidt on fundamental plot arcs, seen through multidimensional analysis of thousands of TV and movie scripts.

600613, Brian Hayes on hit frequencies of numbers at Google.

American is much more interracial than it thinks, from Quartz.

Matt Parker for Slate (excerpted from his new book) on the secretary problem.

Ben Blatt on optimizing Santa’s travel. (Traveling salesman, basically, but with the added wrinkle that Santa has to come in the dark.)

Links for December 14

Erica Klarreich at Quanta on large prime gaps.

What makes Paris look like Paris?

Math-inspired Christmas ornaments (sadly, I don’t have a tree).

Nathan Yau at FlowingData has a list of data-ish physical gift things.

From the archives of the MAA, video of David Blackwell on predicting at random (1966).

Today I am prime again

Not only is my age prime, but it’s a Mersenne prime! Barring some great advances in medical technology it’s the last time I’ll be able to say that.

(What else is interesting about the number 31? It seems like a pretty nondescript age life-wise, so I was hoping for some interesting math at least.)

Links for December 7

Brainfilling Curves: A fractal bestiary by Jeffrey Ventrella.

Matt Parker on Numberphile on Stern-Brocot numbers, fractions, and rational numbers (an exposition of my favorite elementary paper, Recounting the rationals by Neil Calkin and Herbert Wilf)

From DataLab (FiveThirtyEight): how common is it for a man to be shorter than his partner? (Mona Chalabi) and which city has the most predictable weather? (Nate Silver and Reuben Fischer-Baum.

I’m just finding this now, although it’s a few months old: there’s a moving sculpture at a biotech firm in Cambridge, Mass. that can look like just a bunch of balls suspended in space until you look at it from the right angle and at the right time.

How to wrap a gift using the least paper.

A puzzle on escaping from prison using coins and a chessboard from DataGenetics.

Brian Hayes (bit-player) onFour Fifths = A Fifth and the Euler-Fermat conjecture.

A video from Numberphile on Sloane’s gap and the paper it’s based on.

How game theory helped improve New York City’s high school application process. (It’s basically the Gale-Shapley algorithm.)

Mike Lawler has a single post assembling the lectures (by Terence Tao, Jacob Lurie, Richard Taylor, Simon Donaldson, and Maxim Kontsevich) from the Breakthrough Prize symposium in mathematics. Here are the abstracts.

Tied elections

Stephen Pettigrew at FiveThirtyEight writes about the 2014 elections that ended in a tie. These are generally resolved by games of chance. The elections that are mentioned there are small ones (two city councilors and a county commissioner); is this because most elections are small or because small elections are more likely to end in ties? Some of both, I think.

Empirically, according to this paper by Casey Mulligan and Charles Hunter, in the period 1898-1992, six out of 16,577 elections to the US House of Representatives were decided by ten votes or less (one was exactly tied), while nine out of 40,036 elections to state legislatures were decided by one vote or less (and two were exactly tied). Looking at this suggests that state elections are more likely to be tied – perhaps because they’re smaller. And in fact the probability of having a “pivotal” election (an election that could be changed with a single vote, according to Mulligan and Hunter, appears to vary like 1 over the number of votes.

This is easy to explain. Very roughly speaking, if we look at two-party elections (I’ll follow Brian Hayes and call the two parties Red and Blue), the proportion of the vote that Blue receives has some distribution; for the sake of argument let’s say that it’s uniform on [0.25, 0.75]. (I don’t actually expect that it’s uniform, but the value at 0.5 is what matters.) Then for Blue’s proportion of the vote received to be in [0.5 – 0.5/n, 0.5 + 0.5/n] in an n-vote election (if n is even, which is the only case when a tie can actually happen) has probability 2/n. The constant 2 depends on my assumption of a prior distribution (although it turns out to match up well with the empirical data) but the 1/n dependence does not. Mulligan and Hunter go a bit deeper and suggest a two-tiered model (there’s a prior on the true proportion of Blue voters, and then voters vote at random according to this) but the broad conclusion is the same.

This suggests that models like the Banzhaf power index don’t make sense in measuring voting power, since votes are not coin flips. The paper The Mathematics and Statistics of
Voting Power by Gelman, Katz, and Tuerlinckx suggets some more realistic models than the coin-flip model.

Incidentally, before looking at the Mulligan and Hunter paper, I was actually thinking that the probability of a tied election would go like the -3/4 power of the number of voters. My thinking was as follows: I had an argument like the 1/n one in my head, but the probability of getting n/2 heads in n coin flips goes like n^-1/2, so why not pick something in between?

And once we’ve found ties, how do we break them? In the three ties mentioned by Pettigrew, one was broken by picking a name from a hat, one by picking blocks from a bag, and one (for a seat on the Neptune Beach, Florida city council) by the following baroque procedure:

Rory Diamond and Richard Arthur had each received 1,448 votes for Seat 4 on the Neptune Beach City Council. To break the tie, Diamond’s name was drawn from a bag by a third party. This allowed Diamond the chance to call the coin toss. He won the toss by calling heads. Because of this, he could decide whether to draw first or second from a bag of ping-pong balls, numbered one through 20. He deferred to Arthur, who drew No. 12. The ball was replaced, and Diamond then drew No. 4. Arthur won the seat.

Why three rounds? Does this provide more randomness than just one round? This Florida Times-Union article suggests that Supervisor of Elections Jerry Holland “wanted the results to seem as random as possible.”

On the nth day of Christmas…

Today PNC Wealth Management announced its Christmas Price Index. This is the cost of buying all the gifts in the song The Twelve Days of Christmas. All 364 of them.

Where’d that number come from? Well, there is one on the first day: a partridge in a pear tree. There are three gifts on the second day: two turtle doves, and a partridge in a pear tree. And so on up until 78 gifts on the twelfth day: twelve drummers drumming, eleven pipers piping, and all the way on down. The total number of gifts bought is 1 + 3 + 6 + … + 78 = 364, which is, coincidentally, one less than the number of days in the year. (The number 365, being just the nearest integer to a ratio of two times, can’t have any number-theoretic significance.)

But what if Christmas lasted n days instead of three? What then?

The identity $1 + 3 + 6 + \cdots + 78 = 364$ is a special case of

${2 \choose 2} + {3 \choose 2} + \cdots + {n+1 \choose 2} = {n+2 \choose 3}$ $

which in turn is a special case of the “hockey-stick identity”

${k \choose k} + {k+1 \choose k} + \cdots + {m \choose k} = {m+1 \choose k+1}$ $

or in more compact notation

$\sum_{j=k}^m {j \choose k} = {m+1 \choose k+1}$ .

Let’s prove this identity. We want to choose $k+1$ elements from the set $\{ 0, 1, 2, \ldots, m \}$ . We can do this by first choosing the largest element, and then choosing the $k$ smaller elements. If we choose $j$ to be the largest element, there will be ${j \choose k}$ ways to pick the $k$ smaller elements from $\{ 0, 1, \ldots, k-1 \}$ ; summing over the possible values of $j$ gives the answer.

But a different way of counting is suggested by observing that over the 364 days, the true love receives:

$1 \times 12 = 12$ partridges-in-pair-trees;
$2 \times 11 = 22$ turtle doves;
$3 \times 10 = 30$ french hens;
…
$12 \times 1 = 12$ drummers drumming

and so we get the identity

$1 \times 12 + 2 \times 11 + 3 \times 10 + \cdots + 12 \times 1 = 364$ .

If there’s anything right with the world, this ought to be a special case of

$1 \times n + 2 \times (n-1) + 3 \times (n-2) + \cdots + n \times 1 = {n+2 \choose 3}$

and why should this be? Let’s write this as

$\sum_{j=2}^{n+1} (j-1) (n+2-j) = {n+2 \choose 3}$

where the reason for the somewhat strange indexing will be apparent shortly.

Let’s count subsets of the set $\{ 1, 2, \ldots, n+2 \}$ of size 3. We can write each such subset as $\{ x, y, z \}$ where we require $x < y < z$ . > Then we’ll count these subsets according to the difference $z - x$ . To construct such a set with $z - x = j$ we must:

choose $x$ . $x$ must be between $1$ and $n+2-j$ inclusive, so there are $n+2-j$ possible choices.
choose $y$ . $y$ must be between $x$ and $z=x+j$ exclusive, so there are $j-1$ possible choices.

At this point $z$ is fixed. So there are $(j-1)(n+2-j)$ ways to choose the 3-set with $z - x = j$ ; summing over the possible values of $j$ gives the answer.

(Is there a natural generaliztion of this later identity that counts sets of sizes 4 or larger?)

So by counting sets of size 3 in two different ways, we’ve made combinatorial proofs of two different identities, both with a binomial coefficient with “lower number” 3.

The 364-gift total has been observed in various places; people who have looked at the math instead of just adding up the numbers include Murray Bourne and Brent Yorgey. And Knuth observed that the song itself has a space complexity of $O(\sqrt{n/(log n)})$ .