Here’s my solution to this week’s Riddler Express question from FiveThirtyEight. Here’s the question: “You place 100 coins heads up in a row and number them by position, with the coin all the way on the left No. 1 and the one on the rightmost edge No. 100. Next, for every number N, from 1 to 100, you flip over every coin whose position is a multiple of N. For example, first you’ll flip over all the coins, because every number is a multiple of 1. Then you’ll flip over all the even-numbered coins, because they’re multiples of 2. Then you’ll flip coins No. 3, 6, 9, 12 … And so on. What do the coins look like when you’re done? Specifically, which coins are heads down?”
I’ve decided to start writing down my solutions to the weekly Riddler questions from FiveThirtyEight. This way, I don’t have to remember where I saved everything on my computer and maybe somebody will find it useful.
As usual with Riddler questions there are multiple ways to solve this that generally fall into either a simulation solution or a math solution. I prefer the simulation solution since my programming background is better than my math background. As usual, I’m doing this in C since that’s what I know best – technically C is a bit faster at these types of things but this exercise is so fast that even the slowest language would solve it before you blink.
There are lots of ways to solve this but I used an array to represent the coins where they start heads up represented by a 0. The outer loops iterates first through every position and the inner loops iterates through all the multiples of the current position to flip that coin. Here’s the code:
#include <stdio.h>;
int main()
{
// declare array of coins and init all to 0
// 0 represents heads up, 1 represents tails up
// The array is one element longer than necessary
// in order to make it easier to understand
int coins[101] = {0};
int pos; // Variable to iterate through position on track
int i; // Variable to iterate through numbers
// Loop through all positions 1 to 100
for(pos = 1; pos<=100; pos++)
{
// For each position flip over all coins that are a multiple
// Start at the current position along track and each
// iteration through add that position to get next multiple
for(i=pos; i<=100; i+=pos)
{
// If the coin is a 0 make it a 1
// If the coin is a 1 make it a 0
if(coins[i] == 0)
coins[i] = 1;
else
coins[i] = 0;
}
}
// Print out the full array
// 0 represents heads up, 1 respresents tails up
for(i=1; i<=100; i++)
{
printf("%3d %d \n", i, coins[i]);
}
// Print out only coins with tails up
for(i=1; i<=100; i++)
{
if(coins[i] == 1)
printf("%3d %d \n", i, coins[i]);
}
return 0;
}
After we run this, the positions where the numbers are heads down are 4, 9, 16, 25, 36, 49, 64, 81, and 100. Hmm, these look familiar! It’s all the perfect squares. If you think about it from a math direction, if all the coins start heads up and you want to know which ones are tails up at the end, it will be the coins that were flipped an odd number of times meaning that a position has an odd number of prime factors. Just so happens that numbers with an odd number of prime factors (from 1 to 100 at least) are perfect squares.
Leave a comment below if you have a question or if you solved it a different way!
The Wandering Engineer 