# Proof Problem of the Day - Turn Over the Cards!

There are $$2015$$ cards lying on a table. Some of them are face-up while the others are face-down. A move consists of turning over some of the cards. However, you are allowed to flip exactly $$n$$ cards in the $$n$$-th move.

Prove that it is possible to turn over the cards in such a way that after the $$2015$$th move, all the cards are either face-up or face-down.

Click here to see all the problems posted so far. Keep checking everyday!

Note by Mursalin Habib
3 years, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

For 1 card, it is obviously possible to do this - just flip over the card you already have. Suppose this is possible for 2k-1 cards. I will show it is possible for 2k+1 cards. Two cases:

Case 1: All are facing the same way to start with. Place all 2k+1 cards in a line, numbered from 1 to 2k+1 from left to right. At the ith move, if i is no more than k, then flip over the first i cards. Else flip over the last i cards. The last move flips all cards. The other moves are essentially 'paired up': for i <= k, the ith move flips the first i cards while the (2k+1-i)th move flips over the other (2k+1-i) cards. So the combined effect of the two moves is to flip over all the cards. In this way, in effect, all the cards are flipped over k+1 times. Since they were facing the same way to start with, they are also facing the same way at the end.

Case 2: There exists at least one face up card and one face down card. Inductively, we can use moves numbered 1 to 2k-1 to make the remaining 2k-1 cards face the same way. Without loss of generality, assume this is face up. At the penultimate step, flip all these plus the other card which was already face up to begin with. Now all cards are facing down and the last move as usual has no effect on this property of facing the same way.

- 3 years, 9 months ago

We establish two states: state 1 and state 0 that a card can have with state 0 being the opposite of state 1. (i.e. if state 1 is face up, then state 0 is face down.) Thus we note that $$\left\{ 0,0,0,1 \right\} ,\left\{ 1,1,1,0 \right\}$$ are similar sets of cards.

We prove that if it is possible to flip the n cards in n moves, then we are flip (n+4) cards in (n+4) moves. To prove that 2015 works, we have to prove the base case of n=3.

Assume n= 4k+3 works. Then we show that n=4k+7 works.

First divide 4k+7 cards into two groups: $${ S }_{ 1 },{S }_{ 2 }$$, with $${ S }_{ 1 }$$ containing 4k+3 cards while $${ S }_{ 2}$$ contains 4 cards.

We try to obtain $${ S }_{ 2}$$ such that the cards are of the state: $$\left\{ 1,1,1,0 \right\}$$.

Case 1: We cannot find such $${ S }_{ 2}$$. This can only mean that the set is of the form: $$\left\{ 1,1,1...,1 \right\}$$ Then. we can prove that this set of cards can be changed in to the form: $$\left\{ 1,1,1...,1 \right\}$$.

Use the 1st move to flip the first card, the 2nd move to flip the first two cards, and so on until we use the (2k+3)th move to flip the first 2k+3 cards.

Then use the (2k+4)th move to turn the remaining 2k+4 cards which have not been flipped. Use the (2k+5)th move to turn the same (2k+4) cards and the (2k+3)th card. Use the (2k+6)th move to turn the same (2k+4) cards and the (2k+3)th and the (2k+2)th card and so on...

Then each card will be flipped (2k+4) times and be in the same state as they originally were. (i.e.$$\left\{ 1,1,1...,1 \right\}$$ ).

Case 2: We manage to find such $${ S }_{ 2}$$. Since n=4k+3 works, we are able to turn the entire group of cards in 4k+2 moves into the form:

(A) $$\left\{ 0,...,0|0,1,1,1 \right\}$$ or

(B)$$\left\{ 1,...,1|0,1,1,1 \right\}$$

That's all I got for now. Am I on the right track?

- 3 years, 10 months ago

I'm really not sure. I tried reading your comment but I kept zoning out.

There is actually a much cleaner way to do this. In fact if the statement holds for $$k$$, it holds for $$k+2$$. This is not that hard to show. The actual challenge of the problem is finding a way to do this if all the cards are facing the same way.

- 3 years, 9 months ago

The maximum number of non-repetetive moves that would be satisfactory would be $$\lfloor 2015/2 \rfloor=1007$$.

The average number of flips for each card after 2015 moves is $$1+2+3+\dots+2015=\dfrac{(2015)(2016)}{2}=1008$$.

We can start with the base case where you flip each and every card 1008 times, of course ending up with the same thing as we started with. But we can redistribute certain flips. For example, I can skip flipping card number 2014 and instead put an extra flip on card 2015. This will of course change the 2014th card but leave the 2015th card unchanged. In this manner, we can tweak every single card to be exactly what we want it to be. And, it will take $$\leq 1007$$ redistributions (as we showed earlier) which will always be less than 1008. Hence proved.

- 3 years, 10 months ago

It seems a little hand-wavy to me to be honest.

A quick question: does your proof work for other numbers, say $$576$$?

- 3 years, 10 months ago

Wouldn't the 2015 card be changed if we put an extra flip on it?

- 3 years, 10 months ago

No, because I'm saying an additional flip. Since it already is going to get 1 flip, I'm simply adding 1. $$1+1=2 \equiv 0 \mod{2}$$ so the card remains unchanged. Sorry if the wording was confusing.

- 3 years, 10 months ago

@Mursalin Habib Is this right?

- 3 years, 10 months ago

@Mursalin Habib Must I use all 2015 moves?

- 3 years, 10 months ago

Yes.

- 3 years, 10 months ago

Must the $$n$$ cards be distinct?

- 3 years, 10 months ago

I am not sure what you mean.

The cards don't have to be playing cards. Any card that has a well defined face-up and face-down state will work.

During the second move, you have to turn over two cards. You can't turn the same card over twice.

- 3 years, 10 months ago