The 7 face up/down card

Question

Note: This puzzle is a very old puzzle I got from the Internet, however I changed it a bit to be more interesting.

INSTRUCTIONS

You have got 7 blank cards. You are playing with a friend of yours. Your friend lays down those 7 cards in any order each face up or face down, but not all face up or all face down. You can't see in which order your friend lays the cards. You always say the position the card is in (You still can't see the cards) and you friend flips it.

GOAL

Your goal is that either all cards are face up or all cards are face down.

Question

What is the Maximum number of cards you have to flip until you reached your goal and what is the best strategy.

If this is duplicate or a too-maths-question, please report it.

Answer 1

This part of the question is a little bit unclear to me

You always say the position the card is in (You still can't see the cards) and you friend flips it

I understand it as

The game is composed of multiple turns. In each turn you say a number from one to seven and your friend flips the corresponding card. You can never see the position of the cards, but if after a flip the cards are all face down or all face up your friend will tell you and the game is over. Otherwise you have to play another turn and so on.

If this interpretation is correct, this is my answer.

you can do it flipping at most 63 cards in the "worst" possible initial configuration.

Why? First of all consider the configurations of the cards to be binary strings (face down=$0$; face up=$1$).

Decode the configurations

as numbers using the Gray code. The initial position is an unknown number $x$.

The strategy:

Count the turns in your head (let $t$ be the number of the current turn). Pretend that the initial configuration is 0000000 and at each turn ask your friend to flip the card that would make the current configuration encode the number $t$. It is always possible to do this, because any two successive values encoded with Gray code differ in only one bit.

These are the first cards to flip using this strategy:

1,2,1,3,1,2,1,4....

So, if the initial configuration was 0000000 (which is not possible by the rules, but take it just as an example), the configurations in the following turns would be:

0000000 -> 0000001 -> 0000011 -> 0000010 -> 0000011 -> 0000111 -> 0000110 -> 0000100 -> 0000101...

Since the initial configuration is an unknown number $x$ rather than 0000000, the actual configurations are

$x$ -> $x$ XOR 0000001 -> $x$ XOR 0000011 -> $x$ XOR 0000010 -> $x$ XOR 0000011 -> $x$ XOR 0000111 -> $x$ XOR 0000110 -> $x$ XOR $x$ XOR 0000100 -> $x$ XOR 0000101... In other words it's just $x$ XOR $t$.

Eventually you will reach one of the two configurations 0000000 or 1111111, whichever comes first. In particular you will reach 0000000 when

$x$ XOR $t$ is 0000000 i.e. $t = x$ i.e. after $x$ turns

You will reach 1111111 when

$x$ XOR $t$ is 1111111 i.e. $t = \bar{x}$ i.e. after $\bar{x}$ turns, where the bar is the bitwise not.

Now

how big could min($x$,$\bar{x}$) be? It's not difficult to compute. If the first bit of $x$ is one, then $\bar{x}$ is smaller because its first bit is zero. Otherwise $x$ is smaller: in either case the first bit of the smaller sequence is zero, so the number of turns is smaller or equal than $63$. Just remember that all the 7-bit-Gray-encoded numbers that start with zero are smaller than 63 and all the numbers that start with one are bigger than 63.

Answer 2

@melfnt already posted a comprehensive answer using a code. Here's another way to arrive at the same solution with a recursive approach:

Let's build the cases from the ground up. First, we'll solve the same problem with only 1 card. How many flips do we need, at most? The answer is obviously 0, the single card is either face-up or face-down, and we are happy either way.

Then, we'll try to see if we can do the same with more cards. The way to do this is to pick any card as a pivot, and then split the situation into three phases.

1. Apply the N-1 cards solution to the non-pivot card(s).
2. Flip the pivot card
3. Redo the flips from phase 1 in reverse order.

The first phase is guaranteed to visit either a "all face up" or a "all face down" state for the N-1 cards. If we were lucky, the pivot card was already the correct way up, but since we need to be sure, we'll have to assume the pivot was the wrong way up. So, we flip the pivot and redo the first phase, but this time we perform the moves in reverse order! This makes the non-pivot cards go through all the same states as in phase 1, including the same "all cards the same way" state as before, so with our pivot now flipped, we are guaranteed to hit the desired solution state now, if we didn't hit it before.

Then, it's time to calculate the required number of flips.

Since we already know that the 1-card situation takes exactly 0 flips in the worst case, we get that the two-card variation takes 0 + 1 + 0 = 1 flip. This also makes intuitive sense: either the two cards were already the same way up, or they weren't, in which case flipping either card fixes that.

Continuing with the same method, the three-card version takes 1 + 1 + 1 = 3 flips, the 4 card version takes 3 + 1 + 3 = 7, and so on.

Since we don't want to do the tedious addition all the way up to 7 cards (I mean, three more additions? Ain't nobody got the patience for that!), we can notice that adding a card doubles the number of steps needed, and adds one. This also happens to be a formula for generating the next number of form $2^n-1$, assuming you started with a number that was also of that form. Seeing that our 1-card case coincides with $2^0-1 = 0$ then, we get that the general formula for $n$ cards is $2^{n-1}-1$ flips, so we finally get that the solution for 7 cards is

$2^{7-1}-1 = 2^6-1 = \mathbf{63}$ flips.