bushindo

Some comment

Suppose that there are 16 people standing in a straight line in a room. Each person is either a truth teller (always tell the truth) or a naysayer (always answer NO). You are in a different room, and your task is to determine the positions of all the truth teller in this line. You can not see the 16 people, as they are in the other room. You are allowed to take 'turn' to determine their persona. During each turn, you can address 1 single YES/NO question to ALL 16 people. The question will be relayed to the 16 people, and the total number of YES will be relayed back to you. Assume that number of YES relayed back to you at the end of each turn is reliable. As usual, you are not allowed to ask questions that are impossible for the truth tellers to answer accurately with YES/NO (asking paradoxes, etc.) . Show that it is possible to correctly identify all the truth tellers and the naysayers within 6 questions.

Good work, k-man and araver. As usual, araver contributed beyond the requirement of the OP and taught me something new. I have another puzzle up that you both probably will enjoy.

Suppose that you are in a room with 16 light switches, which are arranged in a line on the wall. Each light switch is connected to a unique lightbulb in another room. However, some of the 16 lightbulbs are burned out, which means that the 16 light switches you see consist of functional and non-functional switches. The light switches are currently all set in the OFF positions. It is also known that the 16 switches are arranged in such a manner that within any 7 consecutive light switches, there are an odd number of functional switches. Assume that setting a functional switch to the ON position will turn on the corresponding lightbulbs, and similarly setting it to OFF will turn off the bulb. Turning any switch connected to a burned-out bulb to ON, of course, will have no effect on the bulb. You are allowed to take 'turns' to deduce the position of the functional switches. During a turn, you can set the 16 light switches to any ON/OFF configuration you wish, and someone from the room with the lightbulbs will tell you how many lightbulbs are on. Determine a strategy that is guaranteed to identify all the functional light switches using only 5 turns.

And, it follows trivially Nice work! Once again you made a nice contribution to this topic. Thanks!

Thank you for the puzzle. I liked the cycle-3 alternator very much. Made it different from any other problem I've seen so far. I pondered for a little while if you can narrow down the alternator too at the same time. Probably not, but still pondering. Thanks for working on the puzzle. This answer is entirely satisfactory and I'd consider the OP solved. The note you made at the end made me ponder about it a bit too, Araver's post notes that we could phrase the question in such a way that liars and truth tellers will give us the same answer. That should remove the difficulty you mentioned above.

Suppose that you encounter 4 people, each of whom is either a truth teller (always tells the truth), a liar (always tell lies), a random answerer (always answer randomly with 'Yes' or 'No'), or an alternator. The alternator, upon being asked the first question, will randomly choose to be a truth teller, a liar, or a random answerer and then answer the question with that persona. Every time the alternator is asked a question thereafter, he'll switch his current persona in the following cycle: truthteller -> liar -> random answerer -> truth teller ..., etc. For instance, if the alternator acted as a truth teller for a particular question, he will act as a liar when he is asked the next question, and as a random answerer the question after that. You know that in this group of 4, there are 1 random answerer, 1 truth teller, 1 liar, and 1 alternator, but you don't know which person is which. The puzzle is to identify the 1 random answerer with the following information: 1) You can only ask yes/no questions to 1 person at a time 2) You can ask the same question of different people, or address different questions to the same person. 3) You can not ask any question which is impossible for a truth teller/liar to answer with a yes/no (ie. asking a truth teller what a random answerer would say to a particular question, asking paradoxes, etc. ) 4) Each person in the group of 4 knows what type of people the remaining 3 are. Determine a strategy that is guaranteed to find the 1 random answerer in 8 questions or less.

That's an interesting issue you bring up, I'll have to think about it some. I'm glad you like the puzzle. I greatly enjoy your insights on this puzzle. I have another one that is similar to this but with a twist. However, I'm going on vacation tomorrow and I probably won't be able check this board for the next few days, so I'll post the puzzle next week.

Step 2 - Final adaptive questions (at most 3) -------------------------------------------- All but one case in the table have at least 1 sure position and at least 1 truth-teller among these positions. Target that one known truthteller (let's call him Oracle) with the rest of the questions. First, let's eliminate most of the cases. If there are 3 or more sure positions, then at most 4 unknowns remain. Therefore 3 questions targeted at the Oracle about 3 unknown positions give a total of 6 sure positions and the last can be deduced by whatever type (R or T) is missing from the (3R, 4T) distribution. If there are 2 sure positions, then it's one of the following 7 cases: 20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-. 25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT. 27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----. 41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT. 45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT. 57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT. 61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT. For each case, 3 well-targeted questions clear the rest of the arrangement. If there is only 1 sure position, then it's one of the following 10 cases: 9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T. 21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T. 23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T. 29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T. 37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T. 43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T. 47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T. 53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T. 59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T. 63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T. For each case, 3 well-targeted questions clear the rest of the arrangement. At last, the infamous branch with 0 sure positions. 19) NYNNYN- 5 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT, TTRRRTT. 0 sure position: -------. 3 more questions and we're done: Ask the last (7th) in the line if the first one is random. If Yes - TTRTTRR, RTRTTRT, RRTTTRT. Now the mask is ---TTR-. Ask an Oracle if the last is R (one case). If not, ask if second is R (one case for each answer). If No - TTRTTRR, TTRRTRT, TTRRRTT. Now the mask is TTR----. Ask an Oracle if the last is R (one case). If not, ask if the sixth is R (one case for each answer). Excellent strategy! I didn't realize that it could be done in 9. After reading your post, I re-examined my strategy and realized that there was an inefficient part that essentially wasted 1 question, hence my limit of 10. Great work and thanks for that detailed post. I learned something new today. Alternative strategy

