# Problem of the Week Problem E and Solution Hundred Deck 3

## Problem

Hundred Deck is a deck consisting of $$100$$ cards numbered from $$1$$ to $$100$$. Each card has the same number printed on both sides. One side of the card is red and the other side of the card is yellow.

Sarai places all of the cards on a table with each card’s red side facing up.
She first flips over every card that has a number on it which is a multiple of $$2$$.
She then flips over every card that has a number on it which is a multiple of $$3$$.
Next, she flips over every card that has a number on it which is a multiple of $$4$$.
Finally, she flips over every card that has a number on it which is a multiple of $$5$$.

After Sarai has finished, how many cards have their red side facing up?

## Solution

If a card is numbered with a multiple of $$2$$, $$3$$, $$4$$, and $$5$$, it will be flipped four times. This card will flip from red facing up to yellow to red to yellow to red again. So the card will have its red side facing up once Sarai has finished.
If a card is numbered with a multiple of exactly three of $$2$$, $$3$$, $$4$$, and $$5$$, it will be flipped three times. This card will flip from red facing up to yellow to red to yellow. So the card will have its yellow side facing up once Sarai has finished.
If a card is numbered with a multiple of exactly two of $$2$$, $$3$$, $$4$$, and $$5$$, then it will be flipped twice. This card will flip from red facing up to yellow to red again. So the card will have its red side facing up once Sarai has finished.
If a card is numbered with a multiple of exactly one of $$2$$, $$3$$, $$4$$, and $$5$$, it will be flipped once. This card will flip from red facing up to yellow. So the card will have its yellow side facing up once Sarai has finished.
If a card is numbered with a multiple of none of $$2$$, $$3$$, $$4$$, and $$5$$, then this card will not be flipped and so the card will still have its red side facing up once Sarai has finished.
To determine how many cards have their red side facing up once Sarai has finished, let’s determine how many cards have their yellow side facing up once Sarai has finished, and then subtract this number from the total number of cards. To determine how many cards have their yellow side facing up once Sarai has finished, we need to determine how many card numbers are multiples of exactly three of $$2$$, $$3$$, $$4$$, and $$5$$ and how many card numbers are multiples of exactly one of $$2$$, $$3$$, $$4$$, and $$5$$.

Let’s consider the cases:

• Case $$1$$: A card number is a multiple of $$2$$, $$3$$, and $$4$$, but not $$5$$.
If a card number is a multiple of $$2$$, $$3$$, and $$4$$, then it must be a multiple of $$12$$, the lowest common multiple of $$2$$, $$3$$, and $$4$$. There are $$8$$ cards with numbers which are multiples of $$12$$. They are the cards numbered $$12$$, $$24$$, $$36$$, $$48$$, $$60$$, $$72$$, $$84$$, and $$96$$. Only one of these numbers is also a multiple of $$5$$, namely $$60$$. Therefore, there are $$8-1 = 7$$ cards with numbers that are multiples of $$2$$, $$3$$, and $$4$$, but not $$5$$.

• Case $$2$$: A card number is a multiple of $$2$$, $$3$$, and $$5$$, but not $$4$$.
If a card number is a multiple of $$2$$, $$3$$, and $$5$$, then it must be a multiple of $$30$$, the lowest common multiple of $$2$$, $$3$$, and $$5$$. There are $$3$$ cards with numbers which are multiples of $$30$$. They are the cards numbered $$30$$, $$60$$, and $$90$$. Only one of these numbers is also a multiple of $$4$$, namely $$60$$. Therefore, there are $$2$$ cards with numbers that are multiples of $$2$$, $$3$$, and $$5$$, but not $$4$$.

• Case $$3$$: A card number is a multiple of $$2, 4$$, and $$5$$, but not $$3$$.
If a card number is a multiple of $$2$$, $$4$$, and $$5$$, then it must be a multiple of $$20$$, the lowest common multiple of $$2$$, $$4$$, and $$5$$. There are $$5$$ cards with numbers which are multiples of $$20$$. They are the cards numbered $$20$$, $$40$$, $$60$$, $$80$$, and $$100$$. Only one of these numbers is also a multiple of $$3$$, namely $$60$$. Therefore, there are $$4$$ cards with numbers that are multiples of $$2$$, $$4$$, and $$5$$, but not $$3$$.

