Author |
Topic: NEW PROBLEM: The Operators of Boolania (Read 3405 times) |
|
TimMann
Senior Riddler
Gender: 
Posts: 330
|
 |
Static backward, etc.
« Reply #25 on: Sep 12th, 2002, 11:48pm » |
 Quote  Modify
|
On the static solution to Backward, it was pretty easy to come up with one. Mine turned out to be similar in structure to Jonathan's, as you suggested it must be:
Ask of the leftmost guy:
1) Are you AND?
2) Is XOR leftward of OR? (note: not next leftward cyclically)
3) Is AND in the middle?
AOX YNN
AXO YYN
OAX NNY
OXA NNN
XAO NYN
XOA NYY
Note that you have the opportunity to get some extra information. Since these guys are omniscient, you might as well change question 3 to "Is either of the following true? (a) AND is in the middle, or (b) you are AND and Willywutang wears boxer shorts." If you luck out and the arrangement is AXO, you can find out about Willy's underwear, or any other deep secret of the universe you care to ask about.
The design prinicple I used in the above was to avoid making AND say no or OR say yes until I no longer needed any more information, since their giving those answers "pegs" their answers afterward. It looks like Jonathan was doing that too. In fact, he actually avoiding having AND say no or OR say yes until the last question.
However, you don't really have to do that at all:
Ask of the leftmost guy:
1) Is AND leftward of XOR?
2) Is OR leftward of XOR?
3) Is OR leftward of AND?
AOX YYN
AXO YNN
OAX YYY
OXA NYY
XAO NNN
XOA NNY
Notice that OR says yes to question 1 in the OAX case, so he's pegged at "yes" thereafter, but we get enough information to solve the puzzle anyway. I'm sure you can also construct a solution where OR gets pegged to YYY in one case and AND gets pegged to NNN in another.
The above solution has a different cute property, though. Can you see what it is? (Spoiler: Every answer given is always the correct answer to the question being asked. That is, you'd get the same results if AND, OR, and XOR all forgot to apply their namesake operations and simply answered the questions at hand!)
By the way, since my previous dynamic solution was static in who it asked each question of, there's a mechanical way to convert it to fully static by putting the conditions into the questions themselves instead of into the procedure for deciding what to ask. But that would make an unwieldy solution.
Finally, since these solutions are fully static and involve talking to only one god (like Jonathan's did), that of course establishes the lower bound for min answerers in static solutions.
|
|
 IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Selfless minimum answerers
« Reply #26 on: Sep 13th, 2002, 1:56am » |
Quote Modify
|
Here's a way to show the minimum number of distinct answerers for static Selfless:
Ask the leftmost guy:
1) Is grass red?
2) Is XOR not the rightmost?
3) Is the order not XOA?
seating true given
order answers answers
------- ------- -------
AOX nny NNN
AXO nyy YNN
OAX nny YYN
OXA nyy YYY
XAO nyy NYY
XOA nyn YNY
Thus 1 is the minimum number of distinct answerers.
There may be a more elegant set of questions, but I got tired. I still like my previous solution better: it has a minimal number of distinct questions. 
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #27 on: Sep 13th, 2002, 6:13am » |
Quote Modify
|
have very little time -- but took a glace. why does anyone answer Y to "is grass red?"??!
e
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #28 on: Sep 13th, 2002, 10:00am » |
Quote Modify
|
Here's a "perfect" answer to Universal. Yep... static questions, asking one God. Really.
For 1 <= n <= 3, let N be the proposition: "I am currently asking question #n" (this is the secret!) Let O be the proposition: "You are not OR."
Note that "not-N implies O" is true if you're asking question n. If you're not asking question n, "not-N implies O" is true if you're speaking to AND or XOR, but false if you're asking OR.
Let P be any proposition. You can then ask: "Does N imply P and does not-N imply O?" and get a truthful answer to P. Suppose for the three questions, you'll use propositions P1, P2, and P3. When you're asking question 1, this becomes
P1 AND TRUE AND TRUE for AND,
P1 XOR TRUE XOR TRUE for XOR,
P1 OR FALSE OR FALSE for OR
... all of which are equivalent to P1.
So the problem reduces to the easy task of finding three static questions that will produce unique answers for the six possible arrangements. One such arrangement that works is:
Are you AND?
Are you OR?
Is XOR next cyclically left of AND?
|
|
IP Logged |
My arcade cabinet
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #29 on: Sep 13th, 2002, 9:06pm » |
Quote Modify
|
on Sep 13th, 2002, 6:13am, Eric Yeh wrote:| have very little time -- but took a glace. why does anyone answer Y to "is grass red?"??! |
|
They don't, of course. As the middle section of the table shows, the correct answer to "is grass red?" is always no. This doesn't keep the solution from working, because the gods don't answer the questions p, q, r that you ask them. They answer questions like p AND q, q OR r, p XOR s, etc. -- as you know very well, of course!
|
| « Last Edit: Sep 13th, 2002, 9:19pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #30 on: Sep 13th, 2002, 9:17pm » |
Quote Modify
|
on Sep 13th, 2002, 10:00am, Jonathan_the_Red wrote:| Here's a "perfect" answer to Universal. Yep... static questions, asking one God. Really. |
|
Neat, another kind of dynamic binding. I only considered the binding of "you" to "the god I'm talking to as I ask this question". I never thought about "the number of the question I'm currently asking" as a dynamic element that would be substituted into the other two questions as well as the one I'm actually currently asking. I think I failed to think in this direction because of the warning against paradoxes, which rules out things like references to "the next question" or "your answer to this question", etc. -- but what you've done doesn't cause a paradox. I like it. I wonder if Eric thought of that. 
|
| « Last Edit: Sep 15th, 2002, 11:08pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #31 on: Sep 16th, 2002, 11:58am » |
Quote Modify
|
on Sep 13th, 2002, 9:06pm, TimMann wrote:
They don't, of course. As the middle section of the table shows, the correct answer to "is grass red?" is always no. This doesn't keep the solution from working, because the gods don't answer the questions p, q, r that you ask them. They answer questions like p AND q, q OR r, p XOR s, etc. -- as you know very well, of course!
|
|
Tim,
Ye, I read your two posts too quickly, I suppose -- I didn't notice the transition from the Backward case to the Selfless case.
I certainly agree w most of your reply #25 -- as usu there are wasted part-bits, but it is rare to not have those (as per Knight, Knave, Random). I could have had them speak Gibberish to save an additional .1335 of a bit, but to me it's not quite worth it as a tradeoff for the character of the puzzle.
Yes, you can do the "pegging", as you call it, to the response sets other than the ones which allow continually meaningful responses, but I have yet to see one that I consider elegant, or even intuitively constructed. (I agree that your "cute property" is cute, but not necessarily intuitive  )
Lastly, yes, I agree the mechanical conversion is possible but unwieldy. Like I said in the beginning of this topic, this particualr set of puzzles is very much about elegance.
Regarding your reply #26, nice job! Out of curiosity, was there a method to the madness?
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #32 on: Sep 16th, 2002, 12:12pm » |
Quote Modify
|
on Sep 13th, 2002, 10:00am, Jonathan_the_Red wrote:Here's a "perfect" answer to Universal. Yep... static questions, asking one God. Really.
|
|
Jonathan,
With no slight intended toward the cleverness of your solution (which there certainly is! ), this kind of solution was to me, as Tim mentioned, off-limits.
The general rule I in my mind is that questions cannot be self-referential in any sense, and this includes in the sense of the timing of the questions. For example, we would not want to allow PPF questions to directly involve "when they are being answered". Another point is that this kind of solution requires a sort of "implementation-dependent" assumption regarding how the gods "hear" and "interpret" the questions. One could imagine a PPF-like world where the gods live out-of-phase with human perception of time, in which case phrases such as "the question I am currently asking" would not make sense.
In any case, I appreciate both your interest in my puzzle and your clever solution to it, be it outside the intended bound or not. So I certainly mean no offense, and hope none is taken!
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 Operators of Boolania
« Reply #33 on: Sep 16th, 2002, 9:08pm » |
Quote Modify
|
on Sep 16th, 2002, 11:58am, Eric Yeh wrote:
Regarding your reply #26, nice job! Out of curiosity, was there a method to the madness?
|
|
I started out by making a list of the possible reply sequences that could be given by each god if he happened to be the one you asked. XOR's 3rd answer has to be the XOR of his first two answers, AND can't say yes exactly once, and OR can't say no exactly once. I assigned feasible response sequences to orderings in what seemed a likely way, then played around looking for questions that would generate those responses, mostly working from the top of the table to the bottom, and sometimes switching around the response sequences when it looked like what I was trying wouldn't work. I came up with something that worked before long. It was not pretty, but I was tired, so I typed it in and went to bed.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: The Operators of Boolania
« Reply #34 on: Sep 17th, 2002, 5:24am » |
Quote Modify
|
Well, good job! Ye, the first half of your analysis (re: A&O) is exactly like mine. (I got a little extra structure out of it by placing a further condition on X, but that was not as important.)
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print