Life In 19x19

Life in 19x19. Go, Weiqi, Baduk... Thats the life.
https://lifein19x19.com/

Logical puzzles

https://lifein19x19.com/viewtopic.php?t=2434

Page 5 of 8

Re: Logical puzzles

Posted: Thu Dec 02, 2010 11:52 am
by robinz
hyperpape wrote:
entropi wrote:They agree on something such that everyone survives with a probabilty of 99,5%. What is the idea?


Isn't it the case that the probability that they all survive is 50%? The last 99 are guaranteed to survive, the first has even odds. Perhaps you meant that the expected number of surviving villagers is 99.5? Or did I misread something?


Yes, there's only a 50% probability of everyone surviving, but each individual has a 99.5% probability, coming from 50% if they are asked first and 100% otherwise. I think it's one valid way of reading hyperpape's statement.

Re: Logical puzzles

Posted: Thu Dec 02, 2010 1:23 pm
by entropi
hyperpape wrote:
entropi wrote:They agree on something such that everyone survives with a probabilty of 99,5%. What is the idea?


Isn't it the case that the probability that they all survive is 50%? The last 99 are guaranteed to survive, the first has even odds. Perhaps you meant that the expected number of surviving villagers is 99.5? Or did I misread something?


What I meant is that every individual villager has a surviving probability of 99,5%. It is not the probability of 100 villagers surviving. According to the solution, that would be 50 % of course. Sorry for the unclarity in problem statement.

Re: Logical puzzles

Posted: Thu Dec 02, 2010 2:13 pm
by entropi
tj86430 wrote:
Did you calculate the probability of success? I feel it is lower than in my solution, but I'm not sure
It seems not so easy to calculate, unless I am overlooking something obvious. Therefore I chose to be lazy an wait for the answer, if it is correct or similar then calculate ;-)

Your solution makes sense for sure, like in the case of two boxes. But I feel (just feel, no reasoning) that there should be a way of making better use of the information that comes from the fact that the previous prisoners could find their names. But maybe you are right my solution may even be worse than that. :scratch: curious about the answer

Re: Logical puzzles

Posted: Thu Dec 02, 2010 2:44 pm
by hyperpape
@entropi @robinz Of course. Thanks for setting me straight on what it meant.

Re: Logical puzzles

Posted: Thu Dec 02, 2010 5:23 pm
by HermanHiddema
Not really a hint, but a more an additional piece of information, regarding the cruel bandit puzzle:

The right strategy will make their probability of all surviving:

Greater than 30%

Re: Logical puzzles

Posted: Thu Dec 02, 2010 5:35 pm
by lightvector
While we're at it, I'll throw another puzzle on to the queue. Although maybe this one is too technical. It's cute, though, for those who have the math background.

One particularly powerful overlord has amassed a collection of infinitely many prisoners. The prisoners are labeled 1, 2, 3, 4,... going on forever, one prisoner for each positive integer. Tomorrow, the prisoners will all be lined up in numerical order, such that that every prisoner can see every other prisoner. Then, the overlord will place a red or black hat on each prisoner's head. Every prisoner will be able to see the colors of the hats of all prisoners except for his own. All simultaneously, with no further information, every prisoner must then guess his own hat color. If only finitely many prisoners guess incorrectly, all will be freed. Tonight, the prisoners are allowed to confer on a strategy.

Show that there exists a strategy for the prisoners such that no matter what colors of hats the overlord chooses, only finitely many prisoners will guess incorrectly. You may also assume that the prisoners are all capable of making an infinite number of observations of other prisoners' hat colors in order to make their own decision.

And you may assume the axiom of choice.
http://en.wikipedia.org/wiki/Axiom_of_choice

Re: Logical puzzles

Posted: Thu Dec 02, 2010 11:14 pm
by jts
lightvector wrote:One particularly powerful overlord has amassed a collection of infinitely many prisoners.


Didn't we do this one in the math puzzle thread? I'm still not satisfied with the solution offered there, though, so hopefully someone will take another crack at it. :)

Re: Logical puzzles

Posted: Thu Dec 02, 2010 11:27 pm
by lightvector
jts wrote:
lightvector wrote:One particularly powerful overlord has amassed a collection of infinitely many prisoners.


Didn't we do this one in the math puzzle thread? I'm still not satisfied with the solution offered there, though, so hopefully someone will take another crack at it. :)


Oh, wow, I guess they did. Didn't see that thread.

Re: Logical puzzles

