Looking for hard and rare logic puzzles

[Aro]

Hi everyone,

For a very long time I looked for hard puzzles on the internet. The kind of puzzles I like is actually very difficult to find. I'll explain it : I like puzzles that can be easily explained, that seems impossible to solve a priori and whose answers make you think intelligence or logic is awesome. I'll give you examples of the only four enigmas I know and that satisfy those criterias (each one can be found on this forum ) :

1.

10 peoples are placed in independant boxes at t=0. After a random time interval, a machine take a random people and put him in a room where there is just a switch (nothing else). Then, after a random time interval it put the people back in his box. At the begining the switch is off.
These people must ellaborate a strategy, before beeing put in the boxes, so that it is possible for one of them to say, at any given moment, "now I know that the nine others have been put in the room". Is it possible ?

2.

A monastery is full of monks who have made a vow of silence (there is more than one monk). One day some monks become ill. The only symptom is a blue spot in the forehead so that a monk doesn't know when he is ill but he can see the other ones who are. When a monk know he is ill, he will immediately left the monastery and go to the hospital. The monks can see everyone else once a day during great dinner.
After a year have passed, every sick monk go to the hospital, without having broken their vow of silence. How many monks where ill at the beginning?

3.

100 mathematicians are beeing emprisonned by an evil dictator. One day he imagines a silly game : he puts the mathematicians in a row so that the last one can see the 99 ones that are in front of him, etc. He puts a colored hat on the head of each mathematician. There are three colors : red, yellow and green. And then he says : each one of you, starting from the last one (the one who can see each other) will try to guess the color of his hat. If his guess is right he will be freed if he is wrong he will be executed."
What strategy the mathematicians should choose to save most of them ?

4. (this one requires real bases of mathematics but I still found the result amazing)

500 students are gathered in a room. Their headteacher start speaking : "On the following room there are 500 numbered lockers. Each locker contains the name of a student. After your name is called you will go in this room, and you will open 250 lockers. If anyone of you can’t find his name among those lockers the game stops. You will go back into your room and we will start again tomorrow after I rearranged the names in the lockers randomly. You will be able to go on vacation only when everyone has found his name."
Can the students adopt a method that would probably assure them to be on vacation in a week ?

This topic is adressed to people who already know those puzzles and who can give me links to similar ones. It is not a topic for answering the puzzles I gave.

PS : I read the puzzle about the mathematicians in a circular prison :
http://forums.xkcd.com/viewtopic.php?f=3&t=70558&sid=c7ad9cc397f88009a8dbb4c3cbcb3e08
but, though it is a really nice puzzle, i found the answer way much complex to be explained orally.

[jestingrabbit]

I really like this one.

viewtopic.php?f=3&t=348&p=5098

It works for any number of people, so, for instance, you could simplify it to

Two people are standing face to face, each wearing a hat that is either black or white. They must guess, in secret, what colour hat they are wearing. One of them must get the answer right. What is their strategy?

Spoiler:

One guesses the same colour as the other person is wearing, the other guesses the opposite colour from the other person.

[Goldstein]

Can anyone suggest where I might find a well-written version of puzzle 4 in the original post? I tried searching for it but got a 'locker puzzle' that was just some numbers thing with factors.

[Aro]

I have a very good version in French, because it was an exercise of logic in Ecole Polytechnique that a friend of mine showed to me. I could try to translate it if you want.

[jestingrabbit]

Can anyone suggest where I might find a well-written version of puzzle 4 in the original post? I tried searching for it but got a 'locker puzzle' that was just some numbers thing with factors.

It appears at

viewtopic.php?f=3&t=7164

and has a separate, linked, solution thread.

[Aro]

Here is the link to the french version, with a detailed solution : http://shkdee.info/fichiers/EnigmeCombinatoire.pdf. However I doubt a google translation would have a good result...

Edit : here is my translation. I am not a native english speaker so please excuse my mistakes...

