|
||
|
Title: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 9th, 2002, 5:56pm Hello everybody, To commemorate the new naming conventions created by Will this morning, I am interrupting my planned puzzle posting sequence to bring you a new puzzle dedicated to this site. (Statements made herein are NOT the opinion of the author!!! ;) ) ----- THE PUZZLE FORUM There are three puzzlers in the puzzle forum: A Newbie, a Senior Riddler, and an Uberpuzzler. All three are honest, but can only give answers to the best of their knowledge. Newbies are confused creatures. Until their fifteenth posts, they are only able to make random responses!* Senior Riddlers have great powers of perception, but are not yet infallible. In fact, they have been known to give incorrect responses up to once per day! (Though never more frequently.) They are always able to deduce the identities of their fellow puzzlers, but have no access to individual thoughts or the future. Uberpuzzlers are omniscient beings who are your greatest allies in the Puzzle Forum!!! Not only do they always know and tell the truth, but they also have a special power of Influence! Once a day, an Uberpuzzler may telepathically communicate with anyone else in the room, and clarify their thoughts so that they may answer any question correctly. However, he must do so before the other person begins their thought process, or else it may be too late. In general, an Uberpuzzler will only use his power of Influence in very specific circumstances. First, he determines the goal of the puzzler (which may, for example, be to identify all three puzzlers in five questions). Then he will determine the strategy of the puzzler (in this case, it would be a binary tree of questions, with each node determining a question and the person who should be asked; i.e. a fully dynamic set of questions and answerers). Finally, IF POSSIBLE, he will determine a circumstance (in this case, the question number) for each possible situation (in this case, permutations of the three people) under which he would apply his Influence, such that over all situations, the final set of responses would be distinct relative to the situation. (Thus, he employs a strategy defined as a mapping f:S3->Zn, where n is the number of questions, which can be interpreted as follows: for each ordering of the people s, he will Influence on question number f(s). f is chosen such that the set of total responses will be distinct for each ordering of the people -- IF POSSIBLE given the questions the puzzler is planning to ask. Note that this is different from saying that the puzzler chooses when the Uberpuzzler applies Influence! In general, the Uberpuzzler may have more than one way to make the answers distinct, but the puzzler will not know which one he is employing!!!) Determine with proof the minimum number of questions which will allow you to identify which puzzler is which. [* The Newbie does not make any new posts during questioning. ;) ] ----- As usual, I suggest no computers!! Let me know if anything is unclear! There are also follow-up questions! ;) Happy Puzzling, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by AlexH on Sep 9th, 2002, 7:00pm Haven't even started to think about this one, but very cool puzzle :D |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 9th, 2002, 7:08pm Thanks -- fellow uberpuzzler!!!!! ;) ;) ;) |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 16th, 2002, 10:54am Are we assuming one question per day? That is to say, will the Senior Riddler answer incorrectly once, or will he/she possibly be incorrect every time? Does the uberpuzzler exert influence once a day, or only once? If only once, must the influence occur on the same question number for different permutation, or could the uberpuzzler exert influence at different times for different permutations? Can the uberpuzzler make people answer incorrectly so that the solution is unambiguous? How do we score an answer that sometimes takes more questions than other times? See my preliminary answer below... day 1, to puzzler 1: is the permutation NSU? (if answer YES, done, otherwise...) day 2, to puzzler 1: is the permutation NUS? (etc. Max of 6 questions, and lots of uberpuzzler influence!) surely this must break the rules... |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 16th, 2002, 12:27pm << Wiped out for clarity -- I didn't think I did but somehow this message seemed to be double-posted!! >> |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 16th, 2002, 12:30pm Ok ok, apologies for my overly-narrative style. I keep thinking I can get away with certain natural language descriptions for my mathematical constructs, but it always comes back to bite me. :P The assumption is that all questions will occur in the span of one day. Resets never occur in the middle of questioning. That is to say, both the S mistake and the U power of influence occur at most once during the questioning. To James' [remaining] specific qs: The influence can be at different times for different permutations -- that's why I wrote the function as being from the permutation set S3 to the possible set of question numbers Zn. (Note that this is not the same as saying he preassigns the question number based on what the current ordering is!!!!! He must take into account all permutations and the timing of his influence in each case to determine how the six answer sets would come out!!!) An Uberpuzzler can only use his powers of influence to clarify correct thoughts -- he cannot, for example, convince someone that 1=0 since it does not... Can he??!!! ;) ;) ;) Seriously though, funny you should ask that. I also tried a few cases of that sort, where the Uberpuzzler was arrayed against you... But in the end, I decided it was not good to give myself a bad name like that. ;) ;) ;) Well, that, or the puzzle didn't turn out as well. ;) I'm curious though; I don't have time to think it out right now, but if there's a solution using that power to confuse, I would be interested to see it. The metric for number of questions is always based on the max necessary. Your "preliminary answer", besides taking longer than one would like, is a valid solution with a "score" of 6 questions. (5 actually, but who's counting.) But I reiterate that the entire questioning should occur within one day. Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 16th, 2002, 2:02pm I found a solution with five questions. I'm postulating that four questions is minimal, but I haven't proven it either way. Here's my reasoning: You know you need 3 questions, because of the pigeon-hole principle. On average, you'll ask at least one of those to the newbie, gaining you zero information, so you actually need 4 questions. On average, you'll probably ask the senior riddler one too, and it gains you no information either, so you need 5 questions. But maybe the uberpuzzler will intervene to make sure that you don't have to ask the fifth question. Is is good enough to know that the permutations are distinct given that the uberpuzzler will intervene, or do the permutations have to be completely distinct? (even if you didn't know that the uberpuzzler was going to intervene, you would still know the answer) Also, can the uberpuzzler use his amazing powers of deduction to deduce whether the others are going to answer upcoming questions correctly? (given that he already knows what the upcoming questions will be either way, this seems almost plausible) Of course the uberpuzzler could convince somebody that 0 = 1! In fact, the uberpuzzler would post, as a question, a very convincing proof that 0=1, and defy anyone to show it was wrong! Here's my five-question solution: for p=1,2,3, ask puzzler p: is puzzler p+1 the newbie? If they all answer the same, then the senior puzzler has already answered incorrectly. Two more questions will do it, this is easy. If they answer differently, then you will know one puzzler that for sure isn't the newbie, puzzler r. Ask puzzler r if he/she is the uberpuzzler. If yes, then ask again to confirm. If no, then you know that puzzler r is the senior puzzler. Ask that person if they answered a question incorrectly earlier. They must say 'no' (this verifies that the uberpuzzler has worked that indescribable magic), which guarantees the ordering of the other two. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 16th, 2002, 2:29pm James, Reliance on Influence: Yes, you can use the fact that you know the Uberpuzzler will intervene -- although you don't know how he will intervene. Knowledge of mistakes: Despite being omniscient, the Uberpuzzler cannot deduce when the Senior Riddler will make his mistake. This is because the affliction strikes randomly, and the "random draw" would not be conducted until after the Uberpuzzler has decided on his strategy (i.e. when to use Influence). [Good question!!!!!] 0=1: heehee :) 5Q solution: I'm not sure I get the first part here. How do you follow up in two Q's? Remember, you don't get to choose when the Influence is applied, you only know it may be applied. Best, Eric P.S. It's not "magic", it just takes a little bit of posting!!! ;) You know, a la "Yes, you are a Newbie." ;) JK. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 17th, 2002, 9:54am My question about the influence was that if you get to a position on the decision tree which has only two possibilities, can you count on the uberpuzzler to prevent one of those possibilities? That would make the permutation unique, given that the uberpuzzler is interfering. I haven't come across a scenario where that has happened, but I might try and design a solution around it. For the first part of my solution: If all three answer the same, then you know that the senior puzzler has already answered incorrectly. You further know that: for answers YYY : the novice is number uberpuzzler+1 for answers NNN : the novice is number uberpuzzler-1 Address the "are you the uberpuzzler" question to puzzler 1. If the answer is yes, then puzzler 1 is the novice or the uberpuzzler. Now you know one person that is not the novice, and you can address the next question to that person. If the answer is no, then the person is the novice or the senior puzzler, and again you know one puzzler who is definitely not the novice. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 17th, 2002, 10:59am James, My apologies if I still misunderstand your question. You're at a "position on the decision tree" (does this just mean a sequence of T/F's answered thus far? e.g. TFTF) where there are only two possibilities (e.g. SNU, SUN?). If I understand correctly, the answer is: Yes, if this was an intended terminal node (4 questions) and the Uberpuzzler could have prevented it from happening, he would have done so. However, you do not know whether he would have "prevented it" by (1) changing an answer in the SNU case, so that there you would hear "TFFF", for example, or (2) changing an answer in the SUN case, so that there you would hear "TFTT", or (3) changing both cases!!! Does that answer your question? ----- Continuing my understanding of your 5Q soln. Suppose you hear FFT to your first three qs. You know that the middle puzzler is not the Newbie. You now ask him if he is the Uberpuzzler and get T; again and you get F. Now what? It seems to me it can still be either NSU or USN. Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 17th, 2002, 11:55pm Here's a three question solution. I didn't look at the solutions that have been posted, but I did notice the number of questions they were taking. That led me to give up my laborious approach of first looking for a solution that works without influence and then trying to optimize it! I guess thinking about that did help some, though. What helped more was to give up on trying to do it in my head and start using paper and pen instead. :D Rather than just giving the questions, I'll explain what's happening as I go along. In all cases where I say that influence is used, it should be quite clear that if U fails to influence in that situation, we can go down a different path and create an ambiguous state in at least one of the leaves. It's always the newbie who needs to be influenced, if anyone does. We of course use the fact that the senior riddler can give only one wrong answer. Abbreviations: U = uberpuzzler, S = senior riddler, S' = senior riddler who answered wrong on question 1, N = newbie. Arrangements are listed in ABC order. (Initial possibilities are UNS, USN, NUS, NSU, SUN, SNU.) 1) "A, is the arrangement one of UNS, NUS, or SUN?" (Influence gets used here if A is the newbie.) If 1 is answered yes: (Possibilities are UNS, NUS, SUN, S'NU.) 2a) "B, are you the uberpuzzler?" (Influence gets used here if B is the newbie.) If 2a is answered yes: (Possibilities are NUS, SUN.) 3a) "B, is A the newbie?" If yes, conclusion is NUS; if no, SUN. If 2a is answered no: (Possibilities are UNS, S'NU.) 3b) "A, are you the uberpuzzler?" If yes, conclusion is UNS; if no, S'NU. If 1 is answered no: (Possibilities are USN, NSU, SNU, S'UN, i.e., same as in 2a but with B and C interchanged.) 2b) "C, are you the uberpuzzler?" (Influence gets used here if C is the newbie.) If 2a is answered yes: (Possibilities are NSU, SNU.) 3c) "C, is A the newbie?" If yes, conclusion is NSU; if no, SNU. If 2a is answered no: (Possibilities are USN, S'UN.) 3d) "A, are you the uberpuzzler?" If yes, conclusion is USN; if no, S'UN. This was pretty tricky. Question 1 was hard to find; I kept trying questions that are easier to state in English but that I couldn't get to work. Needless to say: Since we need at least three questions to get enough information to distinguish the six arrangements, the above 3-question solution is minimal. |
||
|
Title: Followup question Post by TimMann on Sep 18th, 2002, 12:17am Suppose the uberpuzzler has a headache and his telepathic influence isn't working. He still answers all questions correctly, though. You're reliably informed of this, but you need to press on in spite of it and find out who's who. Devise a procedure, and if you can, show that your worst case number of questions is minimal. Heck, if you can, show that the total number of nodes in your decision tree is minimal. (Joke answer: Hand out aspirins to everyone before you start the questioning, reducing the problem to the previous case.) Seriously, this looks hard and messy. I tried to work out a complete procedure in my head, but it was giving me a headache. I think the best I did that way was 11 questions on the longest path, but I wouldn't be surprised if you can do better. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 18th, 2002, 6:26am Hey, good for you Tim!! This was precisely one of my follow-ups that I mentioned in my first msg!!! :) Well, I guess it's not a very far stretch, being actually a [conceptual] simplification of the problem. Don't worry, it's not really all that messy. You can indeed do better than 11, though I won't say by how much. I actually found it in many ways easier, and in fact solved it en route to the solution to the main problem -- not suggesting there's any similarity in thought process, but just that I found it initially easier to tackle! I suppose it is a more straightforward problem that doesn't involve as "different" a kind of thinking than the others I've posted; still very fun though. Good luck! Eric P.S. Haven't had a chance to read your sol'n yet -- busy work day and all. Will get to it later. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 18th, 2002, 11:36am Eric, What I am asking is not whether or not the uberpuzzler would prevent you from reaching such a situation--if he could, he would. Let me illustrate: The path in the tree is TTF, and you have two possibilities left: SUN S'NU In the SUN case, nobody has answered incorrectly, so the uberpuzzler can't prevent this case. However, he can prevent the S'NU case. Can we therefore assume that the permutation is SUN? As for my five-question solution, after FFT, the possibilities are NSU, US'N, NUS. In the US'N case, the senior riddler can't lie again, so his first answer can't be T. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 18th, 2002, 11:45am Tim, Nice job, I verified that your soln works! I don't necessarily agree about the Influence only being used on the Newbie, though; the Uberpuzzler could use it on the SR sometimes, if he wants -- e.g. on Q1. In general, I think the UP has a little more flexibility in choosing to Influence than what you listed, but that's minor. Well actually, I should point out that you have to be careful about those Influences when proving that your final set is unique across all possible strategies for the UP. (It's a little tricky; for a sec, I thought it didn't work!) But it looks like you took care of that based on your final solution set, so I'll trust you've done your DD. Well done! Best, Eric P.S. Interestingly, your soln fails to work if we allow the UP to apply Influence twice in a day. I don't have time to think it out, but I'm guessing that that would allow other, simpler solutions, so that it would still not be as effective a puzzle. Let me know if you have any thoughts on that. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 18th, 2002, 12:35pm But James, this seems like the same question to me. Your asking whether you can "therefore assume that the permutation is XXX" is precisely the same as my saying he would block the <other> situation from giving the same answer. In short, yes, you can make the assumption you mentioned -- in the case that your third question is meant to be terminal. 5Q pf: Ok, I now understand your pf better; sorry, for some reason I interpreted your write-up as suggesting that after the first three q's are used to determine r, you were done with their usefulness. Ok, last question then: You get TTF-F so that the left puzzler is "r", and the ultimate F gives you that r is in fact S. If I am not mistaken, your choices are now SNU or S'UN. How does the question about the previous mistake distinguish these if "they must say 'no'"? (I do see how this is easily convertible to a working argument using Influence; I just don't understand what you wrote.) Sorry if I am (yet again) just missing something obvious! Thanks as always for your interest! :) Best, Eric P.S. You are the winner of a Cubic Post Award. I won't be handing out another for quite a long time!!!!! |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 18th, 2002, 1:11pm OK Tim, Here it is then, my minor modification to the problem: The Uberpuzzler can exert Influence arbitrarily often. However, before your session in the Puzzle Forum, he randomly chooses a limit for how many times he will apply it for you (i.e. how helpful he will be :) ). The result is a secret; all you know is that the limit is some positive integer. Determine with proof the minimum number of questions which will allow you to identify which puzzler is which. ----- OK, so it's not much harder, but it's closer to how I originally envisioned the problem. New soln? Happy Puzzling! Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 18th, 2002, 1:16pm Eric, Here is where I use influence for my argument. Without influence, when you get to TTF-F, it is true that you cannot always distinguish between S'UN and SNU. If the answer is F, then you can be sure that the senior hasn't made a false post--if he has, he can't lie about it. However, if the answer is T, then you don't know if the senior made an incorrect post or not. All the uberpuzzler has to do is make sure that the senior puzzler never answers T, which is definitely within his mysterious uber-powers. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 18th, 2002, 1:55pm OK then; I absolutely agree that that works, I just didn't understand your original wording. Good job! Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 19th, 2002, 12:40am on 09/18/02 at 11:45:50, Eric Yeh wrote:
Yes, I listed only the places where the Uberpuzzler is forced to use influence in order to make the solution work. I noticed that along some paths, the newbie is never asked a question but the SR is, so influence is free to be used on the SR in those cases, but that neither helps nor hurts the solution. I suppose I should have been explicit about that. It's interesting that allowing influence to be used more than once breaks my solution. I was surprised to hear that. Hmm, let's see: U can uniquely determine the final states in a different way by influencing the SR on question 1 but not the newbie, then influencing (perhaps for the second time) on question 2a or 2b if the newbie or SR is asked. I'll think about the followup question you asked. Yeah, my followup was pretty obvious. I forgot that you said you had followups preplanned; this clearly would have been one of them! I'm doing better on that one with paper and pen than I was in my head, but haven't had time to work out the last case yet, and I don't have an insight about proving minimality. I have a feeling I'm not onto a minimal solution yet. |
||
|
Title: Multiple influence answer Post by TimMann on Sep 19th, 2002, 9:23am OK, answer to Eric's followup, where U decides in advance to use his influence a fixed positive number of times but doesn't tell you how many. Solution: 1) "A, is B the uberpuzzler?" If 1 is answered yes: 2a) "B, is A the newbie?" If yes, conclude NUS; if no, SUN. If 1 is answered no: 2b) "C, are you the uberpuzzler?" If 2b is answered yes: 3a) "C, is A the newbie?" If yes, conclude NSU; if no, SNU. If 2b is answered no: 3b) "A, is C the newbie?" If yes, conclude USN; if no, UNS. Discussion (less of a spoiler, but still a spoiler): First, note that there are only 6 possible outcomes to the questioning, and that the outcomes where all answers given are correct map 1-1 onto the arrangements. U can't eliminate any of the all-correct mappings by influence; he can only eliminate mappings where some answers are wrong. So if he can fix up this strategy at all, he can fix it up in only one way. (By that I mean that there is only once choice for the final mapping from outcomes to arrangements, not necessarily that there is only one choice in how he applies influence.) U can make this strategy work by applying influence whenever I ask a question of N or S. The strategy is then guaranteed never to address more than one question to other than U himself, so it works even if U decides to use influence only once. In fact, assuming U doesn't apply influence to himself (that would really give him a headache), U has only one opportunity to influence. This strategy is a lot simpler than my previous one, though less symmetrical. Also, it has minimal nodes, not just minimal quesions along the longest path. Interestingly, it doesn't make any use of the fact that S can answer incorrectly only once. I guess that was meant to be a red herring in the puzzle. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 19th, 2002, 10:50am Tim -- maybe if you wouldn't mind you could hide those last few paragraphs? Thanks -- more responses if I get some time. Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Chronos on Sep 19th, 2002, 11:44am Quote:
|
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 19th, 2002, 9:51pm Chronos, you seem to agree that U applying influence to himself isn't useful, so I don't see why you want to object to my saying that I assume he doesn't. If you want to quibble, though, your argument is not quite right. If you read the puzzle definition, it doesn't say that U's influence "cause[s] an answer to be right which might have been wrong before." It says that influencing someone will "clarify their thoughts so that they may answer any question correctly." (Of course, this would be more accurately worded as "clarify their thoughts so that their next answer will be correct".) At any rate, there is no statement that the answer might have been wrong without influence, so you can't exclude U influencing himself or another U by that argument. However, the puzzle statement does say "anyone else in the room", and that does imply that U can't influence himself. So you're right that I didn't need to state this assumption, but not for the reason you gave. 8) Of course it's also true that U influencing himself or another U would have no effect. That's a good reason for it not to be interesting in this context, but not a good reason why he can't do it. OK, I've quibbled enough now. No offense meant, by the way. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 20th, 2002, 6:17am Tim, I just checked your soln -- very nice! It is now almost precisely the same as mine -- except that 1) I apply s/Newbie/Senior Riddler/g (seniority has to buy you something, after all!!! and 2) I optionally provide a third question in the Yx cases, for those sticklers of definition (number of questions asked etc.). It's quite elegant, nein?? 8) It also leads me to wonder now whether or not the solution is actually unique (up to appropriate equivalence)! But it's been long enough that I don't recall my specific theory on it, and don't want to use the time to reconstruct it just now. :P So do you think the added rule oversimplifies the problem, then, or no? It sure seemed to help you simplify your soln fast!!! Perhaps allowing slightly more complex solutions like your first one would make it more challenging over all? On the other hand, I really like the slickness of this final solution. Anyone, comments?? on 09/19/02 at 21:51:04, TimMann wrote:
I take offense at this statement! ;) Ok ok, the "next" reference is actually a good point, I hadn't realized that potential unclearness before. However, the "may/will" change is superfluous!!! This is because I have already described the puzzler's truth profiles, and we know they are all honest. The change would perhaps be more "succinct", but not more "accurate", and in exchange, I lose the narrative style and realism conveyed by the fact that the Uberpuzzler cannot force someone to respond as he wishes (else he could force him to lie, too!), but rather only help them see the truth. It is then up to them to actually tell the truth (and luckily for us, they do!). :) Thanks for hiding the other spoiler per my request. And as always, thanks for your interest! Hope it wasn't too easy for you!!! ;) Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 20th, 2002, 6:19am HEY!!!!! What's going on with the colors??!!! How come 252525 isn't a perfect match any more??!!! |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 20th, 2002, 8:11am I see what you mean about may/will. Even remembering that everyone tries their best to answer honestly, I'd suggest changing the "may" to "can" for clarity. I think the way to make the puzzle most elegant would be to leave out the red herring of the senior riddler and just have two newbies, thus ruling out my first solution. I'm not sure if that would make it too easy, though. Perhaps it would, but now that I know the solution, it's hard for me to judge. The extra twist of having the uberpuzzler decide in advance how many times to influence but keeping it secret would not make the puzzle easier for a person seeing it for the first time, I think. Actually, it might make it harder, because it's one more thing to think about. I got the second solution quickly not so much because of that as because I'd already thought about the problem a lot. However, the extra twist is cumbersome to describe. And it kind of ends up being just another red herring, since in the solution, influence can be used only once. I guess it's a green herring, since it and the SR red herring cancel each other out. :D Hmm, here's another way to have a unique solution, without (I think) making the puzzle easier for people: Ask for the solution where the decision tree has minimal nodes, not just minimal questions along the longest path. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 20th, 2002, 11:15pm I have a 7-question solution for the puzzle variant without influence, but I don't know whether that's minimal. 1) "A, is B the senior riddler?" 2) "B, is C the senior riddler?" 3) "C, is A the senior riddler?" Due to the cyclic symmetry of the questions, if the three answers are not all the same, we only need to consider the case where A's answer was the odd one. So we have four cases: NNN, YNN, YYY, NYY. NNN: Possibilities are UNS, SUN, NSU. 4) "A, are you the uberpuzzler?" 5) (if yes) "A, are you really the uberpuzzler?" N: Possibilities are SUN, NSU. YN: Possibilities are S'UN, NSU. YY: Possibilities are UNS, NSU. In each of the above cases, one puzzler in particular is now known not to be the newbie. Call him Z. 6) "Z, are you the uberpuzzler?" 7) (if yes) "Z, are you really the uberpuzzler?" N or YN: Z is the senior riddler. Done. YY: Z is the uberpuzzler. Done. YNN: Possibilities are USN, S'UN, NSU. 4) "B, are you the uberpuzzler?" N: Possibilities are USN, NSU. B is now known to be the senior riddler. 5) "B, is A the uberpuzzler?" 6) "B, is A the uberpuzzler?" 7) "B, is A the uberpuzzler?" Believe whichever answer B gives a majority of the time. Y: Possibilities are US'N, S'UN, NS'U. Here we know that B must answer the rest of our questions correctly, so we can ask two more questions to finish up. YYY: Possibilities are US'N, NUS', S'NU. As with NNN, the three possibilities are the three cyclic permutations of one arrangement, so the solution for NNN will work here too, though we can ask fewer questions on some paths using our knowledge that S has already been wrong once. NYY: Possibilities are UNS', NUS', SNU. Here we know that C must answer the rest of our questions correctly, so we can ask two more questions to finish up. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 23rd, 2002, 8:05am Tim, Your solution can't be optimal, because my 5-question solution only relies on influence once, and that can be weeded out using one more question. Therefore, optimality needs at most 6 questions. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 23rd, 2002, 8:34am Agreed. (I'm not sure how to respond to these optimality questions; if I say "you can do better" it's a clue, and if I say nothing it could be misleading... Hmm.) |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 23rd, 2002, 9:38am Oh, right, I see what you mean there. I had glanced at your 5-question solution with influence, but I didn't look at it hard enough to understand how good the first question really is, so I aimlessly picked a question that looks similar but actually fails to gather all the information it could. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 23rd, 2002, 11:35am Let me know when someone comes up with a pf of optimality; I am eager to check whether there is a more elegant pf than my current one (which is decent but I could certainly imagine cleaner). :) Thanks, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 23rd, 2002, 12:22pm Eric, You just have to be picky, don't you... If my first questions are optimal, then I know for sure that you need 3 more questions. However, my first questions may not be optimal ... I just can't think of any better questions to ask. My questions seem logical, but everybody knows that puzzles aren't logical... |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 23rd, 2002, 12:32pm James, A search for a pf of optimality will likely clarify your thoughts sufficiently to either find a better soln, or convince yourself you are at an optimal level. Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 23rd, 2002, 1:12pm Eric, I was trying to find a better solution, and I had the following thought: can you force a senior riddler to answer incorrectly? For instance: "Puzzler A, will your answer to this post be 'no'?" By answering, the puzzler is answering incorrectly. The uberpuzzler would probably say "undecideable", and so you could immediately tell what puzzler A was: Uberpuzzler) "Undecideable" Sen. Puzzler) "Yes" (or "No", it doesn't matter) Newbie) "WTF? :-[" |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 23rd, 2002, 1:17pm James, Nope -- in all my riddles it is assumed that no contradictions are allowed. If you ever ask a question that has no answer, you are immediately ejected from the chamber. I sometimes think of the rule as "no self-referential questions." To be really complete, no referential questions of any sort are allowed. There is further discussion of these rules sprinkled across the forums for my three other currently-posted puzzles. Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 23rd, 2002, 2:04pm I was able to shave one question off of my previous best, so now I know that optimal sans influence is at most 5 questions. Still no real progress at a proof of optimality. If you know for sure that one person isn't the newbie, then you can solve the problem in only 3 questions (without any prior knowledge). If you don't know who the newbie isn't then you will waste some entropy on your next question. How to quantify this is still beyond me... |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 23rd, 2002, 9:49pm James, you beat me to it -- I thought of the 5-question solution after posting this morning but didn't have time to post again before going to work. As the solution is based on your initial question, though, it's only fitting for you to have first claim! I think this solution is optimal and will give an argument below. First, it seems best to write down the solution: Begin by asking each of A, B, C: "Is the person cyclically after you the newbie?" Due to cyclic symmetry and yes/no symmetry, there are only two really different cases: YYY (NNN is similar) and YNN (all others are similar). YYY: In any case where all the puzzlers answer a question the same way, we of course know this was both U's and S's answer. However, for the question above, U's answer and a correct answer by S are opposite, so S must have been wrong. Possibilities for YYY: UNS', S'UN, NS'U. We can now finish up in two questions as follows: "A, are you the uberpuzzler?" - Y eliminates S'UN, so we know C is either U or S'; ask "C, are you the uberpuzzler?". - N eliminates UNS', so we know B is either U or S'; ask "B, are you the uberpuzzler?". YNN: In this and the other cases where the puzzlers' answers are not all the same, we can't say whether S is wrong, but for each position U could be in, there is only one possible arrangement, and things nicely work out so that one person is known not to be N. Possibilities for YNN: UNS, NUS', SNU. Here C is known not to be N, so we can finish up by asking him twice "Are you the uberpuzzler?" YY implies he is; anything else implies he is not. (So of course we can stop after 4 questions if we hear N first.) Now an argument for optimality. 1. I argue that you can't do better than to address one of your first three questions to each puzzler. Your first question may have been addressed to N, there is no way you can tell that from his answer, and you obviously want to address as few questions to N as possible, so you should ask someone else your second question. Similarly, your first question may have been addressed to S and your second to N, or vice versa. There is surely no way to distinguish between those two cases just from the answers you get, since both S and N can answer their first question arbitrarily, so you'd better ask the third puzzler your third question to make sure you don't ask N two questions. 2. When you get done asking questions and have determined the order, you also know the following two incidental bits of information, both of which are independent of each other and of the order: (p) What was the random answer that N gave to his initial question? You know this since you know who N is now. (q) Was S mistaken in his answer to the initial question? You know this since you now know who S is, so you can compare the correct answer to the initial question you asked him with the answer he gave. (If at the end you don't always know the correct answer to the initial question you asked S, you must have asked him a question that was at least partly irrelevant. Therefore you wasted a question, and your solution can't have been optimal.) Thus you always know both p, q, and the arrangement at the end; in other words, you know 1 + 1 + log2 6 = 4.58 bits of information. You need at least 5 yes/no questions to get this much information, so 5 is a lower bound. We have a 5-question solution, so 5 is in fact minimal. This is just a tad handwavy in spots. I wonder what Eric's proof looks like? |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 24th, 2002, 6:09am I have proven optimality! Without influence, my (or Tim's)5-question solution is optimal. Read on for my analysis: Without loss of generality, the problem can be solved in 4 questions only if the following problem can be solved in 3 questions: NUS NSU S'NU S'UN USN In order to solve this in 3 questions, one question must reduce it to a problem solvable in 2 questions. Note that a 4-possibility problem is solvable in 2 questions iff one person is known reliable (known to be U or S'). If you ask the first person any question, one of the two answers will give at least 4 possibilities. However, person 1 could be a newbie due to NUS, and due to the NUS and NSU possibilities, both person 2 and person 3 could be the unreliable senior riddler. If you ask the second person any question, at least one of the the two answers will give at least 4 possibilities. Person 2, however, could be a newbie because of S'NU, and persons 1 and 3 could each be newbies due to NSU and USN. If you ask the third person any question, at least one of the two answers will give at least 4 possibilities. However, person 3 could be a newbie due to USN, person 1 could be a newbie due to NUS, and person 2 could be an unreliable senior due to USN. Therefore, no question you ask any of the three people in this stage can reduce the problem to be solvable in 2 questions. Therefore, the original problem is not solvable in 4 questions. Since we know it is solvable in 5 questions, then the optimal number of questions is 5. QED! |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 24th, 2002, 6:13am Tim, Nice go at it. Unfortunately, as you mentioned, there's a bit of handwaving that leaves me not quite convinced. ;) In particular, your (1) is not true. On first read, this was suggested to me intuitively twice: 1) You can get more info asking person 1 two questions, and 2) Your usage of the 2+xxx bits argument precisely demonstrates that you are potentially wasting some information... Food for thought. ;) Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 24th, 2002, 6:13am Bugger! I just figured out how to solve it in 4 questions! It turns out something was subtly wrong with my "proof" of optimality ... I guess what they say about Senior Riddlers is true ... :( |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 24th, 2002, 7:55am Heh, sounds like I was a lot more wrong than I thought I might be! |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 26th, 2002, 12:16am OK, now I'm really stumped. I can't find a 4-question solution, and I can't find anything wrong with James's later-disavowed proof that 5 is minimal. James, would you like to say more? |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 26th, 2002, 9:56am Tim, I couldn't find one either, but I was hoping that I could make Eric give a hint about his proof ... Obviously, he didn't, and I apologize for the time you spent looking for a solution that probably doesn't exist. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 26th, 2002, 10:54pm I guess you were just exercising your privilege of being wrong once a day. Illustrates the point that when S contradicts himself, you may have to ask another question to determine which of his answers was right. :) Anyway, I'm convinced your proof is correct, though a bit sketchy in giving justification for some steps. I didn't particularly understand it at first sight, but after looking hard for a shorter solution, I did. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 27th, 2002, 6:53am Heh. You are SO funny James. Ye, I suspected as much, based on your non-inclusion of the "new" soln in your post. Well, I figured it was either that, or just that you made a mistake that I would have to wait to identify. Indeed, my pf is substantially equivalent to yours. Upon your first post, I double-checked the equivalence, double-checked my pf, and double-checked your pf, and so was convinced that your new "soln" was in error (or a red herring). But in any case, nice job with the pf! Too bad I can't say the same about your questionable moral tactics ;) ;) Tim, What part of the pf did you find "sketchy"? Any disturbances we might be able to assuage? Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 27th, 2002, 9:06am on 09/27/02 at 06:53:25, Eric Yeh wrote:
Nothing that makes me doubt it. The first "without loss of generality" could use a couple of sentences to explain why we don't lose generality by considering only that case, but I understood it later. The answer to your first question (of course addressed WLOG to A) can't eliminate NSU or NUS, and at best it can change SUN and SNU to S'UN and S'NU. It could eliminate both UNS and USN, but if so, having gotten the opposite answer would eliminate neither, so you would need to be able to solve that case, and if you can't solve NSU NUS S'UN S'NU USN in n-1 questions, you certainly can't do the case where UNS is also possible. So no matter what question you ask, there will be at least one answer that leaves you with no more information than the case the proof looks at. The rest of it is clear enough. The reader has to check all the statements while reading, but that's OK. They all check out. All are mechanical except the little lemma that if you have 4 possibilities left, you can't finish in two questions unless you know one puzzler to be reliable. That's pretty obvious, though; you can't split the possibilities 2/2 if the puzzler you question could give either answer in one of the possibilities. (edited to fix typos) |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 27th, 2002, 9:30am Ye, I agree with all your statements. You certainly have to continue checking along the way, and the 4 choice lemma and intial WLOG do require a little thinking at first exposure; I guess I was used to them bc I have thought about this kind of thing before, so kinda just accepted them both naturally. But you're definitely right that there is something of substance behind each. Best, Eric |
||
|
Title: 2084: A Dystopian Puzzle Forum Post by James Fingas on Sep 27th, 2002, 9:47am 2084: A Dystopian Puzzle Forum Scene: A long time from now, in a puzzle forum far, far away ... An old and wizened Uberpuzzler, Joda, gives instruction to his apprentice... U: My young apprentice, come and listen. Today to you, I give your first task. A: But master, I have solved many puzzles! U: Young you are, and the true calling of Uberpuzzlers you do not realize. Today, you shall go and interact with other puzzlers in the Puzzle Forum! A: Yes, master--but what is my task? U: I will send you into a topic, in which participate three puzzlers. Their identities you must determine. A: I will ask them three questions, giving 3 bits of information. There are only six possible permutations, so that ... U: Young you are, and the ways of the world you understand not. Knowledgeable these puzzlers are, but dishonest! A: Master Joda, I do not have your Uberpuzzler powers! If I cannot trust their answers, I cannot deduce their identities! U: Uberpuzzler powers you need not--only knowledge of your enemy. One of these three is a Pathopuzzler. To every question, he gives an incorrect answer. Another is a Meta-Newbie. In every discussion, he gives an even number of incorrect answers. The last puzzler is the most dangerous of the three. He is a Jaded Senior Puzzler. Mostly truthful he is, but exactly once in every discussion, untruthful! A: That cannot be true! What if I were to ask him no questions? Then he could not be untruthful! U: Naive you are! I ask you: do you know who is the Jaded Senior Puzzler? A: No, not yet. U: Then how will you avoid asking him a question? A: There's only a 1/3 probability that the first person I ask is ... U: Do not argue of probabilities with an Uberpuzzler! If no questions you ask, a discussion there is not! If questions you do ask, some you will ask to the Jaded Senior Puzzler. A: But that violates the law of causality! And so does the Meta-Newbie! U: A story I will tell you. A long time ago, in a Puzzle Forum far, far away, the first Uberpuzzler was made. Great powers did he posess, the same powers that all Uberpuzzlers have inherited from that day forth. But the ramifications of his powers, he did not understand. Overuse his powers he did, and the psyches of many young puzzlers he damaged. Strange powers also did they develop, and great knowledge, but their powers are uncontrolled. Such are the powers of the puzzlers you will face. Now it is time to confront the enemy. Go now! A: But what if I can't tell who is who? U: It is better to have puzzled and failed, then never to have puzzled at all. A: Yeah, yeah ... <A few minutes elapse> A: I did it! I figured out their identities! U: Ah, and a minimal question-set you have used. Very good! What did the apprentice ask, to reveal their identities? |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 27th, 2002, 10:27am ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D Omigosh, that was funny! Here's my answer. Is it minimal? "A, is B the pathopuzzler?" Y: JMP N: JPM Done. Extra space hidden to obscure the shortness of the answer! |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Jonathan_the_Red on Sep 27th, 2002, 10:53am Tim, I like your answer, but that might violate causality just a wee bit too much :) Here's mine: Resolve at the beginning to ask one and only one question of each puzzler. That way causality is not violated: the Pathopuzzler and Jaded Senior Puzzler will lie, while the Meta-Newbie will tell the truth. A set of questions that works is: A: Is B the Pathopuzzler? B: Is C the Jaded Senior Puzzler? C: Is A the Meta-Newbie? JPM : N Y N JMP : Y N Y PMJ : Y Y Y PJM : Y Y N MPJ : Y N N MJP : N N N edit apparently, Tim's solution is what was intended... oh well :) |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 27th, 2002, 10:54am Tim, Your answer may seem minimal, but right-minded individuals like Eric and I will only be convinced by a proof. And make it a good one! The puzzle started off with the realization that the rules for the puzzlers are largely arbitrary, but I found the final solution interesting ... I hope it wasn't too blindingly obvious! |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 27th, 2002, 2:09pm VERY VERY amusing James!!!!! I am esp won over by the use of my quote near the end!! :D :D :D Tx! (The question itself, though quick, is interesting, too! :D ) Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 27th, 2002, 10:26pm I'm sure you're just kidding about demanding a proof, but I'll write one out anyway. :D If we take the U's statements as axiomatic, then no matter what questions you ask of whom during a discussion, the JSP always answers exactly one question wrong. Perhaps the JSP has psychic powers that force you to ask one of your questions of him no matter what you had planned -- or perhaps his powers are even more far-reaching -- but all this belongs to the realm of physical or psychical speculation, not mathematical proof. We are merely given that the JSP always gives one wrong answer in every discussion. Therefore, if we ask "A, is B the PP?" and end the discussion, the answer we receive must come from the JSP, and it must be wrong. Therefore Y->JMP, and N->JPM. Let me close by observing that my solution is minimal for A, but most likely not for U. As we read, "Master Joda, I do not have your Uberpuzzler powers!" Undoubtedly Joda could sense the location of the JSP using no questions at all, but merely by sensing the disturbance he caused in the Farce.... Um, I mean the Force. Here's a followup question (really). Can the apprentice solve the puzzle in exactly N questions for any given N? (edited: I know the answer to this followup now.) |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 27th, 2002, 10:36pm p.s. Seriously, it wasn't quite blindingly obvious. Somehow, even though I realized right away that if you ask only one question, the JSP has to be the one who answers, it took me a few more minutes of thought in the shower afterward to realize that you could then use the information in his known-wrong answer to finish the puzzle. D'oh. Oh, here's another followup. Suppose the apprentice walks into the room, shakes hands with the first puzzler he sees, and absentmindedly says, "Good morning! Did you sleep well last night?" Counting this as one of the questions, how many questions will it take the apprentice to identify who is who? |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 29th, 2002, 11:52am on 09/27/02 at 22:26:09, TimMann wrote:
Yes. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 29th, 2002, 11:54am on 09/27/02 at 22:36:30, TimMann wrote:
Two. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 29th, 2002, 2:24pm Eric, I agree with your answer to the first followup I asked. Partial spoiler: For n>2, you just ask the first puzzler the question from the 1-question solution over and over, and believe the answer that he gives more than once. For n=2 you need a custom solution, but it's easy to find. On the second one, though, I don't see how you can do it in so few questions, unless perhaps you're limiting the JSP's powers by some assumption about causality. I.e., are you assuming that if the apprentice asks the JSP two questions, the JSP has to be wrong on the first because he doesn't know for sure that the apprentice will ask another question? I haven't been assuming that. I've been assuming the puzzlers know the apprentice's strategy ahead of time, then choose who is who and when each one will answer wrong, in a way that's sufficient to meet the conditions stated by Joda, but no more. |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 29th, 2002, 9:45pm Nope, I am making no such assumptions. ;) The rules I have followed are the same as the ones you listed. Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by TimMann on Sep 29th, 2002, 10:05pm Oh, I see: Address the same guy again and say, "Did you sleep well last night XOR is this guy on your right the PP?" I bow to the Uberpuzzler! ;) |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by Eric Yeh on Sep 30th, 2002, 7:25am Precisely. ;) Nice puzzles by the way! Best, Eric |
||
|
Title: Re: NEW PROBLEM: THE PUZZLE FORUM Post by James Fingas on Sep 30th, 2002, 12:17pm Tim, When I said we needed a proof, I didn't mean a proof that the solution works ... that should be self-evident! I meant a proof that it's an optimal solution. ;) |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |