An 'impossible' card puzzle | Hacker News Reader

An 'impossible' card puzzle

mindyourdecisions.com

91 pointsstrategy28 comments

I really like these kinds of puzzles. I'm not sure if they have a name, but I like to think of them as "invariant puzzles". The key to understanding them is finding an invariant - something that doesn't change when you manipulate the objects in the puzzle.

You can tell it's an invariant puzzle because they seem to be missing one vital piece of information. This is because one of the factors (in this case, whether a card is face up or face down) has been canceled out due to the invariant.

So what's the invariant? Well, let's start with what we're trying to find. We want the number of face up cards in the new deck (let's call it Deck 2) to equal the number of face up cards in the old deck (Deck 1), so Up1 = Up2. We know we can flip cards, so that's equivalent to Up1 = Down2.

But we're still missing a bit of information. How can we add more face down cards to the second deck when we don't know which way they're facing? Here comes the invariant... it doesn't matter! We can make Up1 and Down2 closer to equal by increasing Down2 (by moving a Down card) or decreasing Up1 (by moving an Up card). Essentially, the value of (Down2 - Up1) decreases by 1 when we move a card no matter what.

So we want to keep moving cards until (Down2 - Up1) = 0. (Down2 - Up1) starts at 10 in this case, so we do it 10 times. We flip Deck 2; Up becomes Down, Down becomes Up, and we're left with Up1 = Up2. QED!

Another cool invariant puzzle is the wine mixing problem (also known as the water/wine problem, the red/white marble problem): http://www.smart-kit.com/s330/red-wine-and-white-wine-brain-...

(Oh, and incidentally there are some problems that seem to be missing an important piece of information, but aren't invariant puzzles, like xkcd's Blue Eyes (http://xkcd.com/blue_eyes.html). Puzzles that include language like "everyone behaves rationally" are almost always recursion problems.)

People are way too quick to call logic puzzles "impossible".

Most logic puzzles (maybe all?) have a particular way of thinking about them that will lead you easily to the answer. If the puzzle seems hard, that's probably a sign you need to change how you're thinking about it.

Edit: Looking at it again, there's something else: Every logic puzzle is going to try to slip some important fact by you with vague language. In this case, the hint gives it away: the piles can be different sizes. In general, if I tell you to divide this pack of cards into two decks, I mean they should be equal, and you understand that. The puzzle is using that deliberately to trick you.

It's easy to get around, though; you just have to define the puzzle logically. A "deck", in logical terms, is an unordered set of any number of cards. Once you realize that, the answer seems stupidly obvious.

Well... it depends how do you look at the rules. Saying "You have been asked to reorganize this pack of cards into two decks" is a bit misleading, as "reorganize" typically means moving things around without changing their properties. Sometimes you just assume rules that seem logical to imply.

To one person it might be obvious you can turn the cards upside down, to another it's obvious you can't. Then again... you could just get all cards into a deck, split in half and put each half on a side, so that no cards are facing up, or destroy the cards, or bring your own new deck and hide the cards you find, or take the cards out of the room to reorganize, or turn on the light, or bring a torchlight, or ...

That's true. In the context of a logic puzzle, we're supposed to assume that a card is a logical entity— having two states, face up and face down, belonging exclusively to one deck, etc.

If the puzzle relies on doing things such as tearing a card or turning on the lights that don't really make logical sense, you would usually call it a lateral thinking puzzle instead.

Obviously some people take a lateral approach to logic puzzles like this and declare it "solved", which is a perfect segue into a lengthy discussion on what the criteria for solving such a thing actually are, and who judges that.

I agree, if I met similar problem in real life I'd easily call it impossible. Maybe that's arrogance, but it's good to do these every once in a while to remember that even if something seems "impossible" there still might be a solution. And the solution might be simpler than you think if you can just get rid of the tunnel-thinking.

Also, in real life problem you usually agree that there might be no solution, which makes you give up even quicker. Here I knew (99% sure) that there is solution, but still I managed to miss it.

Typically a good strategy is to solve a simplified version and generalize.

In this case, assume only 1 card is face up. Take a single card from the deck:

   - if it was face up & you flip it, both have zero
   - if it was face down & you flip, both have one

Go through the deck card by card and rip each card in half, stacking one half in one pile and the other half in the second pile. Done :)

This is the anarchist solution ;-)

Nah, that would be to set the deck on fire.

Maybe it's the communist solution? Everyone gets a piece of everything.

The existentialist's solution: throw all the cards in the trash and make two piles of zero.

The theoretical physisist's solution: chuck the cards into a sealed box with a cat and accept that you have both solved and failed the puzzle.

And possibly fed the cat.

The Darwinist solution: the cards will eventually evolve into something that will sort itself

The creationists solution: Let God sort it out

Maybe that's already happened: we're sorting them. Are we sure we're not sorting them for them?

The metaphysical solution: can a card be face up if one can see it?

Face up cards in 42 card deck = N

Face up cards in 10 card deck = 10-N

Face up cards in 10 card deck after flip = 10 - (10-N) = N

N == N, so they are equal

I had to see this myself: http://gist.github.com/592622

Ruby proved it right, but I still don't get it. :-(

To prove the solution works:

Take ten chosen cards from the deck. Call this set of cards C. Number them c1 through c10. Similarly, number the face-up cards f1 through f10, such that if a face-up card was taken, it has the same number in both orderings.

Note that, at the end of arranging the decks, if a card is face-down, it doesn't matter where it is. The only thing we care about is the locations of the face-up cards. So we can ignore all the cards that aren't in the C or F sets, as they're all face-down in the original deck.

Now, for each card cx in the C deck, flip it over. There are two cases: either cx == fx (i.e., the card was originally face-up), or cx != fx.

If cx == fx, you've flipped it face down, and it doesn't contribute to the count of face-up cards for either deck.

If cx != fx, you've flipped it face-up, and fx is in the original deck. So we can increase the count of face-up cards in both decks by one.

So, for each card we've chosen, either that card contributes nothing to the count of face-up cards in either deck, or it contributes one to the count of both decks.

Thank you. Telling me to ignore the face-down cards let me wrap my brain around this one.

This puzzle seemed very simple. "Impossible" puzzles should be a little tougher.

This is pretty old, I've been told it many times in the past... albeit usually as "there are X coins in a dark room".

I think a variation of this was in the one of M. Gartner's books. It was about red and black cards, but the idea was the same, iirc.

How about turning the light on?

Fascinating puzzle, although I agree impossible was a bit strong. I never would have concluded on my own this to be the solution.

What about shuffling the cards REALLY well and then picking 26 in random.

Wrong

I solved this in like a minute. I rule!

Reply on news.ycombinator.com