A calendar puzzle with some wrinkles

FiveThirtyEight’s puzzle feature, the Riddler, had a puzzle this week called Don’t throw out that calendar!.  (Spoilers below; also, I’m delaying posting this until after the submission period for solutions ends.). This puzzle is due to Ben Zimmer.

Sometime in the 21st century, the following conversation takes place:

“Don’t throw out that calendar! You could reuse it in the future, when the days and dates on the calendar match up again.”

“OK, but that won’t happen for a long time. Forty years, in fact.”

“You’re right! In fact, this calendar has never had a 40-year gap before.”

What year is it?

We can start by observing that there are 14 possible calendars.  To know what calendar we can use in a given year, we have to know whether it’s a common (non-leap) or leap year, and the day of the week of one particular day.    Let’s pay attention to what John Conway called “Doomsday”, i. e. the last day of February (February 28 in common years, and February 29 in leap years).  Doomsday moves forward one day in the week each year, except two days in each leap year – so, for example, Doomsday (February 28) 2015 was a Saturday, Doomsday (February 29) 2016 was a Monday, and Doomsday (February 28) 2017 will be a Tuesday.

So let’s consider when a 40-year gap will happen.  A 40-year gap can’t begin with a common year.   Say the year Y is the year after a leap year; then Doomsday of Y+6 will be the same as Doomsday of Y, since over those six years Doomsday will move forward six days in the week, plus one day for the leap year.  If Y is two or three years after a leap year, then Y + 11 and Y will have the same Doomsday – Doomsday moves forward 11 days, plus three for the leap years.  (This is basically cribbed from the calendar FAQ.

The exception is if Y is very near the end of a century that isn’t divisible by 400 – near enough that one of the otherwise intervening leap years would be a common year.  In any of these cases Y and Y + 12 share a calendar – there are two intervening leap years.

(In most cases Y and Y + 28 share a calendar – that is, if no end-of-century common year intervenes. But we’d still have to do the casework anyway.)

So we must be in a leap year.  But a 40-year gap, from Y to Y + 40, should lead to a Doomsday being one day later (40 + 10 = 50, which is one more than a multiple of seven)  We must be in a leap year for which there are only NINE leap years in the next 40 – i. e. we’re in one of 2064, 2068, …, 2096 – since 2100 isn’t a leap year.   But the calendars 2064 and 2068 will be repeated in 2092 and 2096 (28 years later, with 7 leap years), and 2092 and 2096 will be repeated twelve years later (with two leap years).  So we must be in one of the five years 2072, 2076, 2080, 2084, and 2088.

Which one is it?  See the note “You’re right! In fact, this calendar has never had a 40-year gap before.”  By the same reasoning as above, 40-year gaps in the past could have only happened in starting in one of the leap years 1672-1688, 1772-1788, 1872-1888, since the Gregorian calendar – which insituted our current leap-year policy and thus the nine-in-forty loophole started in 1582.  (1600 and 2000 were leap years, so 15xx and 19xx candidates are out.)

Doomsday in 1672 in the Gregorian calendar was Monday. I cheated by looking it up. For example you can type ncal -sFR 1672 at your friendly Unix prompt, where “FR” is the country code for France, a country that adopted the Gregorian calendar at the beginning. Honestly, it doesn’t matter what day of the week Doomsday in 1672 is, only the relationships between the Doomsdays. In 1772 Doomsday is Saturday (124 days later in the week, that is, 100 years plus 24 leap years); in 1872 it’s Thursday.  So we can work out the doomsdays for each leap year. These are:

1672 through 1688: Mon, Sat, Thu, Tue, Sun

1772 through 1788: Sat, Thu, Tue, Sun, Fri

1872 through 1888: Thu, Tue, Sun, Fri, Wed

2072 through 2088: Mon, Sat, Thu, Tue, Sun

All seven days of the week occur here, so the puzzle seems to be broken.  But if we’re in a country which switched calendars after 1672 but before 1772 – like, say, Great Britain and its colonies, which changed over in 1752 – then the doomsday-Monday calendar won’t have occurred yet but the other six have. (Again from the calendar FAQ), we could also be pretty much anywhere else in Protestant-dominated Europe or colonies thereof.) The answer is 2072.