Posted: Fri Dec 03, 2010 1:16 am
by Redundant
jts wrote:
lightvector wrote:One particularly powerful overlord has amassed a collection of infinitely many prisoners.


Didn't we do this one in the math puzzle thread? I'm still not satisfied with the solution offered there, though, so hopefully someone will take another crack at it. :)


Don't worry about not being satisfied; the solution is just a hack using the axiom of choice. Choice leads to many rather unsatisfactory results.

Re: Logical puzzles

Posted: Fri Dec 03, 2010 7:12 am
by flOvermind
HermanHiddema wrote:Not really a hint, but a more an additional piece of information, regarding the cruel bandit puzzle:

The right strategy will make their probability of all surviving:

Greater than 30%


I think I can prove that this is not possible (which probably just means that I'm missing something crucial ;)).

First of all, the first prisoner (let's call him A) can't have a better chance than 50%, since there is no information available at the beginning.
Also, since the puzzle is symmetrical with respect to the numbering of the boxes, it doesn't really matter which boxes the first prisoner opens, so we can just assume without loss of generality that he opens the first 50 boxes.

What strategic decisions can the second prisoner (let's call him B) make?
The only information he has available is which boxes prisoner A opened. So when B decides which boxes to open, he can decide to open a number of boxes from 1..50 (let's say N boxes), and the other 50-N boxes from 51..100.

Now let's assume that the name of B is in one of the boxes 1..50. The probability of this happening is 49/99, since we know A is in 1..50 for sure. Under that assumption, the probability that B finds his name is N/50.
Assuming the name of B is in one of the boxes 51..100 (probability 50/99), the probability that B finds his name is (50-N)/50.

Thus, the total probability of B finding his name is:
49/99 * N/50 + 50/99 * (50-N)/50
That simplifies to 50/99 - N/(99*50).

N can be from 0 to 50, so the probability that B succeeds lies between 49/99 and 50/99. Multiply that with the 1/2 probability of A succeeding, and you're already below 30% for every strategy that B can possibly choose, and that's assuming the other 98 prisoners have a perfect strategy available.

Re: Logical puzzles

Posted: Fri Dec 03, 2010 7:33 am
by HermanHiddema
flOvermind wrote:
HermanHiddema wrote:Not really a hint, but a more an additional piece of information, regarding the cruel bandit puzzle:

The right strategy will make their probability of all surviving:

Greater than 30%


I think I can prove that this is not possible (which probably just means that I'm missing something crucial ;)).



This is not an easy puzzle, and I never did solve it. It seemed quite impossible to me. Defeated, I looked at the answer. :oops:

I then verified the answer through a computer simulation, and it is correct. :)

Some hints you may or may not wish to see:
In those cases that the strategy fails the prisoners, it is guaranteed that more than half of them will fail to find their name.

An independent observer, aware of the distribution of the names over the boxes and of the strategy of the prisoners, can predict perfectly which prisoners will fail, and which will succeed.

There is a small but significant chance of ~1%, using this strategy, that all prisoners will fail to find their name.

Re: Logical puzzles

Posted: Fri Dec 03, 2010 8:08 am
by SpongeBob
Since lightvector's puzzle seems to be more of a math puzzle than a logical one, let me provide one more. (Herman's puzzle is too hard for me.)

You like simple looking puzzles that turn out to be nerve-wracking? Those that keep your head real busy and make you feel stupid? Here you go:

The teacher tells his kids: "We are going to write a test next week. On the day before the test, you will not know that you will write the test on the following day."

Now Bill thinks: If only I knew for what day the test has been scheduled. Well, it can't be Friday. As this is the last day of the week, we would know on Thursay that the test will be written the following day. It can't be scheduled for Friday, it must be either Monday, Tuesday, Wednesday or Thursday. Could it be scheduled for Thursday then? Well, then we would know on Wednesday, because we already found out it can't be Friday. So Thursday is out, too. With the same logic, Bill rules out all the other days of the week.

What's going on here? Is there a flaw in Bill's reasoning or does the teacher not tell the truth, or what?

Re: Logical puzzles

Posted: Fri Dec 03, 2010 8:18 am
by HermanHiddema
SpongeBob wrote:The teacher tells his kids: "We are going to write a test next week. On the day before the test, you will not know that you will write the test on the following day."

Now Bill thinks: If only I knew for what day the test has been scheduled. Well, it can't be Friday. As this is the last day of the week, we would know on Thursay that the test will be written the following day. It can't be scheduled for Friday, it must be either Monday, Tuesday, Wednesday or Thursday. Could it be scheduled for Thursday then? Well, then we would know on Wednesday, because we already found out it can't be Friday. So Thursday is out, too. With the same logic, Bill rules out all the other days of the week.

What's going on here? Is there a flaw in Bill's reasoning or does the teacher not tell the truth, or what?


AFAIK, the surprise test paradox is unsolved?

Re: Logical puzzles

Posted: Fri Dec 03, 2010 10:12 am
by flOvermind
SpongeBob wrote:Since lightvector's puzzle seems to be more of a math puzzle than a logical one, let me provide one more. (Herman's puzzle is too hard for me.)

You like simple looking puzzles that turn out to be nerve-wracking? Those that keep your head real busy and make you feel stupid? Here you go:

The teacher tells his kids: "We are going to write a test next week. On the day before the test, you will not know that you will write the test on the following day."

Now Bill thinks: If only I knew for what day the test has been scheduled. Well, it can't be Friday. As this is the last day of the week, we would know on Thursay that the test will be written the following day. It can't be scheduled for Friday, it must be either Monday, Tuesday, Wednesday or Thursday. Could it be scheduled for Thursday then? Well, then we would know on Wednesday, because we already found out it can't be Friday. So Thursday is out, too. With the same logic, Bill rules out all the other days of the week.

What's going on here? Is there a flaw in Bill's reasoning or does the teacher not tell the truth, or what?


After Bill ruled out all days, he assumes that the teacher can't be telling the truth. Next week, there is a test on Tuesday, and Bill is very surprised ;)

Re: Logical puzzles

Posted: Fri Dec 03, 2010 11:14 am
by lightvector
HermanHiddema wrote:
SpongeBob wrote:The teacher tells his kids: "We are going to write a test next week. On the day before the test, you will not know that you will write the test on the following day."

Now Bill thinks: If only I knew for what day the test has been scheduled. Well, it can't be Friday. As this is the last day of the week, we would know on Thursay that the test will be written the following day. It can't be scheduled for Friday, it must be either Monday, Tuesday, Wednesday or Thursday. Could it be scheduled for Thursday then? Well, then we would know on Wednesday, because we already found out it can't be Friday. So Thursday is out, too. With the same logic, Bill rules out all the other days of the week.

What's going on here? Is there a flaw in Bill's reasoning or does the teacher not tell the truth, or what?


AFAIK, the surprise test paradox is unsolved?


I think calling it unsolved is a bit strong. Although the wikipedia page seems to indicate many schools of thought, here is my attempted analysis:

The induction over the days of the week is a red herring. The real issue is a construction sort of like the liar paradox, but predicated on the student's knowledge, so that the paradox only applies for the student and not for the teacher or an outside observer.

This becomes more evident when there is only a single day, rather than a week.

That is, the teacher says
(1) We are going to have a test tomorrow.
(2) But today, you do not/will not know that we will have a test tomorrow.

This boils down to
(1): TeacherTruthful -> Test
(2): TeacherTruthful -> not Knows(Test)

We interpret "Knows" to mean "student can consistently deduce", and from the student's perspective alone, this boils down to the axiom Knows(x) <-> x. Let's say the student can apply this axiom but he cannot in general decide the specific truth value of Knows(x) for arbitrary x because he cannot simulate a copy of himself to determine whether he would ultimately ever be able to deduce x.

What is the poor student able to conclude here? From the student's perspective:

Assume TeacherTruthful. Then, Test and not Knows(Test). By axiom, Knows(Test) <-> Test. Hence, Test and not Test. Contradiction. Therefore, not TeacherTruthful.

Yet, we as outside observers can prove (with some work) that the student, continuing from the assumption "not TeacherTruthful", will never be able to consistently deduce Test. Indeed, intuitively he has no reason to believe so, because he thinks the teacher is lying. Therefore, as outside observers, we know that "not Knows(Test)" is true. Therefore, if the teacher actually decides to have a test, then everything works out. It is consistent (from our outside perspective) that Test and not Knows(Test) and TeacherTruthful, but the student can never know this.

We can in fact simplify further. Consider the statement "This statement is true but you cannot consistently deduce this fact". Indeed, you cannot consistently deduce this fact, because any deduction of truth from you is contradictory. So, it is consistent that the statement is true. But you just can't know it without being inconsistent. It's actually the same thing as Godel's second incompleteness theorem.
All times are UTC-07:00
Page 5 of 8

Powered by phpBB® Forum Software © phpBB Limited