You are part of a group of 500 people, gathered in a big room. Each one is given a different number between 1 and 500 (so there is no couple of people with the same number), let's assume you got the number 37, you are the only to have it. In an other room next to the one where your group is gthered, there are 500 lockers. Each locker contains a number between 1 and 500, written on a piece of sheet, without any duplicate : there are not two lockers that contain the same number. So we have 500 people holding 500 different numbers, and 500 lockers containing 500 different numbers. Alternately, each one of the 500 people from your group will go to the room with the lockers, will open and then close 250 lockers to see the number hidden within it. If he sees in one of these lockers the number that correspond to his, he wins, else he looses. On every case he returns into the first room and is not allowed in any manneer to communicate with the other people from his group (so that entering the room with the lockers noone can have a clue about what locker contains his number). For example let's assume it is your turn to go : you open a first locker , and you find the number 412. It is not your number (remember, your number is 37). You close the locker and open a second one, you find the number 125. This is still wrong so you close it, open a third one, etc, and you repeat this 250 times. If at any moment you have found the number 37 in a closer you won, otherwise you lost.
Let's assume that, during one day, everyone have found the time to open its 250 lockers. Your aim, to your group of 250 people, is that everyone has won during the same day : you need that veryone of the 500 people has open at least one time the locker containing its number, amongst the 250 that he has opened. If this aime is reached, you all win a trip in Australia and the game is over; otherwise everyone has lost and you start over the next day, after having randomly melt the numbers in the lockers during the night (so that, once again, noone know a priori which locker contains its number, even if they have a very good memory).
You were about to despair, realising how impossible this task was, when suddenly one of the people in your group (probably a polytechnician...) says : "If everyone follows my method, we will have won a trip to Australia within a week with 9 out of 10 chances !" What is his method ?

Edit edit :

However let's go back to the topic. Does anyone knows puzzles corresponding to the ones i gave ?

@jestingrabbit : I'm trying to solve the puzzle you gave, I think it is exactly what I was looking for ! (unless the solution is disappointing)

Edit^3 :

@jestingrabbit : OK I found the solution (only because I already knew the solution to the other hat problem) and I confirm : it is exactly the kind of puzzles I was lloking for :p

[LSK]

Here is the link to the french version, with a detailed solution : http://shkdee.info/fichiers/EnigmeCombinatoire.pdf. However I doubt a google translation would have a good result...

Edit : here is my translation. I am not a native english speaker so please excuse my mistakes...

You are part of a group of 500 people, gathered in a big room. Each one is given a different number between 1 and 500 (so there is no couple of people with the same number), let's assume you got the number 37, you are the only to have it. In an other room next to the one where your group is gthered, there are 500 lockers. Each locker contains a number between 1 and 500, written on a piece of sheet, without any duplicate : there are not two lockers that contain the same number. So we have 500 people holding 500 different numbers, and 500 lockers containing 500 different numbers. Alternately, each one of the 500 people from your group will go to the room with the lockers, will open and then close 250 lockers to see the number hidden within it. If he sees in one of these lockers the number that correspond to his, he wins, else he looses. On every case he returns into the first room and is not allowed in any manneer to communicate with the other people from his group (so that entering the room with the lockers noone can have a clue about what locker contains his number). For example let's assume it is your turn to go : you open a first locker , and you find the number 412. It is not your number (remember, your number is 37). You close the locker and open a second one, you find the number 125. This is still wrong so you close it, open a third one, etc, and you repeat this 250 times. If at any moment you have found the number 37 in a closer you won, otherwise you lost.
Let's assume that, during one day, everyone have found the time to open its 250 lockers. Your aim, to your group of 250 people, is that everyone has won during the same day : you need that veryone of the 500 people has open at least one time the locker containing its number, amongst the 250 that he has opened. If this aime is reached, you all win a trip in Australia and the game is over; otherwise everyone has lost and you start over the next day, after having randomly melt the numbers in the lockers during the night (so that, once again, noone know a priori which locker contains its number, even if they have a very good memory).
You were about to despair, realising how impossible this task was, when suddenly one of the people in your group (probably a polytechnician...) says : "If everyone follows my method, we will have won a trip to Australia within a week with 9 out of 10 chances !" What is his method?

