A puzzle is a form of entertainment which presents some sort of problem or mystery which makes you think in order to figure it out. There are many common types of puzzles, including crosswords, jigsaw puzzles, riddles, puzzle games, logic puzzles, tavern puzzles and other kinds of mechanical puzzles. Also, most of recreational mathematics can be thought of as puzzles. A lot of recreational mathematics and logic puzzles fall into the category of old chestnuts.

Some examples of puzzles:

• The Farmer

You're a farmer, and are moving a sheep dog, a chicken, and a bag of feed across a river to your new farm. Being so poor, you can only afford a boat which can carry yourself and one other object. Your animals are very hungry; if you leave the sheep dog and the chicken alone, the dog will eat the chicken. If you leave the chicken and feed alone, the chicken will eat the feed. How do you get all three across safely?

• Dollar to Triangle

What is the fewest number of folds it takes to fold a dollar bill into a triangle?

• The Explorer (more of a riddle)

An explorer walks one mile South, one mile East, and one mile North. He finds himself at the exact same spot. He's lost and hungry, so he shoots a bear he finds. What color is the bear?

• Frogs and Lightbulbs

There's a row of 100 lightbulbs, numbered 1-100, and 100 frogs, also numbered. Whenever a frog jumps on a lightbulb, it toggles the bulb on/off. Frog n will jump on every nth bulb (example, the 4th frog will jump on the 4th, 8th, 12th, 16th, etc. bulbs). When all the frogs are done, which bulbs are on?

• Lightbulbs and Switches

You have 3 switches in the basement, labeled A, B, and C. In the attic are 3 lightswitches, 1, 2, and 3. Each switch corresponds to one lightbulb (ie, A might turn on 3, B = 2, and C =1). You can easily figure out which turns on which with 3 trips to the attic. If you're clever, you can do this in two trips. You, however, want to do it in one trip. Can you?

• The Disfigured Checkerboard

If two opposite corners of the checkerboard are removed, can the checkerboard be covered in dominoes? The dominoes are the size of two adjacent squares, and cannot be laid on top of each other.

• Scrambled Marbles

You have three boxes, each with two marbles. There are 2 marble types: black and white. Each box contains two marbles; one box both white, one both black, and one white and one black. Each box is labeled based on its contents, BB, WB, and WW; someone, though, has come back and changed the labels so that all the boxes are mislabeled. You are allowed to take one marble out of a box at a time, without looking inside. What is the least number of marbles you must remove to figure out which box is which?

• The Security Guard

