First, Dave Bishop's hat solution can save all but the first guy at the back. Perfect solution. Of course, everyone has to pay close attantion and follow the logic based on what the previous person said to know what color there hat is and whether they actually saw an even or odd number of reds.

@dave bishop - Are you, per chance, a mathematician/statistician?

If anyone actually is a mathematician, try generalizing the hat problem to an infinite number of people. It's a beautiful argument.

When you first choose a door you have a 33.333333333333% chance, when the game show host chooses the other door and says "Are you sure?" He has given you a 66.6666666% chance on the other door and a 33.33333% chance on your first option. Don Corleone is correct, he just didn't explain why

need more riddles!

Don - you can also generalize to any number of colors...and I think you need to require we have countably many explorers - otherwise, ordering in the sums would become important

Allright, here's another:

let n>1. take a square, 2^n x 2^n grid (for example, if n=3 you have a chessboard) and remove one of the squares. we seek to tile the remaining part of the grid, without overlaps, using only tiles which have the following shape:

the tiles should consist of three squares, arranged in an "L-shape" i.e., they have shape (2,1)

is such a tiling always possible? an example does not necessarily prove the result in general - be careful!

And if that one's too hard, try this one on for size:

let n>1. take a square, n x n grid (for example, if n=8 you have a chessboard) and remove two of the corner squares (from opposite corners). we will call a 2x1 rectangle a "domino". is it possible to tile the remaining board, without overlaps, using only "dominoes"?

I still haven't seen the solution to the aircraft riddle. Well, apparently it's 50%, but I haven't seen the explanation.

I also have a hard time believing this answer, while it is most certainly true if n=2, the chances of the last passenger getting his desingated seat must be smaller than 50%. If n=4 for example, if the first 2 passengers manage to choose seats other than th last passenger's designated seat, the 3rd passenger has a 50% chance of taking it. Becase there is also a chance of the 1st or 2nd passenger taking it, the final outcome must be less than 50%.

About the easier chess riddle. It is not possible. Imagine a real chess board. The opposite corners are of the same color, (i.e. both black or both white). Now, with a 2x1 domino, you always cover 2 different colors. Therefore, it is not possible.

About the L-shaped pieces:
Start small with a 2x2 board. It should be obvious that 1 L-shaped piece can be placed on top of it to leave any square open.
Now take a 4x4 board. Divide it into 4 quadrants, on 3 of the quadrants place a 2x2 board with the missing squares towards the middle. Use 1 extra L-piece to fill up the missing squares of these 3 quadrants and fill the 4th quadrant with a 2x2 board missing the appropriate piece.
Now take a 8x8 board. Divide it into 4 quadrants, on 3 of the quadrants ....... etc.

Not scientific proof, but good enough for me. :-)

Ahhh.... new insight into the aircraft riddle. "Every other passenger" can mean 2 things, and will give entirely different answers to the riddle.
If it means "All other passengers" the answer is 50%, if it means the "All odd-numbered passengers" it's a whole new riddle, and it's very complex!

Passenger 1 forgot his seat number. He takes a random seat.

There is a 1/n chance that he will take his proper seat (seat 1), there is a 1/n chance that he will take the last passenger's seat (seat n), and there is a (n-2)/n chance that he'll take someone elses seat (Seat j).

If he takes seat 1, then everyone will find their seats open when they get there, so passenger n will get his own seat.

If he takes seat n, then passenger n will find his seat occupied.

If he takes seat j, passengers 2 through j-1 get their proper seats. Passenger j's seat is occupied, so he has an 1/(n-j+1) chance that he will take seat 1, there is a 1/(n-j+1) chance that he will take seat n, and there is a (n-j-1)/(n-j+1) chance that he'll take someone elses seat (seat k).

If he takes seat 1, then everyone will find their seats open when they get there, so passenger n will get his own seat.

If he takes seat n, then passenger n will find his seat occupied.

If he takes seat k, passengers j+1 through k-1 get their proper seats. Passenger k's seat is occupied, so he has an 1/(n-k+1) chance that he will take seat 1, there is a 1/(n-k+1) chance that he will take seat n, and there is a (n-k-1)/(n-k+1) chance that he'll take someone elses seat (seat k).

If this reasoning is followed inductively, we see that at any point the odds of someone taking seat 1 or seat n (the triggers that end the loop one way or the other) are always equal.

Assuming no one takes them, the loop then will go on until someone (passenger i) takes the seat of passenger n-1.

Then passengers i+1 through n-1 get their proper seats, and n-1 finds his seat taken. However, the only seats available for him now are seats 1 and n, giving him a 50-50 cahnce to take either one.

If he takes seat 1, then passenger n will seat in his seat.

If he takes seat n, then passenger n will not seat in his proper seat.

As you can see, the odds of the loop ending one way or the other are 50%, because at any point, the odds of exiting the loop one way or the other are equal, and there is a chance to continue the loop as if nothing happened, until you reach the end of the line, where the odds are 50-50.

