bushindo
-
Posts
719 -
Joined
-
Last visited
-
Days Won
5
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by bushindo
-
-
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.
-
I agree. As always, you are correct!
Good one, Bushindo!
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.
-
Ah, brilliant!
I admit I was a little lazy and didn't bother to optimize or check in detail. I thought one case was unbreakable in less than 8 and didn't bother to check the others.
Now, after a little more pondering, I'll call your claim and raise you
that both the random and the alternator can be found in at most 7
I'm borrowing a trick from your sleeve (in part3 puzzle) that 4 YES's means we could have stopped before the fourth YES. I'm also borrowing one of my tricks, asking about the next-in-line's alignment to narrow the cases faster.
And I'm possibly finding a new trick on how to detect flipping answers (see case 2YES/2NO below).
Again, as in my previous solution(s), rephrase all questions as oblique-questions to make the liar sound like a truth-teller. Also, replace any "Is X truth-teller?" from the following with "Is X a liar or a truth-teller?".
Round 1
Q: "Is Random one of the last 2 (third or fourth) in the line?".
Ask question Q to first three of them. After 3 of these questions you get:
- either 2YES/1NO or 2NO/1YES in which case it's undecided and proceed with asking the fourth man the same question.
- 3 YES's or 3NO's in which case proceed to Round 2 without asking the fourth question.
Depending on the number of YES/NO answers, there are 5 cases for Round 1:
- 2 YES/2NO - 4 questions spent
- 3 YES/1 NO or 3 NO/1 YES - 4 questions spent
- 3 YES or 3 NO - 3 questions spent!
2YES/2NO - you can get both Random and Alternator in at most 7 questions.
Round 1 - You must spend your first 4 questions till you get 2YES 2NO, since up until the last of the 4, you could still get a majority.
You only know that the alternator was acting as random (and siding with random) so there's no definite way to point a person that's not random.
Good news is that Alternator will tell the truth the next 2 times you ask him a question.
For Round 2:
- If you take 1 of the 4 you could be looking at either case (T, A, R). Very uncertain.
- If you take 2 from same side you get TT or AR. Since Alternator will act as a truth-teller this time, you get in fact either TT or TR. Which is good enough.
So, pick one side, take the two that answered YES to the first question.
Ask them again the same question as in Round 1. You're looking at either 2YES, 2NO, or 1 YES/1 NO.
- If you get 1 YES / 1 NO, then this is the Random+Alternator side since one of them changed his answer from Round 1. The other side is the truth-tellers' side.
So you can finish in 7 by asking a truth-teller which of the two asked in Round 2 is random. The other one is the alternator.
- If you get 2 YES, then the answer to the question is surely YES (either TT or AR - one of them is definitely telling the truth this time). But since the answer is YES and the question is the same, you've selected the two truth-tellers in Round 2, since they can't be the NO guys in Round 1 (the fact that it's the same question is crucial here!). So you can still finish in 7 by asking one of the truth-tellers if one of the other two is random. The other one on his side in Round 1 is the alternator.
- If you get 2 NO's, then both have changed their opinion since Round 1 (since you picked the YES side). So this is the Random+Alternator side. Again finish in 7 by asking one of the truth-tellers (the other side) if one of the guys in Round 2 is Random. The other one in Round 2 is the Alternator, so you get both.
3YES 1NO - Finish in 7 finding out both the alternator and the random:
From Round 1 - Q is true and two of the three YES's are truth tellers and the other is either random (in which case alternator was random in Round 1) or alternator (either randomly guessing or truth-teller).
You know that Random is either 3rd or 4th in line (since Q is true). Avoid him by asking only the first 2 in line in Round 1.
Now, the first two answered either 2YES's or YES/NO in Round 1:
- If the first two answered 1 YES/1 NO in Round 1, then the NO guy is the alternator lying in Round 1. You can finish in 5 by asking the other whether random is 4th.
- If the first two answered 2 YES's in Round 1 - they are either 2 truth-tellers or one truth-teller and alternator (either randomly guessing or truth-teller, cannot know for sure).
Ask these two if the Alternator is one of the last two. At least one of them tells the truth.
---If you get 2 YES's, then both Random and Alternator are 3rd and 4th which makes the first two truth-tellers. Finish in 7 asking a truth-teller if Random is 4th.
---If you get 2 NO's then Alternator is one of the first two (the answer to the question in Round 2 says so)
---If you get 1 YES and 1 NO, then Alternator is one of the first two (since truth-tellers don't disagree).
In both cases in which the Alternator is one of the first two, we get that the other YES guy in Round 1 (who we didn't ask in Round 2) is a truth-teller and the NO guy in Round 1 the Random. Finish in 7 by asking the truth-teller if Alternator is 1st.
3NO 1YES is symmetrical to 3YES 1NO (replace lying with minority vote above, and ask the 3rd and 4th instead of 1st and 2nd to avoid Random)
3YES - Finish in 7 finding out both the alternator and the random:
Rememember Round 1 spent only 3 questions since we stopped before asking the last.
Q is true after round 1 so Random is either 3rd or 4th.
Then the first two can be TT or TA.
Ask the first if the second is a truth-teller.
-If he answers YES then either he's the alternator and the second is the truth-teller or he's a truth-teller and the second is the truth-teller.
--Either way, the 2nd is a truth-teller, so ask him if the first is the alternator:
---If he says YES, you got the alternator. Ask the truth-teller if the 4th is Random and you get Random too in 3+1+1+1=6 questions
---If he says NO, you got the two truth-tellers as 1st and 2nd. Ask any of them if the 4th is Random and you get Random(either 4th or 3rd) and the Alternator is the other guy(either 3rd or 4th) in 3+1+1+1=6 questions.
-If he answers NO then either he's the alternator and the second is the truth-teller or he's a truth-teller and the second is the alternator. You've spent 3+1=4 questions so far.
Note that if you ask an Alternator something twice (with oblique-questions that liars and truth-tellers answer the same), he's bound to act like a truth-teller at least once.
So, ask the first TWICE if the 4th is Random (6 questions so far)
--If he gives you 2YES's or 2NO's, then you know Random is the 4th or the 3rd. Now, the other guy (3rd or 4th) is definitely a truth-teller (since we already narrowed it down that the alternator is among the first two). Ask him if Alternator is first and finish in 7 questions with both Random and Alternator found.
--If he gives you 1 YES and 1 NO, then he's the Alternator. Ask the second (who is surely a truth-teller)if Random is 4th and you finish in 7 questions again.
3NO - I will discuss this case because one may think the symmetry to the 3YES case is less clear since we stopped after 3 questions. But it is symmetrical since we did not use any information about who answered what in the first round, just the answer itself was important.
Rememember Round 1 spent only 3 questions since we stopped before asking the last.
Q is false after Round 1 so Random is either 1st or 2nd.
Then the last two can be TT or TA.
Ask the 4th if the 3rd is a truth-teller.
-If he answers YES then either he's the alternator and the 3rd is the truth-teller or he's a truth-teller and the 3rd is the truth-teller.
--Either way, the third is a truth-teller, so ask him if the fourth is the alternator:
---If he says YES, you got the alternator. Ask the truth-teller if the 1st is Random and you get Random too in 3+1+1+1=6 questions
---If he says NO, you got the two truth-tellers as 3rd and 4th. Ask any of them if the 1st is Random and you get botth Random(either 1st or 2nd) and the Alternator is the other guy(either 2nd or 1st) in 3+1+1+1=6 questions.
-If he answers NO then either he's the alternator and the 3rd is the truth-teller or he's a truth-teller and the 3rd is the alternator. You've spent 3+1=4 questions so far.
Note that if you ask an Alternator something TWICE (with oblique-questions that liars and truth-tellers answer the same), he's bound to act like a truth-teller at least ONCE.
So, ask the 4th TWICE if the 1st is Random (6 questions so far)
--If he gives you 2YES's (or 2NO's), then you know Random is the 1st (or the 2nd). Now, the other guy (2nd or 1st) is definitely a truth-teller (since we already narrowed it down that the alternator is among the last two). Ask him if Alternator is 4th and finish in 7 questions with both Random and Alternator found.
--If he gives you 1 YES and 1 NO, then he's the Alternator. Ask the 3rd (who is surely a truth-teller) if Random is 1st and you finish in 7 questions again.
And, it follows trivially
that after getting random and alternator in 7 questions, one can get the liar from the truth teller, thus completing the arrangement in at most 8 questions. By asking another oblique question one of the identified "truth-tellers" after 7 questions: "If I would ask you if X is a liar would you answer YES?" where X is the other "truth-teller".
Nice work! Once again you made a nice contribution to this topic. Thanks!
-
Again, as seen before by asking "oblique" questions.
Assuming in the following that all questions are re-processed as "If I would ask you if P is true would you answer Yes?" so basically we have 2T (truth-tellers), 1 R(Random) and 1 A(Alternator).
Assume all 4 are standing in a line.
First question Q) "Is the random one of the last 2 (third or fourth) in the line?". Ask this question to each of the four ONCE. You spend 4 questions this way.
Depending on the number of YES/NO answers, there are 5 cases:
4YES -> Q is true. Alternator was either telling the truth or playing random (and guessing it, but that's not the point).
Note that because the random is either the third or the fourth (as Q is true), then the first two can be TT or TA.
Note that if asked the same question twice, the alternator must answer at least once as a truth-teller.
So ask the first two, TWICE each one, if the last one (4th) is Random.
These four answers are either 4 truths (if TT or TA and both times the alternator was saying the truth) or 3 truths and 1 unknown (if TA and one time alternator was randomly answering). Either way, at least 3 are truths so you know if last one is Random by majority vote of these answers. If majority is YES then Random is fourth. If majority is NO, then Random is third.
Finished in 8 questions this way.
3YES 1NO -> Q is true and two of the three Yes's are truth tellers.
Ask all 3 that said Yes to the first question if last (4th)is random.
Majority vote decides since there are at least two truth-tellers: pick last if YES, third if NO.
Finished in 7 questions this way.
2YES 2NO -> alternator was acting as random (and siding with random). This is the only piece of solid information in this case.
Pick 2 of the Yes's and 1 of the No's.
Either:
A) you picked 2 truth-tellers + 1 random/alternator in which case you have a majority.
B) you picked random+alternator+truth-teller. But as alternator acted like random at the previous question, he will act as a truth-teller for the next question you ask of him. Again you have guaranteed majority for the next question!
Ask the three of them the same question Q as before "Is the random one of the last 2 (third or fourth) in the line?.
This time you get a majority truth-tellers so you know what random and alternator answered to the first question. Moreover, you know what the truth-tellers answered to the first question (opposite than the random).
So you narrow down random to one of two and you have both the truth-tellers narrowed down.
To get the random from the two that answered falsely to the first question, ask a final (8th) question to any of the truth-tellers: Is X random (pointing at any of the two). Depending on his answer you get the random and the either is the alternator.
1YES 3NO -> Q is false. Two of the three No's are truth tellers.
Ask all 3 of them if first is random. Majority vote decides - pick first if YES, second if NO. Again, 7 questions.
4NO -> Q is false, so Random is one of the first two.
Ask the last 2, twice each one, if the first one is Random. As in the 4YES case, you get truth-answers in majority.
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,
The random answerer in fact can be narrowed down in 7 questions instead of 8. For instance, take the case of 4 YES in the above example. Having narrowed the random answerer to the last two people in line, we can pick a person from the first two in line and ask him the same question twice, "Is the random answerer the 4th person in this line?"
a) If the chosen person is a truth teller, we'll get two identical true answers, which allows us to single out the random answerer in 4 + 2 questions.
b) If the chosen person is a alternator, he will either give us two identical true answers, or one YES and one NO. In the first case, we know where the random answerer is in 4 + 2 = 6 questions; in the latter case, we will know that he is the alternator, and pick the remaining person from the first two (a truth teller) and get the random answerer's position in 1 question (4 + 2 + 1 = 7 total).
I'm not able to show that it is possible to get both the random answerer and the alternator in 7 questions. But it should be straightforward to get the positions of both in 8 questions.
araver, your research was conducted well and is mostly valid except for one thing that happens to negate the entire legitimacy of your argument....it is impossible (as far as I can tell) to distinguish between a truth teller and a random. Let's use the case of 3YES and 1NO as an example:
"3YES 1NO -> Q is true and two of the three Yes's are truth tellers.
Ask all 3 that said Yes to the first question if last (4th)is random.
Majority vote decides since there are at least two truth-tellers: pick last if YES, third if NO.
Finished in 7 questions this way."
Suppose the following:
Person A: Random
Person B: Liar
Person C: Truth
Person D: Alternator
Using your question sequence, the respondents' answers could look like this:
A: Yes, Yes
B: No, N/A
C: Yes, No
D: Yes, No
Switching the random's answer also leads to an inconclusive result:
A: Yes, No
B: No, N/A
C: Yes, No
D: Yes, No
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.
-
Did not thought of the majority argument. Seems trivial now
Kudos for the reasoning, smooth indeed.
After giving up my divide-et-impera illusions, I did not want to make such a long strategy ... actually started it thinking it will take 8q most, and ended kinda brute-forcing it with 6 static questions.
I'm still pondering if it's possible to get an adaptive/dynamic strategy that works faster for the first part i.e. balance the tree a little, since it looks too far from an equilibrated tree.
Thanks a lot for the challenge.
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.
-
My first strategy
In 9 questions.
Step 0 - Assume all liars are truth-tellers using known techniques to construct questions.
-------------------------------------------------------------------------------------------
First of all, the distinction between liars and truthtellers is irrelevant. A well-known technique (when dealing with truthtellers/liars alone) if you want to see if a statement P is true or not is to ask another question instead:
Q:"If I would ask you if P is true would you answer Yes?".
If P is true: a liar answers No to P therefore answering Yes to Q. a truthteller answers Yes to both P and Q.
If P is false: a liar answers Yes to P therefore answering No to Q. a truthteller answers No to both P and Q.
So P is true if and only if you get an Yes answer to Q.
Now assuming all questions are asked like this, we have transformed the problem to a similar problem with 3 randoms and 4 truthtellers. Moving on.
Step 1 - Static 6 questions
---------------------------
Assume all 7 are standing in a line.
I will ask each of the first 6 in line the same question: "Is the person next in the line (to your left/my right) to you a random?". Note that from Step 0, my actual question is "If I would ask you if the person next in the line to you is a random would you answer Yes?" to elicit the same response from truth-tellers and liars.
Note that this question reffers to only 2 people's position and has the following "truth table":
Yes No RR 1 1 RT 1 1 TR 1 0 TT 0 1
where 1 means response is possible and 0 means response is impossible.
A truth-teller followed by a random cannot answer No and a truth-teller followed by a truth-teller cannot answer Yes.
These types of questions targeted at position X can be used to reduce the number of possibilities:
- branch Yes is true for all arrangements with randoms on position X and all arrangements with truth-tellers on X and randoms on X+1
- branch No is true for all arrangements with randoms on position X and all arrangements with truth-tellers on X and truth-tellers on X+1
There are 6 (static/non-adaptive) questions, so 2^6=64 possible combinations of answers.
The following table shows the possible arrangements for each combination and creates a "mask" of known positions: e.g. if only arrangements TRTTTRR and RTTTTRR are possible for a combination of answers then the last 5 positions are sure - written --TTTTRR (where - stands for an unknown).
1) NNNNNN- 1 possibilities: RRRTTTT. 7 sure positions: RRRTTTT.
2) NNNNNY- 1 possibilities: RRTTTTR. 7 sure positions: RRTTTTR.
3) NNNNYN- 2 possibilities: RTTTTRR, RRTTTRT. 5 sure positions: R-TTTR-.
4) NNNNYY- 2 possibilities: RTTTTRR, RRTTTRT. 5 sure positions: R-TTTR-.
5) NNNYNN- 3 possibilities: TTTTRRR, RTTTRRT, RRTTRTT. 3 sure positions: --TTR--.
6) NNNYNY- 3 possibilities: TTTTRRR, RTTTRTR, RTTTRRT. 4 sure positions: -TTTR--.
7) NNNYYN- 3 possibilities: TTTTRRR, RTTTRRT, RRTTRTT. 3 sure positions: --TTR--.
8) NNNYYY- 3 possibilities: TTTTRRR, RTTTRTR, RTTTRRT. 4 sure positions: -TTTR--.
9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.
10) NNYNNY- 3 possibilities: TTTRRTR, RTTRTTR, TTTRRRT. 3 sure positions: -TTR---.
11) NNYNYN- 4 possibilities: TTTRTRR, TTTRRRT, RTTRTRT, RTTRRTT. 3 sure positions: -TTR---.
12) NNYNYY- 4 possibilities: TTTRTRR, TTTRRTR, TTTRRRT, RTTRTRT. 3 sure positions: -TTR---.
13) NNYYNN- 3 possibilities: TTTRRRT, RTTRRTT, RRTRTTT. 3 sure positions: --TR--T.
14) NNYYNY- 3 possibilities: TTTRRTR, RTTRTTR, TTTRRRT. 3 sure positions: -TTR---.
15) NNYYYN- 4 possibilities: TTTRTRR, TTTRRRT, RTTRTRT, RTTRRTT. 3 sure positions: -TTR---.
16) NNYYYY- 4 possibilities: TTTRTRR, TTTRRTR, TTTRRRT, RTTRTRT. 3 sure positions: -TTR---.
17) NYNNNN- 3 possibilities: TTRRRTT, RTRRTTT, RRRTTTT. 3 sure positions: --R--TT.
18) NYNNNY- 3 possibilities: TTRRTTR, RTRTTTR, RRTTTTR. 3 sure positions: ----TTR.
19) NYNNYN- 5 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT, TTRRRTT. 0 sure position: -------.
20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.
21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.
22) NYNYNY- 3 possibilities: TTRTRTR, TTRRTTR, TTRTRRT. 3 sure positions: TTR----.
23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.
24) NYNYYY- 3 possibilities: TTRTRTR, TTRTRRT, TTRRTRT. 3 sure positions: TTR----.
25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.
26) NYYNNY- 2 possibilities: TTRRTTR, RTRTTTR. 5 sure positions: -TR-TTR.
27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.
28) NYYNYY- 3 possibilities: TTRTTRR, TTRRTRT, RTRTTRT. 4 sure positions: -TR-TR-.
29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.
30) NYYYNY- 3 possibilities: TTRTRTR, TTRRTTR, TTRTRRT. 3 sure positions: TTR----.
31) NYYYYN- 4 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT. 3 sure positions: -TR---T.
32) NYYYYY- 3 possibilities: TTRTRTR, TTRTRRT, TTRRTRT. 3 sure positions: TTR----.
33) YNNNNN- 2 possibilities: TRRRTTT, RRRTTTT. 5 sure positions: -RR-TTT.
34) YNNNNY- 2 possibilities: TRRTTTR, RRTTTTR. 5 sure positions: -R-TTTR.
35) YNNNYN- 4 possibilities: TRTTTRR, RTTTTRR, TRRTTRT, RRTTTRT. 3 sure positions: ---TTR-.
36) YNNNYY- 4 possibilities: TRTTTRR, RTTTTRR, TRRTTRT, RRTTTRT. 3 sure positions: ---TTR-.
37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.
38) YNNYNY- 4 possibilities: TRTTRTR, RTTTRTR, TRTTRRT, RTTTRRT. 3 sure positions: --TTR--.
39) YNNYYN- 4 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT. 3 sure positions: ---TR-T.
40) YNNYYY- 4 possibilities: TRTTRTR, RTTTRTR, TRTTRRT, RTTTRRT. 3 sure positions: --TTR--.
41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.
42) YNYNNY- 3 possibilities: TRTRTTR, RTTRTTR, TRRTTTR. 3 sure positions: ----TTR.
43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.
44) YNYNYY- 3 possibilities: TRTRTRT, RTTRTRT, TRRTTRT. 3 sure positions: ----TRT.
45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.
46) YNYYNY- 2 possibilities: TRTRTTR, RTTRTTR. 5 sure positions: --TRTTR.
47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.
48) YNYYYY- 2 possibilities: TRTRTRT, RTTRTRT. 5 sure positions: --TRTRT.
49) YYNNNN- 3 possibilities: TRRRTTT, RTRRTTT, RRRTTTT. 4 sure positions: --R-TTT.
50) YYNNNY- 3 possibilities: TRRTTTR, RTRTTTR, RRTTTTR. 4 sure positions: ---TTTR.
51) YYNNYN- 4 possibilities: TRTTTRR, TRRTTRT, RTRTTRT, RRTTTRT. 3 sure positions: ---TTR-.
52) YYNNYY- 4 possibilities: TRTTTRR, TRRTTRT, RTRTTRT, RRTTTRT. 3 sure positions: ---TTR-.
53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.
54) YYNYNY- 2 possibilities: TRTTRTR, TRTTRRT. 5 sure positions: TRTTR--.
55) YYNYYN- 4 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT. 3 sure positions: ---TR-T.
56) YYNYYY- 2 possibilities: TRTTRTR, TRTTRRT. 5 sure positions: TRTTR--.
57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.
58) YYYNNY- 3 possibilities: TRTRTTR, TRRTTTR, RTRTTTR. 3 sure positions: ----TTR.
59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.
60) YYYNYY- 3 possibilities: TRTRTRT, TRRTTRT, RTRTTRT. 3 sure positions: ----TRT.
61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.
62) YYYYNY- 1 possibilities: TRTRTTR. 7 sure positions: TRTRTTR.
63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.
64) YYYYYY- 1 possibilities: TRTRTRT. 7 sure positions: TRTRTRT.
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.
20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.
Ask oracle if first is R (2 cases).
If first is R, ask if 2 is T (one case each answer).
ElseIf first is T, ask if 4 is R (one case each answer).
25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.
Ask oracle if first is T (1 case).
ElseIf first is R, ask if 2 is T (one case). If 2 is R ask if 3 is T (one case each answer).
27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.
Ask oracle if first is R (1 case).
ElseIf first is T, ask if 6 is T (one case). If 6 is R ask if 4 is T (one case each answer).
41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.
Ask oracle if first is T (2 cases).
If first is R, ask if 3 is T (one case each answer).
ElseIf first is R, ask if 2 is T (one case). If 2 is T ask if 4 is T (one case each answer).
45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.
Ask oracle if first is R (2 cases).
If first is R, ask if 2 is T (one case each answer).
ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).
57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.
Ask oracle if first is T (2 cases).
If first is T, ask if 3 is T (one case each answer).
ElseIf first is R, ask if 2 is T (one case). If 2 is R ask if 3 is T (one case each answer).
61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.
Ask oracle if first is R (3 cases). If 1 is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).
ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).
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.
9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.
Ask oracle if first is T (one case).
If first is R, ask if second is T (one case).
If first is R and second is R, ask if third is T (one case each answer).
21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.
Ask oracle if first is T (2 cases).
If first is T, ask if fourth is T (different in these 2 cases).
ElseIf first is R, ask if second is R (one case). If the second is T ask if fourth is T (one case each answer).
23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.
Ask oracle if first is R (2 cases).
If first is R, ask if second is T (different in these 2 cases).
ElseIf first is T, ask if fourth is T (one case). If the fourth is R ask if fifth is T (one case each answer).
29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.
Ask oracle if first is T (2 cases).
If first is T, ask if 4 is T (one case each answer).
ElseIf first is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).
37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.
Ask oracle if first is R (2 cases).
If first is R, ask if 2 is T (one case each answer).
ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).
43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.
Ask oracle if first is R (2 cases).
If first is R, ask if 6 is T (one case each answer).
ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).
47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.
Ask oracle if first is R (2 cases).
If first is R, ask if 6 is T (one case each answer).
ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).
53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.
Ask oracle if first is R (3 cases). If 1 is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).
ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).
59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.
Ask oracle if first is R (1 case).
ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).
63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.
Ask oracle if first is R (1 case).
ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).
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
As araver noted, this problem can simplified by replacing all liars with truth tellers. This does not affect the solution.
Let's say that the 7 people are standing in a line. If we look at the last 3 people, there are 4 possibilities: either there is 0, 1, 2, or 3 random answerers inside this group. Another fact of note is that since there are 4 truth tellers and 3 random answerers, if we ask all 7 the same question, we can get the correct answer by comparing the number of NO's to the number of YES's. For instance, if we get 4 NO and 3 YES to a particular question, we know that the true answer is NO. In fact, if we are asking questions sequentially, we might as well stop when we get 4 YES or 4 NO.
1) Start going from left to right, and ask 1 person at a time, "Are there 0 or 1 random answerers within the last 3 people in this line?".
2) As soon as we get 4 YES or 4 NO, stop asking since we already know the true answer.
3) Once we know the answer to number 1, we can construct a group of of 3 that has more truthtellers than random answerers. For instance, if there are 0 or 1 random answerers within the last 3 people in line, choose those 3. If there are 2 or 3 random answerers in the last 3, choose 3 people from the first 4 in line.
4) We can narrow down a truth teller with 1 question from the group of 3 that has more truthtellers than random answerers (see this )
5) Having identified a truth tellers, we can identify the random answerers using binary search.
Note that in step 2, if we get answers contrary to the majority opinion, those are guaranteed to be random answerers. For instance, we get 4 YES and 1 NO to any question, then the NO must be coming from a random answerer. The cases that requires the most questions are when the first 4 people all answer YES or all NO to part 1). Let's consider the case when the first 4 all answer YES. If that is so, then the last 3 people have 0 or 1 random answerer. We can identify a truth teller from the last 3 with 1 question. That means that there are either 3 random answerers distributed in the first 4 (4C3= 4 ) or 2 random answerers distributed in the first 4 and 1 random answerers from the last 3 minus the truth teller (2C1 * 4C2 = 12 ). Since there are 4+ 12 = 16 states, we can narrow it down in 4 questions using binary search. That makes a total of 4 + 1 + 4 = 9 questions required. The case with 4 NO can be done similarly.
-
Then going by rule number 3 we cant ask anyone what answer anyone else can give unless we a sure that we are either asking about a truth-teller / liar or asking the question to a random answerer?
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.
-
Do the liars and truth tellers know what the random answer will answer for a given question?
Or in another way of asking it. Is the random answer for a particular question predetermined such that if I go to a truth teller and ask him what the random answerer will answer to a particular question and then go to the random answerer and ask him that question they will always be the same answer?
Asked to truth teller "If I next ask him (the random answerer) if he is a liar what will be his answer ?"
Truth teller: True
Asked to specified random answerer "Are you a liar?"
Random answerer: True
The answer will still be random to us it just means that the liar, truth teller and random answerer have access to the same random number table.
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.
-
Recursive functions? I just noticed that! I only summed the terms of a simple series. I understand that you could do this with recursive functions, but it seems like overkill in this case.
I guess we all have our different ways of approaching things. I suppose that's why maths are so cool!
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.
%%% prob( J, B ) is a function that gives the probability that John wins given that John has J points and Bill has B points. prob = function( John_score, Bill_score ) if John_score == 21 return 1 if Bill_score == 21 return 0 return ( (6/11)* prob( John_score + 1, Bill_score ) + (5/11)* prob( John_score , Bill_score + 1.5 ) ) endFunction answer = prob( 0, 0 )And yes, math is very cool!
-
Actually, I have a very strong hunch that
it can be done in 8 questions (or less, depending on the answers). Worst case would be 3+1+1+3=8 questions
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 =)
-
Sorry to continue to be a grouch, but this is another example where the question is so poorly written that it renders the answer meaningless. The clarification helped, but it's still impossible to know the intent. I suspect that rob_3's approach is the correct one. If so, the problem might be reworded thusly:
John and Bill are playing a single game of Ping-pong.The first player to reach 21 points wins the game.
John scores 20% more points than Bill.
Bill says to John, "Well, you`ll win if we score as usual, because you play better than me".
"How do you want us to score then?" asks John.
Bill replies, "Any point I score will be counted as 1.5 points to me, but for you a point will simply be worth only one point. Do you agree?"
"OK" says John, "But I`ll serve first".
Each player serves three times in a row and then the server changes.
Now, who will win that game?
It should be noted that, under the rules of table tennis, the person serving changes hands after two points are scored. Why they are doing something unorthodox may be the author's attempt to mislead. Or the author may be unaware of the fact that the scoring is not dependent on who served.
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.
-
John and Bill wanted to play only one game Ping-pong.The first player to reach 21 points wins the game.
John is 20% better than Bill.
Bill said to John "well, you`ll win if we score as usual,cause you play better than me".
"how do you want us to score then?" asked John.
Bill:"any point I`ll score will be counted as(1.5) points to me,and for you a point will be as it is only one point,do you agree?"
" OK" said john,"but I`ll start the first serve".
Each player serves three points in a row and then switch server.
Now, who won that game?
A recursive code shows that
John wins with probability .252
-
John and Bill wanted to play only one game Ping-pong.The first player to reach 21 points wins the game.
John is 20% better than Bill.
Bill said to John "well, you`ll win if we score as usual,cause you play better than me".
"how do you want us to score then?" asked John.
Bill:"any point I`ll score will be counted as(1.5) points to me,and for you a point will be as it is only one point,do you agree?"
" OK" said john,"but I`ll start the first serve".
Each player serves three points in a row and then switch server.
Now, who won that game?
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.
-
And since I started ranting, let me continue with
a proof that (N,0,N) is not solvable (always) because of the symmetry.
For every (N,0,N) instance (N truthtellers, 0 liars and N randoms) there are a number of possible arrangements.
This number is always even, since for each arrangement there is a mirror arrangement where truth-tellers take the place of randoms and viceversa.
And no arrangement is it's own mirror.
E.g. mirror(TRRT)=RTTR, mirror(TR)=RT.
Note that this mirror argument (the mirror of an arrangement is an arrangement of the same type of instance) only works for (N,0,N)-instances.
Assume that a successful interrogation strategy exists for the (N,0,N)-instance. Let M be maximum number of questions this strategy needs in the worst-case scenario. This means that in at most M number of questions, one can tell who the randoms are, independent of the random answerers' answers/strategy/randomness.
Assume the following infinite-strategy: "I will act as if I am the truth-teller standing on the same position in the mirror-universe".
I'll call this type of person Infinite-Look-Alike.
He is neither Random (since he's predictable), he is neither Truth-teller.
One might ask if he is a perpetual liar, but this is not relevant to the proof. Actually he lies only about the arrangement and tells the truth otherwise i.e. a Perfect-Liar - choose a lie and stick with it without contradicting known facts
Now, since random answerers are truly random, there's no certain way to distinguish them from an Infinite-Look-Alike in a finite number of questions. A random guy (by himself) can act like the Infinite-Look-Alike indefinitely.
In all the possibilities of M consecutive random answers, for any number M, there is a possibility where all random answerers act like Infinite-Look-Alikes (for the first M questions directed at them).
Which means there is a possibility that they act like Infinite-Look-Alikes for the entire successful interrogation strategy.
The problem is, that in that mirror universe, the mirror-truth tellers act like Infinite-Look-Alikes, and mirror-Randoms act like truth-tellers.
In these circumstances, that ideal-interrogation strategy, applied in the mirror universe, gives the exact opposite result - failing.
So, (N,0,N) is not solvable.
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.
Hi...did anyone think about deviding the 6 people into two groups of 3?
In this case we will have only three possiblities:-
1- RRR......TLL
2- RRL......TLR
3- RLL......TRR
This method may help to find a possible solution,and minimize number of questions..
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.
-
Hypothetically, if a question is asked of the truth teller with an answer he cannot possibly determine accurately (e.g. "If asking a yes or no question of a random answerer, will his/her answer be correct"), does the truth teller's head explode?
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?
-
I like your thinking very much
, but its ... finite. For every linear-algebra generated function (sort of interpolation) you can think of, I am almost sure I can find a pair that doesn't satisfy it. I'm pretty confident (although I haven't tried a formal proof), that in the long run, this operation cannot be expressed with a finite formula as above.
So, technically, we're pretty much down to an iterative no-cheating version of the classic game: "Tell me the number I am thinking of".
You cannot win (probably, as I said, I don't have a formal proof, just a hunch) and I cannot win (since the game never ends).
However, in theory, at infinity, I win.
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
For any set of N clues for a *|* b, there are an infinite number of functions f(a, b) that fit the N clues.
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.
-
It surely doesn't fit 1 *|* 0 =2. Also your operation is clearly not commutative (a *|* b <> b *|* a) while OP mentioned *|* is commutative.
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
a *|* b = ( 421 + 1136* (a+b)1 + 1882* (a+b)2 + 1093* (a+b)3 + 1634* (a+b)4 + 97* (a+b)5 ) mod 2087.
It is straightforward to find these coefficients using linear algebra. A new tablet may show up that shows this example to be incorrect, however, it is relatively easy to construct another example that fits the new information.
-
This puzzle seems very hard, at least to my limited brain
.You gotta give more clues. What is 1 *|*1 and 1 *|* 2? You can use spoilers so as not to spoil it for other members.
Thank you.
Here's one solution that fits the existing 6 clues. Plenty more where this comes from =)
a *|* b = ( 1700 + 1309 * a1 + 182 * a2 + 985* a3 + 1440* b1 + 1398 b2 ) mod 2087
-
My permutation is stated in a "where to" way instead of a "where from". So, the first element of 49
means that the first element of line i becomes the 49th element of line i+1. Apparently, you were
expecting a "where from", so you were expecting the 1 (59th element) of line i to become the first
element of line i+1. I couldn't tell which you wanted because the example of the reversal is the
same in both notations. I just checked and araver's is the "where from" version of my "where to".
So, my answer does match the data.
Ah, that's it. Good work! Thanks for working on this problem.
-
Actually 2 solutions since there are 2 fixed points in the permutation at positions 27 and 57 and your vector y contains 1s at positions 27 and 57 (the fixed points positions). For another y, there might be possible to distinguish an unique solution.
59 7 24 12 58 38 61 21 49 62 56 8 11 15 34 45 48 9 23 40 55 20 47 60 22 18 27 44 36 19 14 42 17 2 28 35 10 30 25 13 4 33 53 41 39 31 3 46 1 51 5 43 50 6 32 52 57 37 54 16 26 29
and59 7 24 12 58 38 61 21 49 62 56 8 11 15 34 45 48 9 23 40 55 20 47 60 22 18 57 44 36 19 14 42 17 0 28 35 10 30 25 13 4 33 53 41 39 31 3 46 0 51 5 43 50 6 32 52 27 37 54 16 26 29
Also, only the first 10 powers were needed for this particular vector y to determine P.
Excellent! Thanks for the explanation of your strategy. I'm glad you enjoyed it.
(49 34 47 41 51 54 2 12 18 37 13 4 40 31 14 60 33 26 30 22 8 25 19 3 39 61 27 35 62 38 46 55 42 15 36 29 58 6 45 20 44 32 52 28 16 48 23 17 9 53 50 56 43 59 21 11 57 5 1 24 7 10) and 27 and 57 can be interchanged.
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.
in New Logic/Math Puzzles
Posted · Edited by bushindo
Some comment