How dangerous was 2016?

Jason Crease shows that 2016 was, indeed, a year of surprisingly many celebrity deaths. The hard part is defining “celebrity”. There had been a previous BBC analysis based on the number of deaths of people with prewritten obituaries, but that is naturally skewed towards what one particular news organization is useful. Crease’s analysis uses Wikipedia data – both the length of the article and the number of revisions. It turns out that number of revisions of the Wikipedia article is a useful metric than the length of the article – a long article can be long in part because it includes lists of relatively uncontroversial material.

Other analyses include:

  • Snopes, based on lists of notable deaths put out by various media organizations – but of course there’s probably some bias towards keeping the lists roughly the same length as in previous years.
  • Researchers at the MIT media lab, C. Candia-Castro-Vallejos, Cristian Jara-Figueroa, César A. Hidalgo, who concluded that fewer famous people died in 2016 than expected (although not many fewer) Their notion of fame attempts to be more cross-cultural and looks at the number of languages someone has a Wikipedia article in.
    (Via Metafilter.).

It may just be that the Anglo-American axis had a bad year (and of course Brexit and the ascendancy of Donald Trump can’t have helped the mood in (the media in) either of those countries…

But 2017 has a total solar eclipse in the US, so we’ll be okay.

I made it out of clay

Robert Nemiroff and Eva Nemiroff ask: are dreidels fair? Spoiler alert: Betteridge’s law of headlines applies here.

The game traditionally played with the dreidel is unfair, as Ben Blatt showed by simulation and Robert Feinerman showed analytically, but this is assuming that all four sides of the top are equally likely to come up when it is spun. The Nemiroffs took this one step further and checked whether the four sides of the dreidel are equally likely to come up.  They took three dreidels and spun them (800, 1000, and 750 times respectively) and showed that these dreidels were unfair even in this more basic sense.

Interestingly, the patterns seem to tell a story about how the dreidels the Nemiroffs used were flawed. I reproduce their Table 1 here (and yes, they had a dreidel with Christmas imagery on it…)

Driedel ג (gimel)/ Santa נ (nun)/ candy cane ש or פ (shin or pei) / tree ה (he) / snowman total spins
Old wooden 109 302 134 255 800
Cheap plastic 311 243 196 250 1000
Santa 52 275 126 297 750

The letters נ (nun) and ה (he) appear opposite each other, as do ג (gimel) and whichever of ש or פ (shin or pei) is used. So what we see here is that:

  • on the “old wooden” dreidel and the “santa” dreidel, two sides opposite each other are preferred – perhaps the dreidel is slightly wider in one direction than the other
  • on the “cheap plastic” dreidel, one side is preferred and the side opposite it is dis-preferred – perhaps the dreidel is slightly heavier on one side or the handle is slightly off-center.

Presumably dreidels are allowed to be so unfair because nobody is playing dreidel for high stakes, so there’s no real incentive to construct the things properly.

After this year, I can always divide my life into triangles

Today is my 33rd birthday. In honor of that, here are some interesting properties of 33.

One from Wikipedia’s list which I like because I have a soft spot for integer partition problems, is that it’s the largest positive integer that cannot be expressed as a sum of different triangular numbers. The others are 2, 5, 8, 12, and 23: see OEIS A053614. There’s an almost-proof of this fact in this compilation of problems from mathematical olympiad selection tests; that compliation cites this review paper of Erdos and Graham on results in combinatorial number theory, but I can’t find the result there! If I make it to 128, it’s the largest number not the sum of distinct squares.

An idea of the proof is as follows: check by enumeration that 34 through 66 can be written as the sum of distinct triangular numbers, where 66 is not used: 34 = 28 + 6, 35 = 28 + 6 + 1, 36 = 36, 37 = 36 + 1, 38 = 28 + 10, …, 66 = 55 + 10 + 1. Then add 66 to each of these to get a way of expressing 67, 68, …, 132 as a sum of distinct triangular numbers – for example 104 = 66 + 38 = 66 + 28 + 10. Add the largest triangular number less than 132 (this turns out to be 120) to each of those decompositions to write each of 133, …, 252 as such a sum. And so on.

Why is this worth singling out from the list? Many of the others include some arbitrary constant, such as:

  • “the sum of the first four positive factorials”
  • “the smallest odd repdigit that is not a prime number” (a “repdigit” is a number that consists of the same digit repeated, so the constant 10 is hiding here; inf act you could argue this is basically a strange way of stating the identity 33 = 3(10+1))

It’s also pretty cool that 33 is a Blum integer – that is, a product of two distinct primes, each of which is congruent to 3 mod 4. (But it’s not the first Blum integer – that’s 21.)

Another property of 33, which is less negative, is that it’s the first member of the first cluster of three semiprimes (33 = 3 x 11, 34 = 2 x 17, 35 = 5 x 7). That is, it’s the first member of this sequence. In OEIS terms, I’d say that being the first member of a sequence, or the last member of a sequence, is more interesting than being just out in the middle of the sequence somewhere.

The semiprime thing appears to have an arbitrary constant of 3. But there are no clusters of four or more consecutive semiprimes – out of four consecutive integers, one is divisible by 4 – so 33 is the first member of the first cluster of semiprimes of maximal length.

Want to know what’s interesting about some number? You could trawl the OEIS or Wikipedia, or you could go to Erich Friedman’s list, which is a bit more selective, only listing one property of each number. In fact both of my interesting properties of 33 appear here – the semiprime one is, for Friedman, a property of 34, “the smallest number with the property that it and its neighbors have the same number of divisors”.

Time zones and election turnout

Another bit of election analysis: When You Don’t Snooze, You Lose: A Natural Experiment on the Effect of Sleep Deprivation on Voter Turnout and Election Outcomes, working paper by John B. Holbein and Jerome P. Schafer.

People just to the east of a time zone boundary sleep 20 minutes less than those on the west side of the time zone boundary. (This is based on the American Time Use Survey.) This depresses voter turnout, which, in a US setting, moves election results to the right. (Anecdote is not data, but this year I voted early one morning in the week before Election Day – we have early voting in Georgia – because I happened to be awake anyway. So at least in my house waking up early drives turnout.) Rain also drives down voter turnout. Perhaps if you really wanted to you could blame the results in Wisconsin on rain this Election Day… but let’s not go down that rabbit hole.

For an illustration of a similar phenomenon, take a look at the Jawbone circadian rhythm map (by Tyler Nolan and Brian Wilt), which shows that people (well, Jawbone fitness tracker owners) on the eastern side of a time zone boundary go to bed later than those on the western side of the same boundary. Interestingly, they don’t see the effect in total amount of time sleeping, which suggests that in their data set people on the eastern side of a time zone boundary also wake up later.

How to flip an election

Another reason Clinton lost Michigan: Trump was listed first on the ballot, by Josh Pasek, University of Michigan. (Disclaimer: I went to middle and high school with Pasek.) From the blog post: “The best estimate of the effect of being listed first on the ballot in a presidential election is an improvement of the first-listed individual’s vote share of 0.31%.” Trump was listed first on the Michigan ballot, because the governor of Michigan is Republican. This study is based on elections in California, which randomizes the order of the candidates on the ballot by precinct. Here’s a preprint of the paper (Pasek, J., Schneider, D., Krosnick, J. A., Tahk, A., Ophir, E., & Milligan, C. (2014). Prevalence and moderators of the candidate name-order effect evidence from statewide general elections in California. Public Opinion Quarterly, 78(2), 416-439.).

Clinton also would have won if the map of the United States looked slightly different. If you want to play around with this yourself, you can redraw the states using the tool by Kevin Hayes Wilson. Move Camden County, New Jersey into Pennsylvania and Lucas County, Ohio (i. e. roll back the Toledo War, which was a thing) into Michigan, and Clinton wins.  Each of these counties is adjacent to the state it’s being moved into. Here’s the resulting map.

I’m pretty sure that two is the minimal number of counties that have to be moved to get a Clinton win, under the constraint that the counties in each state have to remain geographically contiguous. Clinton starts out needing 37 more EV. and the only way to get that by flipping just one state is to flip Texas; but no state adjacent to Texas went blue.  There is a way to make Clinton win that involves moving one county into another state – namely, move Los Angeles County, California into Texas – but that doesn’t seem to be in the spirit.)