Part I: You work the nightshift as a security guard, and, while getting ready for work, the power keeps going out. You know that in your sock drawer are 10 white socks and 10 black socks (you're too tired to fold them). How many socks do you need to draw from the drawer to ensure you have a pair of socks?

Part II: New company policy: black socks only! How many socks do you need to draw from the drawer to ensure you have a pair of black socks?

• Election Logic

You have three politicians arguing over the outcome of an election: George, Al, and Ralph. They are all saying different things:

• George says Al didn't win.
• Al says neither himself nor George won the election.
• Ralph says that either George or Al won the election.

If only one is telling the truth, who won the election?

• The Tower and the Glass Balls

You are standing in a tower with n floors, holding 2 glass balls. You want to determine the lowest floor at which a glass ball will break. What is the most efficient way of doing this?

• Hats

Four people are standing in a row facing the same direction, to the right. The person in the back of the line is asked to turn away, to look left. They are all asked to close their eyes while a hat is put on their head randomly. The hats are drawn from a bag of 2 white and 2 black hats. Whenever someone logically deduces what color hat they have on, they get a prize. So they open their eyes ... About a minute passes, and someone says "I know what color my hat is!" Who was it and how did they figure it out?

Answers (I had to figure these out myself; if you can find the answers to those I haven't got, or if you find any errors, please send them to me.

• The Farmer:
• Chicken across
• Nothing back
• Feed across
• Chicken back
• Dog across
• Nothing back
• Chicken across
• Dollar to Triangle: I don't know! Help me out!
• The Explorer: The bear is a polar bear, and therefore white. For the explorer to appear at the same spot, he must be at the North pole.
• Frogs and Lightbulbs: I see no pattern and am lazy! Help!
• Lightbulbs and Switches: You can! Here's how: Turn on one switch and wait 5 minutes or so, then turn it off and flick on another switch. Quickly run upstairs. The lightbulb which is on belongs to the switch you just turned on, the lightbulb which is hot is connected to the switch which you first turned on, and the cold lightbulb is connected to the remaining switch.
• The Disfigured Checkerboard: Well, the corner's of the board which are removed will be of the same color. This means that there will be 32 of one color and 30 of the other. No matter what, after placing 15 dominoes, there will be two remaining squares of the same color. Since no two adjacent squares are the same color, it is impossible to do this. (Thanks to Mr. Ibarra for this answer)
• Scrambled Marbles: Only 1! First, take a marble from the box labeled "BW". This box must be either BB or WW (it is mislabeled), so if the marble is black, the box should be BB; if white, WW. So you switch the signs so that the one box is labeled correctly. Now, one box is labeled with BW and one with WW/BB. The one with WW/BB is mislabeled (it hasn't changed since you started), and it can't be the label of the now correctly labeled box. This means that it has to be BW. So you switch signs again and they are now labeled correctly. Here's an example of how this works:
• You draw a black from the box labeled "BW". This means that this box has 2 black marbles in it
• You switch the signs. Now, they are labeled, WW (wrong), BW (we don't know), and BB (correct).
• The box labeled "WW" can't have 2 white marbles in it; we know it is labeled wrong.
• The box labeled "WW" can't have 2 black marbles in it; we already know which box has 2 black marbles.
• Therefore, the box labeled "WW" must have 1 black marble and 1 white marble. It should be labeled "BW"
• Also, the box labeled "BW" must have 2 white marbles in it.
• You switch the signs and the boxes are all correctly labeled now.
• The Security Guard: 3 and 12. Part I: After 2 socks, it is possible for you to draw one black and one white sock. The third sock gives you a pair. Part II: You could conceivably draw 10 white socks in a row. So the 11th and 12th socks, if this happens, must be black.
• Election Logic: I don't understand this question. Illuminate me!
• The Tower and the Glass Balls: I'm thinking drop a ball at every third floor; if a ball breaks, go down two floors and drop your remaining ball. If it doesn't break, go up one floor and drop it there. This seems silly, though, because the number 3 seems arbitrary. This seems wrong, come up with a better answer and write me!
• Hats: The person second from the front figured it out. How? Because the third person didn't give an answer right away. The only way for the third person to be able to answer right away, the two front hats would have to be the same color (then the third person would know his/hers was the opposite color). Since the third person is silent, then the front two hats must be of opposite colors. Therefore, the second person simply must look at the front person's hat, wait, then say the opposite color. This was tricky, cause it draws you into thinking about that third person who has the most information immediately.

Answers to some of MinderBender's puzzles:
• Frogs and Lightbulbs:
There's an elegant way to figure this out using number theory. The way I actually did it, however, was just to test it out and look for a pattern. I'll list which bulbs are on after each frog hops.
1. 1 2 3 4 5 ... 100
2. 1 3 5 7 9 ... 99
3. 1 5 6 7 10 12 13 17 18 ...
4. 1 4 5 6 7 8 10 13 17 18 ...
5. 1 4 6 7 8 13 15 17 18 ...
6. 1 4 7 8 12 13 15 17 ...
7. 1 4 8 12 13 14 15 17 ...
8. 1 4 12 13 14 15 16 17 ...
9. 1 4 9 12 13 14 15 16 17 18...
Ah ha!
1, 4, and 9 will be on at the end. 2, 3, 5, 6, 7, and 8 will not. You could keep on going; it will probably be even more obvious after you reach 25. The square numbers (and 1) are left on.

The elegant way: Consider a lightbulb k. Which frogs will toggle k? All the frogs whose number is a factor of k. Since every lightbulb starts in the off position, only numbers with an odd number of factors will be on after all frogs have hopped. Which numbers have an odd number of factors? From number theory, only perfect squares have an odd number of factors. Well, and the number 1, of course.

• Election Logic:
This is a standard "enumerate every possibility" puzzle. There are two liars and one truth teller. Try each possible man as the truth teller, and look for a contradiction. Return the first guess that doesn't reach a contradiction.
• Guess 1: George is telling the truth.
George's true statement -> Al didn't win.
Al's false statement -> one of Al or George won.
Ralph's false statement -> neither George nor Al won.
Contradiction: (one of Al or George won) and (neither George nor Al won) can not both be true.

• Guess 2: Al is telling the truth
George false -> Al won.
Al true -> Neither Al nor George won.

• Guess 3: Ralph is telling the truth
George false -> Al won.
Al false -> Al or George won.
Ralph true -> George or Al won.
No contradiction. Ralph must be telling the truth.
Since the third set of events is the correct guess, we determine who won the election from the implications of that guess. Therefore Al won.

• The Tower and the Glass Balls:
A more efficient solution than MinderBender's (I assume efficient means minimizing trips up and down the tower to retreive dropped balls):

Drop a ball every square_root(n) floors until it breaks, and then try every floor sequentially from the next lowest multiple of square_root(n) until the second ball breaks.

Worst case here will be 2*square_root(n) trips up and down the tower, and O(square_root(n)) trips in the average case. MinderBender's solution was n/3 and O(n/3) for the worst case and average case, respectively. This seems pretty elegant, but I haven't proved that it's the most efficient. I've also left out the caveat about having to go up and down the tower only every two times when you still have both balls, but this will just be something like a factor of (2/3) (square_root solution) or (1/2) (3 floors solution), and does not effect the asymptotic behavior.

A puzzle

feel the edges,
corners out
see which way is
up, down

fill in by the hints
the lighting, where
foreground, background

there are faces
spans of green, blue
the last piece
has a distant tree on it

a marvelous image
celebration outdoors
meats cheeses fruits
a child fiddles for dancers

a frame would cost
more than the puzzle did
give it to a niece
time for the next one

Puz"zle (?), n. [For opposal, in the sense of problem. See Oppose, Pose, v.]

1.

Something which perplexes or embarrasses; especially, a toy or a problem contrived for testing ingenuity; also, something exhibiting marvelous skill in making.

2.

The state of being puzzled; perplexity; as, to be in a puzzle.

Puz"zle, v. t. [imp. & p. p. Puzzled (?); p. pr. & vb. n. Puzzling (?).]

1.

To perplex; to confuse; to embarrass; to put to a stand; to nonplus.

A very shrewd disputant in those points is dexterous in puzzling others. Dr. H. More.

He is perpetually puzzled and perplexed amidst his own blunders. Addison.

2.

To make intricate; to entangle.

They disentangle from the puzzled skein. Cowper.

The ways of Heaven are dark and intricate, Puzzled in mazes, and perplexed with error. Addison.

3.

To solve by ingenuity, as a puzzle; -- followed by out; as, to puzzle out a mystery.

Syn. -- To embarrass; perplex; confuse; bewilder; confound. See Embarrass.

Puz"zle, v. i.

1.

To be bewildered, or perplexed.

A puzzling fool, that heeds nothing. L'Estrange.

2.

To work, as at a puzzle; as, to puzzle over a problem.