For the case of 4 passengers, we have:

Passenger 1:

1/4 chances to take each seat, so that 1/4 to taking seat 4 (thus ending the possibility for passenger 4 to take it) and 1/4 to take seat 1, thus leaving all the other seats open for their owners (4 gets his seat)

1/4 chances for P1 to take seat 2, so P2 has to take a random seat:

1/3 chances to take seat 1 leaving the other 2 seats open for their owners, giving a combined 1/12 chance that P4 gets his seat.
1/3 chances to take seat 4, giving a combined 1/12 chance that 4 doesn't get his seat.
1/3 chances to take seat 3, so P3 has to choose: 1/2 to take seat 1, giving a combined (1/4*1/3*1/2) 1/24 chance that 4 gets his seat this way, and 1/2 to take seat 4, giving a combined (1/4*1/3*1/2) 1/24 chance that 4 doesn't get his seat.

1/4 chances that P1 takes seat 3, in wich case P2 gets his seat, and P3 has to choose, 1/2 to take seat 1, giving a combined 1/8 chance that 4 gets his seat, and 1/2 to take seat 4, giving a combined 1/8 chance that 4 doesn't get his seat.

If we add them up, the chance that 4 gets his seat is: 1/4+1/12+1/24+1/8 = 1/2

three door quiz show is called the monty hall problem (though monty hall never gave the contestant the choice of changing)

as for the intuition, assume there are n doors, (say n=100) you pick 1 door, it has a 1% chance of being right, the host now opens 98 other doors which contain no prize.

now you have you 1% chance, or a 99% chance (because the other option is picking 99 doors of which only one is still closed) It's not 50/50 at that point.

@Hamish: you said "...the final outcome must be less than 50%." but you didn't take into acount all the possible results.

"If n=4 for example, if the first 2 passengers manage to choose seats other than the last passenger's designated seat, the 3rd passenger has a 50% chance of taking it. Becase there is also a chance of the 1st or 2nd passenger taking it" no, if nobody takes the 3rd passenger's seat he takes it and has a 0% chance of taking the last person's seat.

Too many people not thinking outside the box. The answer is zero.

Passenger 1 arrived late to the airport and missed boarding. He therefore had a zero chance of being seated.

Passenger 2's connecting flight was delayed to weather. She therefore had a zero chance of being seated.

Passengers 3 (a small infant) had a temper tantrum and his mother (Passenger 4) was so frazzled, she decided to take the next flight instead. They therefore had a zero chance of being seated.

Passenger 5 was an obnoxious Greek who was denied boarding because of his foul temper, obscenities, and profanities that the boarding crew labelled him a likely terrorist threat. He was detained at the gate therefore had a zero chance of being seated. He is still being held, without access to legal representation.

Passenger 6 mistakenly signed up for a live game prior to boarding and was trying to get his next set of moves in to avoid NMR/CD status. The door was closed while his orders were being finalized. He therefore had a zero chance of being seated.

The correct answer is therefore zero.

;-)

you are missing entirely the point of these questions. They assume certainties which never exist in real life. Pure maths to test your own logical reasoning and deductive skills.

whereas in reality we need to do probability based error/risk estimates and nobody is thought how. (actually in dip we have to do similar risk estimates, which are more realistic and interesting...)

@orathaic. Not at all. Many folks are making assumptions that are not specified. Try that in a math/logic class and see what marks you get. For example, nearly all of the analyses above assume two key facts never articulated : a) the number of passengers and seats are the same and b) all passengers end up getting seated.

In most cases, failure to state key assumptions makes a response just as wrong as the incorrect conclusion.

For the record, combinatorics was the most interesting class I ever took in university, and the most applied class to real life out of all the 'pure maths'. It can go from describing all of these riddles to what your chances are at winning at a casino for any given game to picking up girls at a bar... really, try it one day and see, life is but a numbers game!

@noob: it is correct that those are assumptions which are being made, they happen to be the correct assumptions and the responders are not being corrected for making mistakes. This kind of assumption is exactly the point i'm making, we make them in real world situations all the time without noticing; However given the style of riddle, it is assumed that we have 100% certainty about some facts. (like it being impossible to communicate with others in the hat-cannibal problem)

@Leo: I kinda agree and disagre, probability and combinatorics should infact be thought as a problem solving skill, (from a young age) rather than a pure maths skill (which it is usually in my experience)

let n>1. take a square, n x n grid (for example, if n=8 you have a chessboard) and remove two of the corner squares (from opposite corners). we will call a 2x1 rectangle a "domino". is it possible to tile the remaining board, without overlaps, using only "dominoes"?

for n odd, nxn is odd, nxn -2 is odd thus it is not possible to tile with dominoes.

