wu :: forums
« wu :: forums - NEW PROBLEM: THE PUZZLE FORUM »

Welcome, Guest. Please Login or Register.
Aug 18th, 2019, 2:06am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, Grimbal, SMQ, towr, Icarus, william wu, ThudnBlunder)
   NEW PROBLEM: THE PUZZLE FORUM
« Previous topic | Next topic »
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: NEW PROBLEM: THE PUZZLE FORUM  (Read 8113 times)
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
NEW PROBLEM: THE PUZZLE FORUM  
« on: Sep 9th, 2002, 5:56pm »
Quote Quote Modify Modify

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!!!  Wink )
 
-----
 
THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM THE PUZZLE FORUM 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.  Wink ]
 

 
-----
 
As usual, I suggest no computers!!  Let me know if anything is unclear!  There are also follow-up questions!  Wink
 
Happy Puzzling,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
AlexH
Full Member
***





   
Email

Posts: 156
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #1 on: Sep 9th, 2002, 7:00pm »
Quote Quote Modify Modify

Haven't even started to think about this one, but very cool puzzle  Cheesy
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #2 on: Sep 9th, 2002, 7:08pm »
Quote Quote Modify Modify

Thanks -- fellow uberpuzzler!!!!!   Wink  Wink  Wink
« Last Edit: Sep 9th, 2002, 7:09pm by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #3 on: Sep 16th, 2002, 10:54am »
Quote Quote Modify Modify

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...
 
IP Logged

Doc, I'm addicted to advice! What should I do?
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #4 on: Sep 16th, 2002, 12:27pm »
Quote Quote Modify Modify

<< Wiped out for clarity -- I didn't think I did but somehow this message seemed to be double-posted!! >>
« Last Edit: Sep 16th, 2002, 2:13pm by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #5 on: Sep 16th, 2002, 12:30pm »
Quote Quote Modify Modify

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.  Tongue
 
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??!!!  Wink  Wink  Wink
 
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.  Wink  Wink  Wink  Well, that, or the puzzle didn't turn out as well.  Wink
 
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
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #6 on: Sep 16th, 2002, 2:02pm »
Quote Quote Modify Modify

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.
IP Logged

Doc, I'm addicted to advice! What should I do?
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #7 on: Sep 16th, 2002, 2:29pm »
Quote Quote Modify Modify

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  Smiley
 
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!!!  Wink  You know, a la "Yes, you are a Newbie."  Wink  JK.
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #8 on: Sep 17th, 2002, 9:54am »
Quote Quote Modify Modify

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.
« Last Edit: Sep 17th, 2002, 9:57am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #9 on: Sep 17th, 2002, 10:59am »
Quote Quote Modify Modify

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
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #10 on: Sep 17th, 2002, 11:55pm »
Quote Quote Modify Modify

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.  Cheesy
 

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.
« Last Edit: Sep 18th, 2002, 12:01am by TimMann » IP Logged

http://tim-mann.org/
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Followup question  
« Reply #11 on: Sep 18th, 2002, 12:17am »
Quote Quote Modify Modify

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.
 
 
 
IP Logged

http://tim-mann.org/
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #12 on: Sep 18th, 2002, 6:26am »
Quote Quote Modify Modify

Hey, good for you Tim!!  This was precisely one of my follow-ups that I mentioned in my first msg!!!  Smiley  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.
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #13 on: Sep 18th, 2002, 11:36am »
Quote Quote Modify Modify

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.
IP Logged

Doc, I'm addicted to advice! What should I do?
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #14 on: Sep 18th, 2002, 11:45am »
Quote Quote Modify Modify

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.
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #15 on: Sep 18th, 2002, 12:35pm »
Quote Quote Modify Modify

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!  Smiley
 
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!!!!!
« Last Edit: Sep 18th, 2002, 12:37pm by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #16 on: Sep 18th, 2002, 1:11pm »
Quote Quote Modify Modify

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  Smiley ).  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
« Last Edit: Sep 18th, 2002, 1:12pm by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #17 on: Sep 18th, 2002, 1:16pm »
Quote Quote Modify Modify

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.
IP Logged

Doc, I'm addicted to advice! What should I do?
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #18 on: Sep 18th, 2002, 1:55pm »
Quote Quote Modify Modify

OK then; I absolutely agree that that works, I just didn't understand your original wording.
 
Good job!
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #19 on: Sep 19th, 2002, 12:40am »
Quote Quote Modify Modify

on Sep 18th, 2002, 11:45am, Eric Yeh wrote:

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.

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.
 
IP Logged

http://tim-mann.org/
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Multiple influence answer  
« Reply #20 on: Sep 19th, 2002, 9:23am »
Quote Quote Modify Modify

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.

 
« Last Edit: Sep 19th, 2002, 9:22pm by TimMann » IP Logged

http://tim-mann.org/
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #21 on: Sep 19th, 2002, 10:50am »
Quote Quote Modify Modify

Tim -- maybe if you wouldn't mind you could hide those last few paragraphs?
 
Thanks -- more responses if I get some time.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Chronos
Full Member
***





   
WWW Email

Gender: male
Posts: 288
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #22 on: Sep 19th, 2002, 11:44am »
Quote Quote Modify Modify

Quote:
...assuming U doesn't apply influence to himself (that would really give him a headache)
I don't even see how U can apply influence to himself (or even to another U, should one be present).  Remember, even aside from Influence, an Uberpuzzler never answers wrong, and all that Influence does is cause an answer to be right which might have been wrong before.  Even if we allow for Influence to make U redundantly right, so to speak, doing so does not in any circumstance help the questioner, and we've already established that U is trying to use his Influence to help the questioner.
IP Logged
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #23 on: Sep 19th, 2002, 9:51pm »
Quote Quote Modify Modify

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. Cool
 
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.
« Last Edit: Sep 19th, 2002, 10:33pm by TimMann » IP Logged

http://tim-mann.org/
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: THE PUZZLE FORUM  
« Reply #24 on: Sep 20th, 2002, 6:17am »
Quote Quote Modify Modify

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??  Cool
 
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.  Tongue
 
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 Sep 19th, 2002, 9:51pm, TimMann wrote:
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".)

I take offense at this statement!  Wink  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!).  Smiley
 
Thanks for hiding the other spoiler per my request.  And as always, thanks for your interest!  Hope it wasn't too easy for you!!!  Wink
 
Best,
Eric
« Last Edit: Sep 20th, 2002, 6:18am by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board