What was the best Puzzle/Brainteaser you've ever been asked at an interview? And Why?

There have been many questions related to what one should ask interviewees, what you should ask a company you're interviewing at, etc. I searched and I don't think this one is a duplicate. Also, community wiki from the start.

So here goes: **What is the most interesting (challenging, fun, original, useful) brainteaser or puzzle question you've been asked at an interview and why?

For me, it was this one that I was asked recently (I found a similar one online and copy-pasted it here to avoid retyping the whole thing):

> There are ten gnomes. They are in the
> dungeon. Their captor has given the
> gnomes a chance of survival. Here is
> the offer:
> 
> He lines the gnomes up in a
> single-file row. This means that the
> tenth gnome sees the back of the
> person in front of him, and there is
> no gnome behind the tenth gnome. The
> ninth gnome has the tenth gnome behind
> him and the eighth gnome directly in
> front of him, and so on. Finally, the
> first gnome has the second gnome
> directly behind him, but there is no
> one in front of the first gnome.
> 
> The captor has a bag full of many
> black hats and many white hats. There
> is not necessarily the same number of
> black hats as white hats. (important)
> He randomly reaches into his bag and
> places a hat on each of the gnomes.
> This means that the tenth gnome can
> see everyone's hat except his own, the
> ninth gnome can see everyone's hat
> except his own and the tenth gnome's
> hat, and so on. The first gnome can
> see no one's hat.
> 
> The captor then takes out his gun and
> puts it to the temple of the tenth
> gnome. He asks the gnome, "What color
> is your hat?" If the gnome answers
> correctly, he lives and gets freed
> from the dungeon. If he does not, he
> dies. He continues up the line in this
> progression.
> 
> However, before placing the hats on
> the gnomes, he allows the gnomes to
> meet as a group and discuss a strategy
> to save as many of the gnomes as
> possible. How many gnomes can you
> guarantee to save, and with what
> strategy?
> 
> REMEMBER: When it is your turn to say
> the color of your hat you must ONLY
> say "white" or "black." If you say
> anything else, the king will shoot you
> and all of the remaining gnomes.


Once I figured out the solution to this one, the interviewer then posed another question:
what