for n even, (i'm not good, apparently, at converting this kinda of geometric problem into maths) if you fill the top row with dominoes you get left with a space at the end, take a dominoe and you effectively are taking the corner out of the next row.

Repeating this method, for n = 4 you get to corner holes missing at opposite ends.
for n = 6 you get the same problem. similarily for all n even (you need an odd number of rows to get them to match sides...)

not as comprehensive as Robin.Kleer's answer nor as compact.(but i misread his answer at first)

@Patdragon, is your first 2^Nx2^N problem L shapes of 3 or 4 squares? (a tetroid L 3 in lenght with one block on the end, like a knights move in chess? or a three square shape? i suppose the answer is obvious, you can't fill any 2^Nx2^N with one piece missing = odd number of squares with a 4 block piece... hmm.)

@orathaic. Odd couldn't be done even if the corners were there because the square of every odd number is another odd number. When you subtract two, it is still an odd number. The dominos will always be an even number of squares. Doesn't fit.

To show the problem with the evens, look at a 2x2. You have two non-adjacent squares left. This is because, if you think in checkerboard design, you are taking two squares of the same color out. A domino will always cover one of each color, so you will always have two uncovered squares (identically colored on a checkerboard) as you have two more of one color than the other.

Orthaic, Hamish - props to you guys! And yes, orthaic - we should use 3-square L's for the 2^n square board (else the problem is trivial). And I liked Hamish's solution - and I disagree that it's not "scientific" - it clearly uses induction in a sensible way, even if you didn't state it completely formally (as did Xapi in his airplane solution). More generally, for people like Noob: As for calling for more assumptions or explicitly ruling out linguistic tricks, I leave this to personal taste. If you really think these problems are made more interesting by thinking of them in such a way, then this is probably how you should think of them. Personally, I prefer logic and deduction - in the correct context, all the necessary assumptions should become clear, as well as which ones are cheap cop-outs. Hamish - if you still don't believe the airplane result, read through Xapi's solution - he even follows up with an example to illustrate. Unfortunately, it seems like several people (including Noob - no offense, dude) think that such an example constitutes a proof. For shame!

Allright, enough combinatorics and probability - here's one for the topologists:

I have a painting that I would like to hang on a wall. The painting has a loose string attached to the upper corners of the back side (though you needn't assume that the string is already attached, we will assume that it is). I also have two nails. I would like to hang the painting in such a way, that if either nail is removed, the painting will necessarily fall. Is this possible? How about for 3 nails?

For example, the conventional way to hang such a painting would be to drive the two nails into the wall, and simply loop the string around both. This does not satisfy the criterion demanded above, because if either nail is removed, the painting is still left hanging on the other.

Another example that doesn't work: hang the painting on just one nail, and just have the other nail sticking into the wall anywhere else. Removing the nail the painting is hanging on will certainly make it fall, but removing the other nail will not. Hence, this does not satisfy our requirement of "if EITHER nail is removed, the painting will fall."

Or if you want something more algebraic:

Let t be a real number, and let floor(t) be the greatest integer less than or equal to t, i.e. floor(t) is t, rounded down to the nearest whole number. Define x=floor(t) and y=floor(2t). Write a polynomial in the variables x, y which is identically zero.

let me start on the 2^n x 2^n board problem.
n>1, (2^n x 2^n)-1 tiles, divided into 3-square L's

(2^n x 2^n) = 2^2n
for n = 2, 2^2n-1 = 15 (divisible by 3)
or n = n+1 (2^2n) -1 = 2^(2n +2) - 1 = 2^2n*4 -1 = 2^2n*3 + (2^2n -1) which is divisible by 3 if (2^2n -1) is. Thus all possible boards have a multiple of 3 squares.

one more question, are we allowed to remove any square? (cause in that case i intuit the answer is yes, but i'll have to work on a proof)

Orthaic, you've got a great start - divisibility by 3 is certainly necessary...but not sufficient. Yes, you can remove any square. Hamish's solution by induction is quite elegant...convince yourself it's trivial for n=1, and then just find a crafty inductive step!

Or here's one for anyone, no fancy math required:

I have a perfectly cylindrical can containing some liquid. Devise a test that anyone in a gravitational field can perform, which will determine if the can is more than, less than, or exactly half-full.

"I have a painting that I would like to hang on a wall. The painting has a loose string attached to the upper corners of the back side (though you needn't assume that the string is already attached, we will assume that it is). I also have two nails. I would like to hang the painting in such a way, that if either nail is removed, the painting will necessarily fall. Is this possible? How about for 3 nails? "

For two nails, I'd nail the loose side of the string to the other upper corner of the painting, nail the other nail to the wall, and hang the painting from the now tight string on the nail in the wall. If either nail is taken out, the painting falls.

You know, the usual way :P

For three nails... I'd have to think about that.

"I have a perfectly cylindrical can containing some liquid. Devise a test that anyone in a gravitational field can perform, which will determine if the can is more than, less than, or exactly half-full. "

Put it in the tub, and see how much it floats.