Turning Cards

Here is a fun puzzle that I first came across in one of Martin Gardner’s books. It’s a very simple game to teach some elementary number theory.

Place 13 cards of the same suit all face up on a table going from A,2,3…. 10, J, Q, K. Then overturn every other card starting with card 2. After this, overturn every 3rd card starting with card 3. Then overturn every 4th card starting with card 4. Continue this process until you’ve reached the last (thirteenth / King) card. You will notice that the only cards that are face up are the Ace, Four and Nine - these are all square numbers.


The final layout will look like this:



Is it just coincidence that these are all square numbers? Or is there something more to it. I will write a quick R script to explore this a bit more:



The Code

Let’s just use the letter “D” to refer to a card that is face down and the letter “U” to refer to a card that is face up. We need to have 13 spaces to refer to the cards Ace to King. First, we will make 13 cards be face up:

x <- rep("U",13)
x
##  [1] "U" "U" "U" "U" "U" "U" "U" "U" "U" "U" "U" "U" "U"


I decided to do the turning over of every nth element in the following fashion. First, create a turnover function that switches “U” and “D” with each other, and then run that function at every nth element using seq, length and by. There’s no need to assign the new variable as ‘x’ here as the eval.parent bit of the function takes care of that:

turnover <- function (x) { eval.parent(substitute(x <- ifelse(x=="U", "D", "U")))  }
turnover(x[seq(2, length(x), by =2)])
x
##  [1] "U" "D" "U" "D" "U" "D" "U" "D" "U" "D" "U" "D" "U"


If were to then do turn over every 3rd card, we do this:

turnover(x[seq(3, length(x), by =3)])
x
##  [1] "U" "D" "D" "D" "U" "U" "U" "D" "D" "D" "U" "U" "U"


If were to then do turn over every 4th card, we do this:

turnover(x[seq(4, length(x), by =4)])
x
##  [1] "U" "D" "D" "U" "U" "U" "U" "U" "D" "D" "U" "D" "U"


… and so on !.


This grid shows the progression with each step of the procedure:

##    A 2 3 4 5 6 7 8 9 10 J Q K
## 1  U U U U U U U U U  U U U U
## 2  U D U D U D U D U  D U D U
## 3  U D D D U U U D D  D U U U
## 4  U D D U U U U U D  D U D U
## 5  U D D U D U U U D  U U D U
## 6  U D D U D D U U D  U U U U
## 7  U D D U D D D U D  U U U U
## 8  U D D U D D D D D  U U U U
## 9  U D D U D D D D U  U U U U
## 10 U D D U D D D D U  D U U U
## 11 U D D U D D D D U  D D U U
## 12 U D D U D D D D U  D D D U
## 13 U D D U D D D D U  D D D D



Is this just chance?

What if we had a row of 100 cards face up at the beginning? Which ones would be left if we turned over every 2nd, then every 3rd, then every 4th…… all the way to every 99th, every 100th card.

We can check this by putting the turnover function into a loop like this:

X <- rep("D",100)
for(i in 1:100) {turnover(X[seq(i, length(X), by = i)])  }

X
##   [1] "U" "D" "D" "U" "D" "D" "D" "D" "U" "D" "D" "D" "D" "D" "D" "U" "D"
##  [18] "D" "D" "D" "D" "D" "D" "D" "U" "D" "D" "D" "D" "D" "D" "D" "D" "D"
##  [35] "D" "U" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "U" "D" "D"
##  [52] "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "U" "D" "D" "D" "D"
##  [69] "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "U" "D" "D" "D" "D"
##  [86] "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "D" "U"
which(X=="U")
##  [1]   1   4   9  16  25  36  49  64  81 100


These are all of the square numbers again … this seems pretty unlikely that this is just due to chance!



The proof

So why does this occur? Why is it only numbers that are square numbers that remain face up at the end of the procedure?

It’s actually pretty straightforward and has to do with the divisors of each number. All numbers have an even number of divisors (or factors) other than square numbers that have an odd number of divisors/factors.

We can look at this programatically. Here is a function to calculate the number of divisors of a number. It examines every number from 1 to the number itself and tests for each whether there is a remainder when the number is divided by it. If the remainder is equal to zero, then that number is a divisor.

divisors <- function(x){ seq_len(x)[x%%seq_len(x) == 0 ]} #for all of 1 to number, find those divisors that leave a remainder of 0

divisors(81)
## [1]  1  3  9 27 81
divisors(82)
## [1]  1  2 41 82
divisors(83)
## [1]  1 83


Most divisors are in pairs, the first pair of divisors of any positive integer are 1 and the number itself, then e.g. 2 and 41 for number 82 and so on. The only numbers that have an extra divisor are squares, whereby one divisor is multiplied by itself e.g. 9*9 =81 but 9 only counts once as a divisor.

Let’s look at the positive integers 1 to 26, to see how many divisors each number has:

num_divisors <- unlist(lapply(lapply(1:26, divisors), length))
names(num_divisors)<-1:26
num_divisors
##  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
##  1  2  2  3  2  4  2  4  3  4  2  6  2  4  4  5  2  6  2  6  4  4  2  8  3 
## 26 
##  4


The only numbers with odd divisors are square numbers - 1, 5, 16, 25 …


So basically, the number of times that each card gets turned when faced down is equal to the number of divisors that it has. A card such as the number 10 has divisors 1, 2, 5, 10 and so it will be turned four times - when all cards are put down and turned over to start, when each 2nd card, each fifth card and each 10th card are turned over. The only cards that are turned an odd number of times are the square numbers! That is why they are always left upturned at the end.



If you have any feedback please get in touch. Probably the fastest way is to go to my twitter page.