• Case $$4$$: A card number is a multiple of $$3$$, $$4$$, and $$5$$, but not $$2$$.
It is not possible for a card number to be a multiple of $$4$$ but not $$2$$. Therefore, there are no card numbers in this case.

• Case $$5$$: A card number is a multiple of $$2$$, but not $$3$$, $$4$$, or $$5$$.
There are $$50$$ cards with numbers which are multiples of $$2$$, and $$25$$ cards with numbers which are multiples of $$4$$ (and thus $$2$$). So there are $$50 - 25 = 25$$ cards with numbers that are multiples of $$2$$ but not $$4$$. They are the cards numbered

$$2$$, $$6$$, $$10$$, $$14$$, $$18$$, $$22$$, $$26$$, $$30$$, $$34$$, $$38$$, $$42$$, $$46$$, $$50$$, $$54$$, $$58$$, $$62$$, $$66$$, $$70$$, $$74$$, $$78$$, $$82$$, $$86$$, $$90$$, $$94$$, $$98$$

After removing numbers that are still a multiple of $$3$$ or $$5$$, we are left with

$$2$$, $$14$$, $$22$$, $$26$$, $$34$$, $$38$$, $$46$$, $$58$$, $$62$$, $$74$$, $$82$$, $$86$$, $$94$$, $$98$$

So there are $$14$$ cards with numbers that are multiples of $$2$$, but not $$3$$, $$4$$, or $$5$$.

• Case $$6$$: A card number is a multiple of $$3$$, but not $$2, 4$$, or $$5$$.
There are $$33$$ cards with numbers that multiples of $$3$$. They are the cards numbered

$$3,6,9,12,15,…,87,90,93,96,99$$

Of these numbers, $$17$$ are odd. So there are $$17$$ cards with numbers that are multiples of $$3$$ but not $$2$$. They are the cards numbered

$$3$$, $$9$$, $$15$$, $$21$$, $$27$$, $$33$$, $$39$$, $$45$$, $$51$$, $$57$$, $$63$$, $$69$$, $$75$$, $$81$$, $$87$$, $$93$$, $$99$$

None of these numbers are a multiple of $$4$$. After removing the multiples of $$5$$, we are left with

$$3$$, $$9$$, $$21$$, $$27$$, $$33$$, $$39$$, $$51$$, $$57$$, $$63$$, $$69$$, $$81$$, $$87$$, $$93$$, $$99$$

So there are $$14$$ cards with numbers that are multiples of $$3$$, but not $$2, 4$$, or $$5$$.

• Case $$7$$: A card number is a multiple of $$4$$, but not $$2, 3$$, or $$5$$.
It is not possible for a card number to be a multiple of $$4$$ but not $$2$$. Therefore, there are no card numbers in this case.

• Case $$8$$: A card number is a multiple of $$5$$, but not $$2, 3$$, or $$4$$.
There are $$20$$ cards with numbers which are multiples of $$5$$, but half of those are multiples of $$2$$. The card numbers that are multiples of $$5$$ but not $$2$$ are

$$5$$, $$15$$, $$25$$, $$35$$, $$45$$, $$55$$, $$65$$, $$75$$, $$85$$, $$95$$

We still need to remove numbers that are multiples of $$3$$. After doing so we are left with

$$5$$, $$25$$, $$35$$, $$55$$, $$65$$, $$85$$, $$95$$

So there are $$7$$ cards with numbers that are multiples of $$5$$ but not $$2$$, $$3$$, or $$4$$.

Thus, once she has finished, Sarai is left with $$7 + 2 + 4 + 0 + 14 + 14 +0 + 7= 48$$ cards with their yellow side facing up. Therefore, Sarai is left with $$100 - 48 = 52$$ cards with their red side facing up.

Extension:
Suppose Sarai continues flipping cards in this manner. That is, after she has flipped all cards whose number is a multiple of $$5$$, she then flips all cards whose card number is a multiple of $$6$$, then $$7$$, then $$8$$, and so on until she flips all cards whose number is a multiple of $$100$$. Once Sarai has finished, how many cards will have their red side facing up?