(Puzzles are not ordered by difficulty.)

Three princesses puzzle: You, a prince, travel to a distant land in search of a princess to marry. One day you find a kingdom which is rumored to be home to three beautiful princesses. According to the rumors, the youngest princess always lies and the eldest princess always tells the truth. The middle princess, on the other hand, sometimes lies, sometimes tells the truth, sometimes picks answers at random, and sometimes appears to read your mind in order to give you the answer that will confuse you the most. After a brief discussion with the king, he agrees to let you meet his daughters and asks you to choose which one you plan to marry immediately after the meeting. During the meeting, he will allow you to ask a single princess a single yes/no question. You are willing to marry any princess other than the middle princess, since if you marry her you will never know what she is thinking for the rest of your life. Unfortunately, when you meet the daughters you find that they all look identical, and you have no way to guess at their ages. What question should you ask? (Note: you have no idea how educated these princesses are. Asking a question they are not capable of answering with yes or no, or simply asking a question which is too confusing, is a serious diplomatic faux pas and may result in the loss of your head.)

Robot maze puzzle: each square of an n by n grid of squares is either filled with cement or left empty, such that there is at least one path from the northwest corner to the southeast corner of the grid (outside the grid everything is filled with cement). A robot is currently located at the northwest corner of the grid and wants to get to the southeast corner, but it only knows the value of n and doesn't know the layout of the grid. It also has no method of observing its surroundings, and it is your job to give it instructions to ensure it ends up at its destination. Your instructions should be a finite list of cardinal directions (N, E, S, W) - the robot will try to move in the indicated directions in order, and if there is a cement wall in the way at some step it will simply fail to move in the corresponding direction and continue on with the next instruction in the list. Since the robot has no way of sensing whether it has reached its destination, it might reach the destination somewhere in the middle of your list of instructions and then later leave. The goal is to give a list of instructions, depending only on n, such that after following your instructions the robot is guaranteed to end its journey in the southeast corner of the grid. (From this xkcd thread. This is the "super hard, probably" version.)

Circular prison puzzle: you are a member of a tribe of immortal mathematician-monks who each live alone in the mountains and meditate on the nature of infinity. One day, an evil dictator constructs a circular prison with n rooms, kidnaps you and n-1 other mathematician-monks while you are sleeping, and locks each of you in a separate room of the prison before you wake up. The cells are all identical, have no windows, are arranged in a large ring, and are perfectly square. The only thing in any cell which can be affected is a light switch, but due to poor construction each light switch controls the lightbulb in the next cell counterclockwise in the ring. Additionally, due to budget cuts, power is only provided to the lights for a single instant at midnight. The warden is worried that you will use the lightbulbs to communicate, so every day at noon all of the prisoners are knocked out, have their rooms completely cleaned and the light switches reset to the off position (to save electricity), and the prisoners are all rearranged among the cells however the warden pleases before they wake up. Everything is carefully arranged so that none of the prisoners ever see each other, and of course none of the mathematician-monks have ever met each other prior to your incarceration, and none of you have any idea what n is (not even an upper bound, although you are quite sure it is finite and greater than 0). The warden visits you one day, and challenges you to discover the number n of prisoners in the prison: at any time, a prisoner can guess the number of prisoners, and if correct then all prisoners will be released, while if incorrect, then all prisoners will be executed. You in particular have been singled out to provide a strategy for all of the prisoners - by tomorrow you must write a single message which the warden will make copies of and simultaneously provide to all of the prisoners (and a copy for himself, of course). The warden has a deep hatred of mathematicians, so he will attempt to thwart your strategy, and he has access to both a halting oracle and a truly random number generator. The warden has cameras in every prison cell, and has been watching the prisoners for long enough that he can predict all of their future actions, including any of their attempts to generate random numbers - which will in fact always be merely pseudorandom, as the prisoners have no access to coin flips or other sources of entropy. Additionally, due to their similar backgrounds, any pair of mathematician-monks are liable to come up with identical pseudorandom sequences. What is your strategy message? (From this xkcd thread, with a few extra conditions to eliminate probabilistic solutions.)

A Sherry Gong puzzle: You live in a village which has a severe bedbug infestation. Bedbugs crawl on every surface, and have permanently infested the walls and ceiling (they can tunnel through wood and dirt). They can crawl upside down. At any time, they can choose to fall from whatever they are crawling on down to whatever is below it (so for instance they could drop from a ceiling down to the lip of a bowl filled with water, and then crawl down the side of the bowl). The only thing bedbugs can't crawl through is water. You want to find a way to keep the bedbugs off your bed when you go to sleep, and you are not willing to sleep on a bed which doesn't have a roof over it (or, for that matter, a soaking wet mattress). You also don't have any water pumps, so all the water you use to ward off bedbugs must be standing water. Any water outside your house evaporates during the day. You can ask the village's metalworker to make devices out of metal to help you accomplish this task. Low-budget/realistic solution preferred. How do you do it?