The natural question, then, if we want to know how much “unfairness” is due to the electoral college, is something like this: given the actual voting results, and some “random” partitioning of the US into states, what is the probability of a Trump (or Clinton) win? But what does a “random” partitioning of the US into states even mean?  It seems difficult to define this, given that we don’t have a huge number of alternate histories to run, but I’d imagine we’d want to preserve facts like:

  • some states have many more people than others, but no state is much smaller in population than the average congressional district;
  • more populous states tend to be more urban (this is relevant since the electoral college helps low-population states, and one party is more represented in urban areas);
  • states are geographically relatively compact (unlike, say, Congressional districts in some states)

But in the end this is an academic question, because we don’t get to redraw the states.  (Can you imagine the gerrymandering?)

Dressing goes on salad

Someone needs to make a better stuffing vs. dressing map than this one from Butterball. The problem is that they have a small sample: the fine print reads “This survey was conducted online with a random sample 1,000 men and women in 9 regions – all members of the CyberPulseTM Advisory Panel. Research was conducted in May 2007. The overall sampling error for the survey is +/-3% at the 95% level of confidence.” So the average state has a sample of 20, which would lead to a 21% or so margin of error. This error is enough that the map just looks wrong – Georgia and Mississippi call it stuffing, but Alabama and Tennessee call it dressing?  The Butterball map does seem to capture the regional divide, though, where the South calls it “dressing” and the North calls it “stuffing”.  We’re still fighting the linguistic Civil War in my house.  Obviously this is meant to be entertainment, but get a bigger sample, will you?

