Servants Telling the Truth

[dibsy]

I was asked the following "logic" question yesterday - Any idea if there is a solution?

There are 10 philosophers. Each philosopher has a servant. That servant is either a thief or not a thief. There is at least one thief. Each philosopher knows the state of every other philosopher's servant (but not his own). The philosophers meet 3 times with the intention of finding whether their servant is a thief or not. They say nothing and do nothing and after the 3rd meeting all philosophers know the state of their servants. How many thieves are there?

[BruceZ]

[ QUOTE ]
I was asked the following "logic" question yesterday - Any idea if there is a solution?

There are 10 philosophers. Each philosopher has a servant. That servant is either a thief or not a thief. There is at least one thief. Each philosopher knows the state of every other philosopher's servant (but not his own). The philosophers meet 3 times with the intention of finding whether their servant is a thief or not. They say nothing and do nothing and after the 3rd meeting all philosophers know the state of their servants. How many thieves are there?

[/ QUOTE ]

If there were 1 thief, his master would know that at the first meeting since he would see no other thieves, and he would not attend the 2nd meeting. When they all show up for the 2nd meeting, they know that there must be at least 2 thieves. If there are 2 thieves, their masters would know that at the 2nd meeting since they would each see 1 other thief, and they wouldn't bother to come the 3rd meeting. The other philosophers would come to the 3rd meeting, and then they would know by the absence of 2 philosophers that there were 2 thieves.

Note that if "after the 3rd meeting all philosophers know the state of their servants" is interpreted as "after the 3rd meeting of ALL of the philosophers", then there would be 3 thieves. Otherwise there are 2 thieves.

EDIT: As Megumi as said, my "1st meeting" can be replaced with the initial knowledge that everyone has, and this leads to 3 thieves instead of 2 by the same logic above shifted by 1 meeting.

[MegumiAmano]

Wouldn't it be somewhat important to note in the queston that a philosopher will stop showing up once he knows the state of his own servant?

Or is that just part of the riddle too?

[BruceZ]

[ QUOTE ]
Wouldn't it be somewhat important to note in the queston that a philosopher will stop showing up once he knows the state of his own servant?

Or is that just part of the riddle too?

[/ QUOTE ]

[ QUOTE ]
The philosophers meet 3 times with the intention of finding whether their servant is a thief or not

[/ QUOTE ]

Since this is the purpose of their meeting, they have no reason to attend once they have made this determination. This is also clear from the fact that they all stop attending after 3 meetings. The problem could be worded better so as not to suggest that ALL philosophers attend 3 meetings, since then they wouldn't achieve their objective, unless they do the following:

Another solution would be for the philosophers to kill or imprison the thieves as soon as they are identified. Or simply not bring them to the next meeting. Then all philosophers could attend all 3 meetings, and the objective would be reached by noting the absence of both thieves at the 3rd meeting.

[PairTheBoard]

[ QUOTE ]
Wouldn't it be somewhat important to note in the queston that a philosopher will stop showing up once he knows the state of his own servant?

Or is that just part of the riddle too?

[/ QUOTE ]

I agree. You might deduce it from the reason given for why the philosopers meet. ie. once they know the status of their servant there's no reason to attend another meeting. But imo that's debatable and fuzzes up the thing unnecessarily.

PairTheBoard

[PairTheBoard]

[ QUOTE ]
Note that if "after the 3rd meeting all philosophers know the state of their servants" is interpreted as "after the 3rd meeting of ALL of the philosophers", then there would be 3 thieves. Otherwise there are 2 thieves.

[/ QUOTE ]

I think it's got to be 2 thieves. If all the philosophers met for the 3rd meeting, only the ones with thieving servants would know there are 3 thieves with their servant being one of them. The remaining philosopers would see 3 thieves and wonder if their servant is the 4th. They would have to attend a 4th meeting to know one way or the other.

PairTheBoard

[BruceZ]

[ QUOTE ]
[ QUOTE ]
Note that if "after the 3rd meeting all philosophers know the state of their servants" is interpreted as "after the 3rd meeting of ALL of the philosophers", then there would be 3 thieves. Otherwise there are 2 thieves.

[/ QUOTE ]

I think it's got to be 2 thieves. If all the philosophers met for the 3rd meeting, only the ones with thieving servants would know there are 3 thieves with their servant being one of them. The remaining philosophers would see 3 thieves and wonder if their servant is the 4th. They would have to attend a 4th meeting to know one way or the other.

PairTheBoard

[/ QUOTE ]

That's correct, by the interpretation that ALL would attend 3 meetings, some would have to attend a 4th meeting with some members missing, and that would imply 3 thieves. It is also possible that that each of them attend all 3 meetings and only 3 meetings if they agree not to bring their thieves to the meeting once they are identified. This would have to be stated in the problem also. There are cleaner ways to pose this problem.

[MegumiAmano]

I think you guys might be off by one here. The problem states "Each philosopher knows the state of every other philosopher's servant (but not his own)." It doesn't state that they have to look at each other to learn this knowledge.

So, in the case of only one thief, that philosopher will already know it's his and not bother to show up to the first meeting at all. From there, it follows the same logic you were using, but one meeting earlier.

[dibsy]

Apologize for vagueness, but that's how it was posed to me. I agree with this solution of 2 thieves and their masters not showing up on third meeting.

Will let you know if question poser had different answer in mind.

thanks

[ImBen]

nvm