Author |
Topic: NEW PROBLEM: THE PUZZLE FORUM (Read 9672 times) |
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
 |
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #25 on: Sep 20th, 2002, 6:19am » |
 Quote  Modify
|
HEY!!!!! What's going on with the colors??!!! How come 252525 isn't a perfect match any more??!!!
|
|
 IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #26 on: Sep 20th, 2002, 8:11am » |
Quote Modify
|
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. 
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #27 on: Sep 20th, 2002, 11:15pm » |
Quote Modify
|
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.
|
| « Last Edit: Sep 20th, 2002, 11:15pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #28 on: Sep 23rd, 2002, 8:05am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #29 on: Sep 23rd, 2002, 8:34am » |
Quote Modify
|
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.)
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #30 on: Sep 23rd, 2002, 9:38am » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #31 on: Sep 23rd, 2002, 11:35am » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #32 on: Sep 23rd, 2002, 12:22pm » |
Quote Modify
|
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...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #33 on: Sep 23rd, 2002, 12:32pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #34 on: Sep 23rd, 2002, 1:12pm » |
Quote Modify
|
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?  "
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #35 on: Sep 23rd, 2002, 1:17pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #36 on: Sep 23rd, 2002, 2:04pm » |
Quote Modify
|
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...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #37 on: Sep 23rd, 2002, 9:49pm » |
Quote Modify
|
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?
|
| « Last Edit: Sep 23rd, 2002, 9:49pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #38 on: Sep 24th, 2002, 6:09am » |
Quote Modify
|
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!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #39 on: Sep 24th, 2002, 6:13am » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #40 on: Sep 24th, 2002, 6:13am » |
Quote Modify
|
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 ... 
|
| « Last Edit: Sep 24th, 2002, 6:14am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #41 on: Sep 24th, 2002, 7:55am » |
Quote Modify
|
Heh, sounds like I was a lot more wrong than I thought I might be!
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #42 on: Sep 26th, 2002, 12:16am » |
Quote Modify
|
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?
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #43 on: Sep 26th, 2002, 9:56am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #44 on: Sep 26th, 2002, 10:54pm » |
Quote Modify
|
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.
|
| « Last Edit: Sep 26th, 2002, 10:59pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #45 on: Sep 27th, 2002, 6:53am » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #46 on: Sep 27th, 2002, 9:06am » |
Quote Modify
|
on Sep 27th, 2002, 6:53am, Eric Yeh wrote:
What part of the pf did you find "sketchy"? Any disturbances we might be able to assuage? |
|
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)
|
| « Last Edit: Sep 27th, 2002, 10:03am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #47 on: Sep 27th, 2002, 9:30am » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
 |
2084: A Dystopian Puzzle Forum
« Reply #48 on: Sep 27th, 2002, 9:47am » |
Quote Modify
|
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?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: THE PUZZLE FORUM
« Reply #49 on: Sep 27th, 2002, 10:27am » |
Quote Modify
|
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!
|
| « Last Edit: Sep 27th, 2002, 10:27am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print