It looks like Epicurious has some internal data based on search results that led to their site, but they’re not sharing.

My Google Image Search results for “stuffing vs. dressing” find a bunch of pictures of the ambiguously named bready dish, and also this map of the largest religious denomination in US counties and this article on Josh Katz’s maps of Bert Vaux’s dialect survey. “Stuffing” vs “dressing” is not one of the questions in that survey, sadly.

And yes, I know about the compromise where it’s “stuffing” when it’s cooked in the bird and “dressing” when it’s cooked separately. But in my family of origin we generally have too much to fit in the bird, so some gets cooked in the bird and some doesn’t… does that mean we have “dressing” and “stuffing” on the table at the same time?

Use R, vote D?

David Robinson, data scientist at StackOverflow, tweeted:

Of course this is because of a confounder.  Namely, R comes out of the statistics community, which is concentrated in places with universities, which also tend to be pro-Democratic in the current political environment.   Python, he finds, is also anti-correlated with Trump voting; C# and PHP are correlated with Trump voting, he finds:

Interpret this as you will.  (Seriously, I don’t know enough about who uses C# and PHP to comment anywhere near intelligently.)

The data on language usage by county is not public, but the data on voting is, David Taylor has assembled vote counts by county, and David Robinson has some code for manipulating them and making some plots. Fun fact: the county(-equivalent) with the lowest percentage of Trump voters is the one Trump doesn’t want to move to.

A proof that π < 22/7

Note: this proof has a fatal error.

There’s a reasonably well-known proof that 22/7 > \pi, which can be written in one line:

0 < \int_0^1 {x^4 (1-x)^4 \over 1+x^2} dx = {22 \over 7} - \pi But I’ve always found this one unsatisfying because what does that integral have to do with \pi anyway? As it turns out, \pi enters through the integral \int_0^1 {1 \over (1+x^2)} = \pi/4. But let’s say I’m a purist and think that \pi is about circles. Can I do better? (Of course I can. If I couldn’t I wouldn’t be writing this post.) Start by observing that (21/11)^3 > 7, which can be shown by explicit computation: 11^3 = 1331 and 21^3 / 7 = 21^2 \times 3 = 1323.

Edited to add, November 30: of course I just showed here that (21/11)^3 < 7. This is what happens when you do arithmetic in your head…

Now, the sine function is given by the alternating series sin(x) = x - {x^3 \over 3!} + {x^5 \over 5!} - {x^7 \over 7!} + \cdots and in particular \sin(x) > x - x^3/6 by the alternating series test. Applying this with x = 11/21 gives \sin(11/21) > 11/21 - (11/21)^3/6 > 11/21 - (1/7)/6 = 1/2.

Taking the inverse sine of both sides, 11/21 > \sin^{-1} 1/2.

Finally, we have \pi = 6 \sin^{-1} (1/2). This is a geometric fact that goes back to Euclid’s construction of the hexagon. So \pi < 22/7.

On related notes:

  •  Noam Elkies, Why is π2 so close to 10?
  • Alejandro Morales, Igor Pak, and Greta Panova, Why is π < 2φ?  (This is not a particularly good approximation, but it actually admits a combinatorial proof in terms of Fibonacci and Euler numbers.)

Crossword rundown

Kurt Schlosser at Geekwire: How hard is the New York Times crossword?  This is a description of the Puzzle Difficulty Index that Puzzazz, a puzzle solving app, has been calculating.  Unsurprisingly, if you know anything about that puzzle, later-in-the-week crosswords take longer and are less frequently solved (with the exception that a few more people solve on Thursdays than Wednesdays, which I’d attribute to either noise or the fact that Thursday puzzles tend to have some sort of “gimmick” and are not just halfway between Wednesdays and Fridays).  Both links are worth reading, although there’s some redundancy.  I’ve thought for a while that this sort of thing would be possible if I had enough data.

The next frontier in this sort of analysis would be seeing which individual clues are the hardest – what do people solve immediately and what do they leave until the end, when they have a lot of crossing letters?  I’m not sure if crossword constructors would be interested in this, although anecdotally they seem to be a mathy bunch…

Of course, all of this would be irrelevant if crosswords didn’t exist, and it’s not immediately obvious that enough different strings of letters make words that crosswords should be possible.   In his book Information Theory, Inference, and Learning Algorithms, the late David MacKay analyzed this; here’s the relevant excerpt from that book (three-page PDF) and a more elaborated version of the analysis.  This actually goes back to Shannon’s founding paper although he doesn’t give the detailed analysis.  Shannon writes that:

A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%.

 Here “redundancy” has a specific information-theoretic meaning, and it turns out that the redundancy of English is just around 50%; MacKay’s analysis further shows that crosswords should be harder to construct (i. e. there should be fewer valid ways to fill in a given pattern of black and white squares) as words get longer.
Since I’m talking about crosswords, I’d be remiss if I didn’t point out the famous quote of Tukey:

Doing statistics is like doing crosswords except that one cannot know for sure whether one has found the solution.

Brillinger, in this paper memorializing Tukey, tells us that this quote or something like it came from books of crosswords which he gave to his students as gifts… but from which removed the answers!

And FiveThirtyEight isn’t just election news! Ollie Roeder reported on the American Crossword Puzzle Tournament in 2015.