FiveThirtyEight Riddler Express October 14 2016

[asterion]

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.

[Indistinguishable]

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.

[Baffle]

The numbers which end up tails have an odd number of factors. A factor being one of two integers, which when multiplied, give your starting number.

Every number, for example, is a product of one and itself, and so the minimum number of factors is 2.

Since there’s always 2 unique integers being multiplied, there should always be an even number of factors… right?

[spoiler] Unless one of the factorizations is the same number repeated… in which case, it’ll only get flipped once for a factor pair.

[spoiler] Which numbers have a factor pair where both integers are identical?

Perfect squares. The remaining tails will be 1, 4, 9, 16, 25, 36, 49, 63, 81, 100.
[/spoiler][/spoiler]

[Great_Antibob]

Already answered up thread, but from the Ask Dr Math archives: 100 lockers.

[Rysto]

@Indistinguishable

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.

What about prime numbers? Shouldn’t they only be flipped once?

Edit: Oh, I see, in this case we have to consider 1 as part of its factorization.

[bob_2]

Those of you who enjoy this kind of puzzle may like to read this, have a go at the puzzles created by GCHQ, and maybe even buy the book.

I wonder how well the spooks at the NSA will do?

[MikeS]

@Rysto

What about prime numbers? Shouldn’t they only be flipped once?

Edit: Oh, I see, in this case we have to consider 1 as part of its factorization.

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.