Waste less time on Facebook — follow Brilliant.
×

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
2 years, 4 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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. Ww Margera · 2 years, 3 months ago

Log in to reply

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? Tan Wee Kean · 2 years, 4 months ago

Log in to reply

@Tan Wee Kean 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. Mursalin Habib · 2 years, 3 months ago

Log in to reply

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. Finn Hulse · 2 years, 4 months ago

Log in to reply

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

A quick question: does your proof work for other numbers, say \(576\)? Mursalin Habib · 2 years, 4 months ago

Log in to reply

@Finn Hulse Wouldn't the 2015 card be changed if we put an extra flip on it? Tan Wee Kean · 2 years, 4 months ago

Log in to reply

@Tan Wee Kean 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. Finn Hulse · 2 years, 4 months ago

Log in to reply

@Finn Hulse @Mursalin Habib Is this right? Finn Hulse · 2 years, 4 months ago

Log in to reply

@Mursalin Habib Must I use all 2015 moves? Tan Wee Kean · 2 years, 4 months ago

Log in to reply

@Tan Wee Kean Yes. Mursalin Habib · 2 years, 4 months ago

Log in to reply

Must the \(n\) cards be distinct? Happy Melodies · 2 years, 4 months ago

Log in to reply

@Happy Melodies 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. Mursalin Habib · 2 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...