FiveThirtyEight’s weekly riddler column has started a shorter version to go along with the longer one. The column is here. I’m not going to give the answer I got here in the OP, in hopes that there will be a better discussion. The basics are as follows:

Line up 100 coins heads up, numbered 1 to 100. For every number N, 1 to 100, flip over the coin which is a multiple of N. So, when N=1, all coins are flipped to tails, when N=2, all the even numbers flip back to heads, and so on. At the end of the operation, which coins are tails?

Now, I’m not very good at these sorts of things, so I brute-forced it using an Excel function. Leaving cell A1 blank, I ran the coin numbers down column A and the numbers N along row 1, with the initial state (all heads expressed as 1) in column B with B1=N=0. I then wrote the function =(IF(MOD,$A2,C$1)=0,B2*-1,B2*1). The MOD function takes the coin number, divides it by the value for N, and returns a remainder. If the remainder equals zero, the IF function flips the sign and if the remainder does not equal zero, the IF function keeps the value the same. Copying the function throughout the Excel sheet gave the results for all N.

I figure there has to be a more elegant way to find the answer. This just feels like the classic sort of puzzle that has a simple algorithm that returns the answer, but I have no idea how to do it.

A coin will be tails if it is flipped over an odd number of times. It is flipped over once for each of its factors. Each factor f of x comes paired with a corresponding distinct other factor x/f, except in the case that these two actually coincide (i.e., when x = f[sup]2[/sup]; there will be precisely one such f if x is a perfect square, and none otherwise). Thus, a coin will end up tails if and only if its number is a perfect square.

One could also pose a version of the problem where we don’t flip all the coins whose numbers are divisible by 1 – in which case all of the coins with square numbers would be flipped an even number of times and the rest would be flipped an odd number of times. The result would still be basically the same, just with every coin reversed.