This is impossible as written. For the first person, the probability of finding their name regardless of method used is 1/2. That means that no method can guarantee a chance of winning above 50%, which can't approximate the 90% given in the puzzle.

[Qaanol]

Well, there was one that made the xkcd newsblag a while back:

You are presented with two indistinguishable envelopes and allowed to choose one. Each envelope contains a real number, and the numbers are different. You open your envelope and see the number inside. Now you must guess whether the number in the other envelope is greater or less than the number in your envelope. What strategy can you use to have a greater than 50% chance of being right?

And there are a few that invoke the axiom of choice, such as:

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

[Goplat]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Depends on the distribution that you chose f from. There is no strategy here that works for any distribution; if you independently choose f(x) uniformly from [0,1] for each x in ℝ, then my probability of being right will always be 0.

[sfwc]

I rather like this one.

[skullturf]

This is impossible as written. For the first person, the probability of finding their name regardless of method used is 1/2.

Is it?

(Disclaimer: I think I've seen this puzzle before.)

The very first locker you open is effectively like rolling a 500-sided die.

But you're not required to open lockers "blindly". You're not required, at the beginning, to choose a random collection of 250 lockers.

[skeptical scientist]

otherwise everyone has lost and you start over the next day, after having randomly melt the numbers in the lockers during the night (so that, once again, noone know a priori which locker contains its number, even if they have a very good memory).
You were about to despair, realising how impossible this task was, when suddenly one of the people in your group (probably a polytechnician...) says : "If everyone follows my method, we will have won a trip to Australia within a week with 9 out of 10 chances !" What is his method?

This is impossible as written. For the first person, the probability of finding their name regardless of method used is 1/2. That means that no method can guarantee a chance of winning above 50%, which can't approximate the 90% given in the puzzle.

LSK, they get 7 tries, not just 1.

[Nitrodon]

This is impossible as written. For the first person, the probability of finding their name regardless of method used is 1/2.

Is it?

(Disclaimer: I think I've seen this puzzle before.)

The very first locker you open is effectively like rolling a 500-sided die.

But you're not required to open lockers "blindly". You're not required, at the beginning, to choose a random collection of 250 lockers.

This doesn't matter. Every individual still has a 1/2 probability of finding his or her own number. The trick to maximizing the probability of success induces a correlation between the various participants: if anyone fails, then more than half of them will fail. The probability of success with the solution I've heard is approximately 1-ln(2), or 30.7%.

Looking at the puzzle more closely, this is done every day, and the group member quoted a 90% probability of succeeding within a week. The probability of winning at least once in 7 trials is about 92.3%.

[Aro]

@Qaanol : I dont' quite understand your puzzle. How can you elaborate a strategy when you can just say "more" or "less" ? Knowing the axiom of choice is it a necessary condition to find the answer of the other one ?

@swfc : this puzzle seems interesting however I find the description too much complex (it requires basic notions of computer science like transition functions, that makes the puzzle difficult to explain to everyone). I'll try to find the solution.

[Goplat]

@Qaanol : I dont' quite understand your puzzle. How can you elaborate a strategy when you can just say "more" or "less" ?

There are more strategies you could use than just "always say the other number is greater" and "always say the other number is less". (Once you find the most general way to describe a strategy, you've almost solved the problem.)

[Qaanol]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Depends on the distribution that you chose f from. There is no strategy here that works for any distribution; if you independently choose f(x) uniformly from [0,1] for each x in ℝ, then my probability of being right will always be 0.

You have no information about the distribution from which I chose f. The optimal strategy has probability greater than 0 of success.

Knowing the axiom of choice is it a necessary condition to find the answer of the other one ?

Personally I reject the axiom of choice, but I recognize that if one accepts the axiom of choice then the puzzle has a solution. Well, to actually implement the strategy you would need to be able to find an appropriate choice function, not just be satisfied that one exists, but all we need to do is describe the strategy not actually utilize it. I do not actually know if the AoC is necessary to solve this puzzle, but it is sufficient.

[skeptical scientist]

Knowing the axiom of choice is it a necessary condition to find the answer of the other one ?

If you don't know the axiom of choice, you would be very unlikely to come up with the correct answer. To even prove that there is such a strategy, you need something like the axiom of choice. In any case, the intended strategy requires deciding infinitely much information in advance.

The axiom of choice says:
Given a collection of sets {X_i : i in I} indexed by a set I, there is a function f from I to the union of the collection, such that for each i in I, the value f(i) is an element of X_i. Or to put it more colloquially (but less precisely) given a collection of sets, you can simultaneously choose one element from each set.

[mike-l]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Ugh, this hurts my head, but I'm pretty sure the answer is

Spoiler:

1, and in fact I think my solution works to leave out countably many points and guess them all with probability 1... which REALLY hurts my head.

[Qaanol]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Ugh, this hurts my head, but I'm pretty sure the answer is

Spoiler:

1, and in fact I think my solution works to leave out countably many points and guess them all with probability 1... which REALLY hurts my head.

Spoiler:

Only countably many?

[mike-l]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Ugh, this hurts my head, but I'm pretty sure the answer is

Spoiler:

1, and in fact I think my solution works to leave out countably many points and guess them all with probability 1... which REALLY hurts my head.

Spoiler:

Only countably many?

Spoiler:

I'm not sure how to pick a random set of measure 0 in a nice way. I guess I could pick the cantor set shifted/scaled by random factors and do it with uncountably many points as well.

[Qaanol]

Well done.

Spoiler:

Now I’m going to think of a function g:ℝ→ℝ and not give you its value anywhere.

You come up with a bijection h from an uncountable null set K ⊂ ℝ, for instance the Cantor set, to ℝ. You then ask me to extend my function g to a function f:ℝ→ℝ such that for all x in K, f(x) = g(h(x)), and I can define f however I like outside K. I oblige. Maybe I choose values for f uniformly at random from [0, 1] (or perhaps even {0, 1}) for each x outside K. In any case, I then tell you the values of f(x) for all x outside K.

Do you now know g with probability 1?

Edit.

Spoiler:

Wait, your method involves picking a random set? Maybe it’s different from my method. Or did you just mean for the set of points to be omitted, which need not be random?

Edit 2.

Spoiler:

Okay, now I think about it a bit, I’m not sure either. Is it meaningful to ask, “What is the probability of two arbitrary null subsets of ℝ having non-empty intersection?”? Or more accurately, “Given a particular null subset of ℝ, what is the probability of an arbitrary null subset of ℝ having non-empty intersection with the given one?”. I’m not sure there is a uniform distribution over the null sets.

It should work for countable sets though.

[skeptical scientist]

I'm not sure how to pick a random set of measure 0 in a nice way.

Spoiler:

It works for any probability measure on the space of negligible sets such that given a negligible set, the measure of the class of negligible sets intersecting that set is 0.

Now I’m going to think of a function g:ℝ→ℝ and not give you its value anywhere.

You come up with a bijection h from an uncountable null set K ⊂ ℝ, for instance the Cantor set, to ℝ. You then ask me to extend my function g to a function f:ℝ→ℝ such that for all x in K, f(x) = g(h(x)), and I can define f however I like outside K. I oblige. Maybe I choose values for f uniformly at random from [0, 1] (or perhaps even {0, 1}) for each x outside K. In any case, I then tell you the values of f(x) for all x outside K.

Do you now know g with probability 1?

No. You can just pick f so that f(x)=1 for x outside K, regardless of the values on K. Telling me the values of f outside K doesn't do anything.

Edit.

Spoiler:

Wait, your method involves picking a random set? Maybe it’s different from my method. Or did you just mean for the set of points to be omitted, which need not be random?

Your method better also...

Spoiler:

...involve picking a random set. In order to make sure you guess the missing value(s) with probability 1, you need to ensure that with probability 1, each missing value is not in one of the places that the functions disagree, which means you need to choose a random value to be missing. You could pick countably many values to be missing, or even a measure 0 set to be missing, but only if you do it in such a way that you miss the bad places with probability 1.

It's important that c is picked after the function is selected, since if the missing points are known in advance, you can choose your function in such a way that it differs from the member of the equivalence class on the missing points.

[Qaanol]

Your method better also

Spoiler:

involve picking a random set. In order to make sure you guess the missing value(s) with probability 1, you need to ensure that with probability 1, each missing value is not in one of the places that the functions disagree, which means you need to choose a random value to be missing. You could pick countably many values to be missing, or even a measure 0 set to be missing, but only if you do it in such a way that you miss the bad places with probability 1.

It's important that first you pick the function, and then I pick c at random. If you picked the function for a pre-determined c, you could make me be wrong by choosing your function to be different from the value of the representative of the equivalence class at c.

Thanks, I needed that. Or I needed sleep. But we’ll go with “I needed that”.

[Aro]

You are presented with two indistinguishable envelopes and allowed to choose one. Each envelope contains a real number, and the numbers are different. You open your envelope and see the number inside. Now you must guess whether the number in the other envelope is greater or less than the number in your envelope. What strategy can you use to have a greater than 50% chance of being right?

I'm lost here... I've come to some conclusions but I'm still blocked.

Spoiler:

I think that the only "strategy" would be : I will say "more" or "less" after comparing the number I saw with a previously decided number a. The value of a could be easily decided if we knew the probability distribution used to choose the two real numbers, which is not the case...

[Trebla]

Here's a site I've been frequenting for some years. At the very least, your first 3 examples are there in some form or another though I don't recognize the 500 students riddle.

http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml

I would recommend going through the posted riddles (which haven't been updated in years) in at least the easy/medium/hard sections as there are some "easy" riddles that demonstrate some interesting concepts. I wouldn't say you'll find many riddles that meet your standards, but I wouldn't presume to try to narrow the list down for you. With somewhat less frequency, regular members have been able to pose good riddles in the forums, but those will be even harder to find. One of my favorites from this set is the "Gods of Gibberland" which is a simple variation on the Truth/Lie/Random puzzle, but unambiguously solvable.

Your #1 riddle below has over 50 pages of discussion spanning multiple years and various refinements of the methods used to solve (though their version uses 100 prisoners and asks for an optimal solution rather than a "possible" solution) and is one of the most popular riddles on the site.

[Aro]

Thank you for your website Trebla I didn't know it. I'll try to solve the "Gods of Gibberland" puzzle.

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Maybe I lack the necessary mathematic knowledge to solve this one. Whatever, here is my try :

Spoiler:

I think the function that has been chosen will be continuous at the point you chose with a probability of 1 because of a property I don't really know...
It remember me when I was in what we call in France "Classes Préparatoires" and to demonstrate something I tried to define a function that wasn't continuous on any point. I got stuck and my teacher asked me : "Are you even sure it is possible ?" I don't remember if he gave me an answer to this question... So maybe you could enlight me on this point ? How could you define a function "uncontinuous" on an interval of R ? Is it possible ?

Other question, that would simplify the problem, is the set of functions that are continuous almost everywhere on R dense in the set of all functions ? (I may have known the answer to this question but forgot it...)

Edit : Ok actually it is simple to define a function that is "uncontinuous" everywhere, you just have to give a definition for the rationnal number and an other for the irrationnal... Just remembered this...

[Goplat]

You are presented with two indistinguishable envelopes and allowed to choose one. Each envelope contains a real number, and the numbers are different. You open your envelope and see the number inside. Now you must guess whether the number in the other envelope is greater or less than the number in your envelope. What strategy can you use to have a greater than 50% chance of being right?

I'm lost here... I've come to some conclusions but I'm still blocked.

Spoiler:

I think that the only "strategy" would be : I will say "more" or "less" after comparing the number I saw with a previously decided number a. The value of a could be easily decided if we knew the probability distribution used to choose the two real numbers, which is not the case...

Big hint:

Spoiler:

Use a nondeterministic strategy.

[Qaanol]

You are presented with two indistinguishable envelopes and allowed to choose one. Each envelope contains a real number, and the numbers are different. You open your envelope and see the number inside. Now you must guess whether the number in the other envelope is greater or less than the number in your envelope. What strategy can you use to have a greater than 50% chance of being right?

I'm lost here... I've come to some conclusions but I'm still blocked.

Spoiler:

I think that the only "strategy" would be : I will say "more" or "less" after comparing the number I saw with a previously decided number a. The value of a could be easily decided if we knew the probability distribution used to choose the two real numbers, which is not the case...

There are strategies that work even if the person putting the numbers in the envelopes already knows ahead of time what your strategy will be and chooses numbers in a deliberate attempt to foil it.

[skeptical scientist]

There are strategies that work even if the person putting the numbers in the envelopes already knows ahead of time what your strategy will be and chooses numbers in a deliberate attempt to foil it.

Spoiler:

However, if the opponent knows your strategy in advance, he can make your odds of picking the greater number less than 50%+ε, for any positive ε he chooses.

[rhino]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Everyone so far has been somewhat restrained on this, which gave me the pleasure of working it out for myself (an all-too-rare feeling now that my full-time job has nothing to do with maths). I think this is the method you're all hinting at:

Spoiler:

First, partition the set of functions from ℝ to ℝ into equivalence classes, using the relation f₁ ~ f₂ iff f₁ and f₂ differ only on a set of measure zero. Now, using the axiom of choice, choose a representative member of each equivalence class.

Next choose c from a random distribution such that for any specific set S with measure zero, the probability that c is in S is zero (say, the normal distribution).

Then find out what values f takes on points other than c - this pins it into one of your equivalence classes. Find your pre-chosen representative of f's equivalence class (call it F) and assume that f(c) = F(c).

This works with probability 1 because in order to get it wrong, we need c to belong to the measure-zero set where F differs from f - but because of how c was chosen this has probability zero. Ridiculous! The extension to countably many missing points is clear, but I can't immediately think of a way to choose a random uncountable set of measure zero that will almost surely miss any specific set of measure zero. This seems much harder to achieve.

This is probably the funniest bit of maths I've seen in a long time! It's enough to turn me into a constructivist (well, not really). Thanks for posting.

[Qaanol]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Everyone so far has been somewhat restrained on this, which gave me the pleasure of working it out for myself (an all-too-rare feeling now that my full-time job has nothing to do with maths). I think this is the method you're all hinting at:

Spoiler:

First, partition the set of functions from ℝ to ℝ into equivalence classes, using the relation f₁ ~ f₂ iff f₁ and f₂ differ only on a set of measure zero. Now, using the axiom of choice, choose a representative member of each equivalence class.

Next choose c from a random distribution such that for any specific set S with measure zero, the probability that c is in S is zero (say, the normal distribution).

Then find out what values f takes on points other than c - this pins it into one of your equivalence classes. Find your pre-chosen representative of f's equivalence class (call it F) and assume that f(c) = F(c).

This works with probability 1 because in order to get it wrong, we need c to belong to the measure-zero set where F differs from f - but because of how c was chosen this has probability zero. Ridiculous! The extension to countably many missing points is clear, but I can't immediately think of a way to choose a random uncountable set of measure zero that will almost surely miss any specific set of measure zero. This seems much harder to achieve.

This is probably the funniest bit of maths I've seen in a long time! It's enough to turn me into a constructivist (well, not really). Thanks for posting.

Nicely done!

Spoiler:

One could also define the partition as two functions being equivalent if they disagree on at most finitely many points, or on at most countably many points.

Having it as you do, where they disagree on at most a set of measure zero, is the most general and results in the fewest equivalence classes. But making them agree everywhere except a finite set of points makes it abundantly clear what’s going on, and allows people who have never studied measure theory to understand it.

[mfb]

10 peoples are placed in independant boxes at t=0. After a random time interval, a machine take a random people and put him in a room where there is just a switch (nothing else). Then, after a random time interval it put the people back in his box. At the begining the switch is off.
These people must ellaborate a strategy, before beeing put in the boxes, so that it is possible for one of them to say, at any given moment, "now I know that the nine others have been put in the room". Is it possible ?

A while ago, I posted that in another forum - it turned out that for large number of prisoners there are a lot of different strategies to speed that up compared to the conventional solution. To make things even more complicated, you can add a second light switch (or any other number of possible states).

Bad thing that your list is nearly what I collected in the past.
Maybe too easy:

n prisoners get a hat which is black (B) or white (W), they cannot see their own hat. They are not allowed to communicate in any way and get the task to line up in row with separated colors (something like WWWWWBBBBBBBBB). The only action they can do is "get in the line" (or "create the line" for the first). How do they do that?

A door with several locks is guarded by 9 guards. They must be able to open all locks if and only if 5 or more guards (with their own keys) are present. How many locks and keys are necessary?

[notzeb]

This thread reminds me of this.

This puzzle and this one are both classics as well (I like to give the second one along with the challenge of finding a way to trick the devil despite apparently being in a losing position).

[Goplat]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

Everyone so far has been somewhat restrained on this, which gave me the pleasure of working it out for myself (an all-too-rare feeling now that my full-time job has nothing to do with maths). I think this is the method you're all hinting at:

Spoiler:

First, partition the set of functions from ℝ to ℝ into equivalence classes, using the relation f₁ ~ f₂ iff f₁ and f₂ differ only on a set of measure zero. Now, using the axiom of choice, choose a representative member of each equivalence class.

Next choose c from a random distribution such that for any specific set S with measure zero, the probability that c is in S is zero (say, the normal distribution).

Then find out what values f takes on points other than c - this pins it into one of your equivalence classes. Find your pre-chosen representative of f's equivalence class (call it F) and assume that f(c) = F(c).

This works with probability 1 because in order to get it wrong, we need c to belong to the measure-zero set where F differs from f - but because of how c was chosen this has probability zero. Ridiculous! The extension to countably many missing points is clear, but I can't immediately think of a way to choose a random uncountable set of measure zero that will almost surely miss any specific set of measure zero. This seems much harder to achieve.

This is probably the funniest bit of maths I've seen in a long time! It's enough to turn me into a constructivist (well, not really). Thanks for posting.

Nicely done!

Spoiler:

So if the guesser can choose a representative of each equivalence class, he can guess f(c) with p=1 no matter what f is.
But as I said, if his adversary makes f by choosing each f(x) independently and uniformly at random from [0,1] for every x in ℝ, the guesser has insufficient information to determine f(c) with probability > 0. Obviously, these two facts are in contradiction.
Is building f this way just "not allowed"? Why would it be that choosing representatives from each equivalence class without specifying a distribution is OK, but choosing f(x) values with a specific distribution isn't?

[mike-l]

Spoiler:

So if the guesser can choose a representative of each equivalence class, he can guess f(c) with p=1 no matter what f is.
But as I said, if his adversary makes f by choosing each f(x) independently and uniformly at random from [0,1] for every x in ℝ, the guesser has insufficient information to determine f(c) with probability > 0. Obviously, these two facts are in contradiction.
Is building f this way just "not allowed"? Why would it be that choosing representatives from each equivalence class without specifying a distribution is OK, but choosing f(x) values with a specific distribution isn't?

Spoiler:

That only tells us that the value at a random point need not be independent of the other values, even though the value at each point is. AoC is weird, especially when you're doing things like switching the order you do things in (here we're picking uncountably many random numbers, then randomly picking from them, which is different than picking a random point and then randomly picking numbers. I feel like it's akin to the AoC guaranteing immeasurable sets.

[Qaanol]

Spoiler:

So if the guesser can choose a representative of each equivalence class, he can guess f(c) with p=1 no matter what f is.
But as I said, if his adversary makes f by choosing each f(x) independently and uniformly at random from [0,1] for every x in ℝ, the guesser has insufficient information to determine f(c) with probability > 0. Obviously, these two facts are in contradiction.
Is building f this way just "not allowed"? Why would it be that choosing representatives from each equivalence class without specifying a distribution is OK, but choosing f(x) values with a specific distribution isn't?

Spoiler:

Building f that way is certainly allowed.

Remember though, that as soon as I know f almost everywhere, I have a preselected representative function g ready to go that agrees with f almost everywhere. The set of points where f and g are different has measure zero.

Or, to use the other formulation of the solution, let the partition of functions be such that two functions are equivalent iff they disagree at only finitely many points. Now when I know f at all but finitely many points, I have a preselected function g ready to go that agrees with f everywhere except at a finite number of points.

Because I chose the point c from a “nice” distribution, say a Gaussian, the probability that c is among the “bad points” where f and g disagree is 0.

Indeed, even if you know what my representative functions are, as long as you pick f before I pick c, I still guess right with probability 1.

What this amounts to is, you first pick a finite set (or a countable set, or a null set, depending on the formulation of my equivalence relation) of real numbers by whatever means you like, and then I pick a single point from a nice distribution. Now my point, with probability 1, does not lie in your set.

[Superisis]

Well, there was one that made the xkcd newsblag a while back:

You are presented with two indistinguishable envelopes and allowed to choose one. Each envelope contains a real number, and the numbers are different. You open your envelope and see the number inside. Now you must guess whether the number in the other envelope is greater or less than the number in your envelope. What strategy can you use to have a greater than 50% chance of being right?

Spoiler:

Aren't there and equal amount of real numbers above zero as below zero? You have no idea how the numbers are chosen, hence you cannot assume certain numbers are favoured higher than others. Hence an equal (uniform) distribution of all numbers. So if your number is a number below zero then it should be more likely that the other number is greater. If you pick a number above zero then it should be more likely that the number is less. Am I missing something?

[mfb]

Spoiler:

Aren't there and equal amount of real numbers above zero as below zero? You have no idea how the numbers are chosen, hence you cannot assume certain numbers are favoured higher than others. Hence an equal (uniform) distribution of all numbers. So if your number is a number below zero then it should be more likely that the other number is greater. If you pick a number above zero then it should be more likely that the number is less. Am I missing something?

There is no uniform distribution over the real numbers. That does not mean that the puzzle is impossible, it only means that your solution does not work. 0 is not special in any way.
I think we already had a correct solution here in the thread - if not, the blag should link to one somewhere. There is a real solution to this.

[Goplat]

Solution to the envelopes problem:

Spoiler:

Choose a random number from the normal distribution (or any distribution you like that covers the whole (-∞, +∞) interval). If your random number is greater than your envelope's number, say the other envelope's number is also greater; if it's less, say less.

If your random number happened to be between the two envelopes' numbers, then you will be correct no matter which envelope you have; otherwise you will only be correct for one of them. You don't know how probable the "between" case is, since it depends on the distribution the envelope numbers were picked from, but it has to be nonzero, so your probability of being correct will be above 0.5.

[mfb]

Spoiler:

But your probability is just larger than 0.5 on average or if you look at specific numbers. There is a way to get a probability larger than 0.5 for every pair of numbers.