Proof Problem of the Day - Turn Over the Cards!

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.

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.

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?

Must the $n$ cards be distinct?

@Mursalin Habib Must I use all 2015 moves?