Yes, we can't ask anyone what answer someone else will give to a particular question, unless we are sure that we are either asking about a truth-teller / liar or asking the question to a random answerer.

Let's say that the liars and the truth tellers do not know what the random answerers would respond to any given question. I think the question is more challenging that way.

I didn't think about summing a series neither. Do you mean summing the chance that John won given that Bill has 0 points, 1 points, and so on? I didn't think about it that way, although now I wonder why I didn't think of that before. Recursive functions are actually fit this problem quite well. It only takes a couple of lines as in the following pseudo-code. And yes, math is very cool!

But I'm very far from actually writing such a successful strategy (at least the first part of it), so for now I guess I'm just bragging I eagerly look forward to this strategy =)

I don't think that this question is "so poorly written that it renders the answer meaningless". I understand the puzzle just fine, as do The Genius of Genius, Dhanannjay Deo, rob_3, and I suspect many others. This is a very nice puzzle that demonstrates the elegance of recursive functions, and makes a valuable contribution to this Logic/Math puzzle forum. We have been through this before. I recommend that you read these excellent responses from and to your last post.

A recursive code shows that

Some clarifications please: 1) Does the fact that John is 20% better than Bill means that John is 20% more likely to win a point (e.g., John would on average win 6 out of every 11 points) ? 2) Does serving change the odd of a person winning the point? If so, how does that change?

This is an extension of my last which was flawed but still had some value to the board thanks to contribution from araver. Suppose that you encounter 7 people, each of whom is either a truth teller (always tells the truth), a liar (always tell lies), or a random answerer (always answer randomly with 'Yes' or 'No'). You know that in this group of 7, there are 3 random answerers, 2 truth teller, and 2 liars, but you don't know which person is which. The puzzle is to identify the 3 random answerers with the following information: 1) You can only ask yes/no questions to 1 person at a time 2) You can ask the same question of different people, or address different questions to the same person. 3) You can not ask any question which is impossible for a truth teller/liar to answer with a yes/no (ie. asking a truth teller what a random answerer would say to a particular question, asking paradoxes, etc. ) 4) Everytime you ask a question, your question count increases by 1 5) Each person in the group of 7 knows what type of people the remaining 6 are. Determine a strategy that is guaranteed to find the 3 random answerers in 10 questions or less.

Good work, araver. You made some valuable contribution from an otherwise flawed puzzle. I'm glad you enjoyed it. I sure enjoy reading your proof. This is a good start, but it is virtually impossible to distinguish between mirror pairs. Suppose we narrow the problem to either possibility 2 or 3 in your example, it is virtually impossible to determine which is the correct one from there.

Yes, if that happens, the truth teller's head will explode. Actually, more seriously, I just realized that I made a mistake in constructing this puzzle. Turns out in the worst case I can narrow the 6C3 = 20 possible configurations down to 2, but no further. Therefore a solution is not possible, at least not for me. If a mod can delete this topic, I'd appreciate it very much. Sorry to those who spent time thinking about the problem as it was posted.

Suppose that you encounter 6 people, each of whom is either a truth teller (always tells the truth), a liar (always tell lies), or a random answerer (always answer randomly with 'Yes' or 'No'). You know that in this group of 6, there are 3 random answerers, 1 truth teller, and 2 liars, but you don't know which person is which. The puzzle is to identify the 3 random answerers with the following information: 1) You can only ask yes/no questions to 1 person at a time 2) You can ask the same question of different people, or address different questions to the same person. 3) Everytime you ask a question, your question count increases by 1 4) Each person in the group of 6 knows what type of people the remaining 5 are. So, determine a strategy that is guaranteed to identify the 3 random answerers. Bonus: what is the maximum number of questions required to guarantee correct identification?

In the original setting of the problem: "In a future not so far way, Earth archaeologists find on a far away planet a fragment from a long lost civilization. This fragment involves an unknown operation *|*. Unlocking its secrets may lead to a breakthrough in understanding their civilization. " Please allow me to state (and add to the OP) 2 informal assumptions I made when posting the original setting of the problem: 1) We're talking about aliens so they *might* possess different insights than humans. 2) It's a fairly used operation on their world, so one *might* expect the symmetry /simplicity / "beauty" of a human operation (e.g. addition/ multiplication, etc.) Disclaimer: I am not implying the fact that an alien operation is bound to be hard to grasp by humans, just that in worst-case scenarios it might be difficult to translate in human-operations. This may or may not be the case here. Just sayin'. P.S. I'm not sure how sane I am at this hour so if I don't make much sense, feel free to skip these assumptions. Other than the slightest hint possible, there's no real value / necessity in these assumptions. EDIT: grammar I was just being facetious. I know I didn't have the correct function, but wanted to point out the fact that The challenge is to find one that has 'symmetry /simplicity / "beauty"'. I'm not really good at this type of problem, so I'll wait for the correct answer from the brain denizens. Nice puzzle. It's rare for a puzzle on brainden to be unsolved this long.

Also, can you please let me know how did you come up with such a complex formula? Do you have some standard method for these kind of problems or you are using some computer algorithm? Edit: added spoiler. Actually, the example above does work for 1 *|* 0; ( 1700 + 1309*(1) + 182*(1) + 985*(1) ) = 4176, which is equal to 2 modulo 2087. I did not notice the post that required the operation to be commutative. That can be easily fixed. This is one example that fits all 6 clues and is commutative

Here's one solution that fits the existing 6 clues. Plenty more where this comes from =)

Ah, that's it. Good work! Thanks for working on this problem.

Excellent! Thanks for the explanation of your strategy. I'm glad you enjoyed it. I think something has gone amiss here. This solution does have a cycle of 60, so it properly takes y back to itself on the 60th power. The powers of P in between 0 and 60, however, don't match the data though.