Another xkcd forum puzzle: There are n nails jutting out from a wall (for hanging up pictures). A collection F of subsets of the nails is given with the following properties: the full set of nails is in F, and every superset of a set in F is also in F. Show there is a way to wind a (heavy, frictionless) closed loop of string around the nails such that removing a subset of the nails from the wall causes the string to fall if and only if the subset is in the collection F.

I forget who told me this puzzle: Let X be any set. Can you always find a chain contained in the powerset of X (ordered by inclusion) with cardinality strictly greater than the cardinality of X?

Non-repeating pattern: Is there an infinite word on a three letter alphabet which doesn't contain any two consecutive occurences of the same subword? (For instance, "abab" and "abb" would not be allowed, but "abcabacb" is fine.)

Lion and man puzzle: You find yourself trapped in a disk of radius 1, together with a very hungry, very intelligent lion. You and the lion are both points. You and the lion can run at the exact same speed, never get tired, and can change directions instantaneously. In order to catch and eat you, the lion has to be in the exact same location as you. Will the lion eventually catch you, or can you avoid it forever?

Crazy architect puzzle: One day you awaken to find yourself chained to the center of a tile on an n by n tiled floor. The chain somehow allows you to visit any point in your tile, but not to leave your tile. The other tiles are either empty, or completely filled with infinitely tall square-based columns made out of concrete. Each concrete column is painted a different color. You decide to pass the time by counting the number of distinct colors you can see from the tile you are chained to. Unknown to you, the architect carefully arranged the columns so that you would be able to see as many distinct colors as possible. Asymptotically, how many colors will you be able to see (before starving to death) as a function of n? (Solution here.)

A Zuming Feng puzzle: Alice and Bob are both very interested in the results of a tournament held between 256 contestants. They have spent the past few weeks learning everything about the contestants, their strengths and weaknesses, etc. They don't know what the match-ups are going to be before the tournament begins (it is decided by lottery). Alice manages to get a ticket to watch the tournament, and watches all the way until the final match between the last two contestants, but unfortunately has to leave to go to work before the outcome is decided. While Alice is at work, Bob listens to the radio and hears the name of the final winner of the tournament, but he doesn't know who the runner-up was. Bob wants to tell Alice who the final winner was, but since this puzzle takes place in the future, the only method of communication is text messaging. The text messaging company charges 100 dollars per bit sent in a text message, and refuses to deliver empty messages. Although a text message is usually delivered within a second of being sent, occasionally it is delayed by a minute, sometimes by a day, rarely by a week, and once (according to rumor) by an entire century. If two text messages are sent, it is possible that they will be delivered out of order. Alice and Bob anticipated this situation beforehand, and devised a strategy to let Alice know the identity of the final winner while spending the least possible amount of money between the two of them. What is it?

I heard this one from Bjorn Poonen at the Arizona Winter School: Is there a collection of circles (geometric circles) in three dimensional space such that every point is contained in precisely one of the circles?

A puzzle I heard from Tanya, who heard it from someone else: You are playing a game against the devil involving a sequence of quarters, each one displaying heads or tails. If the leftmost quarter is heads, you get to move, while if the leftmost quarter is tails, the devil gets to move. On either player's move, they pick up the leftmost quarter and put it at the right end of the sequence, choosing only whether to place it with heads or tails displayed. You win if the sequence of coins ever displays all tails, while the devil wins if the game continues forever without ever reaching an all-tails position. What is the winning strategy?

How many automorphisms does the field of p-adic numbers have? (As a warm-up, try the corresponding puzzle for the field of real numbers first.)

As a function of n, what is the longest chain in the lattice of partitions of n, ordered by majorization? (Note: I have never seen a correct solution to this puzzle.)

Can a Turing machine reverse a sequence of n bits in asymptotically fewer than n² steps?

Call a rectangle "good" if at least one of its side lengths is an algebraic number, otherwise call it "bad". Is it possible to tile a bad rectangle with a finite collection of good rectangles?

SRAT: Self-Referential Aptitude Test.

Computer generated puzzles: Simon Tatham's Portable Puzzle Collection. If you are looking for sheer difficulty, I suggest trying the puzzles named "Unequal" and "Towers" on the hardest difficulty settings. "Galaxies" on any difficulty setting is surprisingly fun. I also recommend trying "Loopy" and "Slant" with grid sizes around 40 by 20. Most people seem to find "Untangle" satisfying even though it can be solved algorithmically in linear time.