4
$\begingroup$

I came along this puzzle somewhere it a logic-related lecture:

  • There are two prizes: Prize A and prize B.

  • When you make a true statement, then you win prize A.

  • When you make a false statement, then you do not win prize A

  • What do you have to say in order to win prize B?

The solution, for those who struggle with it:

You have to say: "I will not win any prize" (or alternative formulations, like "I will win neither A nor B")

It's easy to show that this solution is "correct". It's also easy to explain why it is correct, and that it's "the only one that is possible". It's easy to make reasonable statements about the solution in hindsight.

Please do not post answers that only explain the solution!

This question is obviously not about the solution itself, but about how to find the solution - and not only about how to find it, but about how to find it systematically.

I'm not sure whether the solution cannot be derived with plain first- or even second order logic. The main caveat here seems to be that the problem description contains a statement about a statement that is not made yet (namely the statement that the answerer will make).

Some (very) basic thoughts:

One could define:

  • $A$ = I will win prize A
  • $B$ = I will win prize B
  • $S$ = The statement that has to be made

Then the problem description is

  • $S \to A$
  • $\neg S \to \neg A$

But that's naive and does not bring any progress (as it does not involve $B$ in any way)

One could try to start with the truth table of the possible outcomes:

  • $\neg A$ $\neg B$
  • $A$ $\neg B$
  • $\neg A$ $B$
  • $A$ $B$

and somehow argue that one has to achieve one of the two last combinations. But there's this chicken-egg problem that the outcome will depend on the statement that one is just about to derive...

I also wondered whether the "Winning" can be part of the variable (that's where higher order logic might come into play). Maybe it would be necessary to define

  • $w(X)$ = I will win prize X
  • $s(A, B)$ = The statement to find (about everything that exists in the universe: A and B)
  • $s(A, B) \to w(A)$ : For a true statement, one wins A
  • $\neg s(A, B) \to \neg w(A)$ : For a false statement, one does not win A

but (maybe due to my lack of familiarity with higher-order logic), I don't see how one could strictly mathematically and systematically derive the solution

$s(A, B) = \neg w(A) \land \neg w(B)$

from that.

I always end up with arguing like "this must be the solution, because I know that this is the only solution that works".

Does anybody have hints or ideas that would undoubtedly work even if the solution was not known beforehand?

Update

There are several answers now. While they are interesting and helpful, I cannot say that any of them is perfectly satisfactory. (This does not say anything about the answers per se, but maybe just about my ability to understand them - no offense!). All of the current answers seem to rely on several assumptions, which "turn out to be true", but seem to be hard to justify in the first place. I'll try to explain my doubts:

Doubt 1:

As mentioned in my third approach above, the "universe" for this setup seems to consist of two elements - namely the prizes A and B. So one might assume that the solution has to involve statements solely about these two elements. Particularly, the assumption would be

  • that "winning" can be encoded in a way that $A$ just means "I will win A" (formally: That the statement will consist of first-order logic)
  • or that a statement about $A$ and $B$ will be sufficient (formally: That the statement will be a simple second-order logic predicate like $s(A, B)$)

But I wonder how this is justified. For example, the necessary statement could also be something like this:

"If the condition for winning prize A referred to prize B, and my statement was false, then not winning B would cause a contradiction to the condition for not winning prize A"

This is just intended as an overly complex example, showing that the "statement" might not only be about winning A or B, but also about the rules of the game, or (self-referentially!) about the statement itself. The point is: When looking at the problem description initially, one cannot be sure that something like this will not be ncessary...

Doubt 2:

Many arguments in the current answers are aiming at finding a paradox/contradiction. While this does indeed yield a solution (and, as ffao mentioned in his answer, could even lead to "trivial" solutions), there does not seem to be a reason to assume this.

There is no statement about "winning B" in the problem description. So it certainly sounds reasonable to say: "In order to cover B in any way, I have to make a statement about B", and consequently, "I have to make a statement that is contradictory when I don't win B". But I still don't see a way to find the right statement systematically.

A slight variation:

As ffao pointed out, there may be several possible solutions. Now, imagine (just for the sake of the argument) that the problem description had contained the additional rule:

  • You may not say that you will win neither A nor B

Iff (if and only if) I understood the answers correctly, then, as as ffao said, the statement

"I will not get exactly one prize"

would then still have been a valid solution - but this would not have been found with the methods that have been described in any of the other answers.

(Another remark: Back when I was first confronted with this, I wondered whether it was possible to write a Prolog program to solve this - that is: An algorithm...)

Improve this question
$\endgroup$
8
  • $\begingroup$ I edited your title to make it a bit more descriptive and specific. Feel free to rollback (or edit to some more succinct middle ground) if you think that makes it stupidly long. $\endgroup$
    – Rand al'Thor
    Apr 21, 2017 at 22:48
  • $\begingroup$ @randal'thor Yes, I hesitated with the title and how many details it should contain. It's hard to summarize the question succinctly. (I also considered some "clickbaiting title", like "Learn how to win a prize!!!" - but then resorted to the neutral one). The edit is fine for me. $\endgroup$
    – Marco13
    Apr 21, 2017 at 23:07
  • 1
    $\begingroup$ The three rules that set up the scenario do not indicate that there is a way to win prize B, just that there is a way to win or lose prize A. If your intention is that one prize must be won, I recommend you stating so in the rules, or else there is literally no statement you can make to guarantee that you win prize B. $\endgroup$
    – Ian MacDonald
    Apr 22, 2017 at 2:42
  • $\begingroup$ @IanMacDonald That's the crux. There is a statement that can be made to win prize B (because every other statement would cause a contradiction to the given rules). The question is: How to systematically (mathematically) derive this statement? $\endgroup$
    – Marco13
    Apr 22, 2017 at 14:56
  • 2
    $\begingroup$ No, there isn't. Any statement you make can still result in the officials replying "the rules do not allow you to win prize B, only to win or not win prize A. Prize B is, in fact, not in the list of things you can win". Your assumption means that there could be a statement that wins you all of the money in the world, even though the contest doesn't indicate that's an option. $\endgroup$
    – Ian MacDonald
    Apr 23, 2017 at 3:04

5 Answers 5

Reset to default
4
$\begingroup$

I like systematically explaining solutions to puzzles, so let's give this a shot.

We can tell immediately that the solution is likely to be some statement involving the winning or otherwise of one or both of the prizes. It's not going to be some irrelevant statement, because then you could just not win B without violating any of the conditions. It must be something to do with the prizes themselves, so that you force the prizegiver's hand.

OK, so it must be some logical function of the statements X: "I will win prize A" and Y: "I will win prize B". Clearly X is the statement which links back to the given conditions and Y is the statement which links to the desired result; our solution should somehow bridge the gap between these. The function could be something simple like X and Y or something more complicated like if X, then not Y, but it must depend somehow on these two basic statements.

Once we've got that far, it becomes a matter of trial and error: start from the most basic statements and work our way up the complexity level until we get to something that works. The simplest things to start with are the and/or combinations of X, ¬X, Y, and ¬Y; going through each of these in turn, we'll sooner or later reach ¬X and ¬Y and find that it works as required.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks so far, but ... maybe I should have emphasized the word systematically even more than I already did ;-) The argument in the first paragraph sounds convincing (as the solution will likely not be a statement like "My pants are wet"). I already tried to tackle this in my third approach: The "universe" in this setup mainly consists of the prizes, so the statement would likely be of the form s(A,B). But the universe also contains "meta-objects" like the player and the quiz itself, and the statements that are related to the quiz. (Continued...) $\endgroup$
    – Marco13
    Apr 21, 2017 at 23:00
  • $\begingroup$ (Continued...: ) What makes you sure that the statement will not be something like: "If the condition for winning prize A referred to prize B, then I could make an arbitrary true statement to win". (This is just intented as an example - it would be complicated to analyze this...). Your second paragraph is in line with my s(A,B) approach. But the last paragraph is where I also always ended up: Some trial and error. I was actually looking for a way that does not involve trial and error... $\endgroup$
    – Marco13
    Apr 21, 2017 at 23:01
  • $\begingroup$ (To be clear: The trial and error here only involves "all combinations from the truth table", so this would not be the most important issue. More important here is the fact that this already makes the assumption that searching the truth table will yield a solution) $\endgroup$
    – Marco13
    Apr 21, 2017 at 23:03
  • 1
    $\begingroup$ @Marco13 Perhaps "trial and error" is the wrong word: what we're doing here is going systematically through a countable set of possibilities until we find the solution. The solution should be some logical function of X and Y, so we'd start with the simplest possibilities and work our way upwards and outwards from there, eventually passing through much more complicated statements such as, I dunno, "if the statement $X\Rightarrow Y$ were true, then Y is false". We're just lucky that a valid solution comes relatively quickly in this process. $\endgroup$
    – Rand al'Thor
    Apr 21, 2017 at 23:51
  • $\begingroup$ I tried to summarize some of the comments here in a small "update" for the question. $\endgroup$
    – Marco13
    Apr 22, 2017 at 19:48
2
$\begingroup$

Actually, unlike stated in the question, there are three different solutions to this problem1. For a way to get those three solutions, which might or might not be systematic enough to your taste:

First, we need to know which variables are interesting for our statement -- variables that are not affected by our statement can just be treated as constants since they always assume one value no matter what the statement is. For this problem, those variables are $A$ (I will win prize A) and $B$ (I will win prize B).

Now, we can see that we do not want the possibility that $\neg A \neg B$, or $A \neg B$. The only way we have to restrict those possibilities is using the two implications given in the statement: $\neg A \to \neg S$ and $A \to S$ (or $S=A$, to simplify). So, to create a paradox out of $\neg A \neg B$, we need $\neg A \neg B \to S$, and to create a paradox out of $A \neg B$, we need $A \neg B \to \neg S$. This gives the following truth table:

A  B  S
0  0  1
0  1  ?
1  0  0
1  1  ?

We can make the two remaining combinations valid or not by deciding if we want to assign paradoxes to them or not. Any statement that satisfies this truth table without paradoxes in all rows is valid -- as you mention in the question, "I won't win any prize" ($\neg A \neg B$), is one such statement.

But it is not the only one -- a better strategy might be, for instance, to also force a paradox in $\neg A B$ by doing $\neg A B \to S$: 

A  B  S
0  0  1
0  1  1
1  0  0
1  1  ?

To satisfy the condition that at least one row must not be paradoxical, the ? must be 1. This truth table is achieved, for instance, by the statement "I will win B or I won't win A" ($\neg A \lor B$). In this case the only valid solution is to give you both prizes.

For completeness, the third solution is filling in the table so that both rows are non-paradoxical:

A  B  S
0  0  1
0  1  0
1  0  0
1  1  1

This is "I will not get exactly one prize" ($AB \lor \neg A \neg B$), which guarantees that you will get B, but you might or you might not get A.

1: I'm excluding self-referential statements, because the problem is trivial if you are allowed to use them: just say $S$ is $\neg B \to \neg S$ and you can even ignore the rules about prize A.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think that the strategy of "trying to create a paradox/contradiction" might again be something that you'd only do because you know that the solution will be based on creating a contradiction. If you did not know that, why should you try this? $\endgroup$
    – Marco13
    Apr 22, 2017 at 15:01
  • $\begingroup$ (Maybe this becomes clearer when you explain why you translated the statement "If you make a true statement, then you win A" as $A \to S$. I think it would rather be $S \to A$ ...?!) $\endgroup$
    – Marco13
    Apr 22, 2017 at 15:06
  • $\begingroup$ @Marco13 The solution of this question depends on the assumption that S's truth value can be decided; this is not necessarily true in logic so I think at least the paradoxical part of the solution has to be gotten from elsewhere, and after this assumption is made then you can use logic to derive what the three solutions look like. $\endgroup$
    – ffao
    Apr 22, 2017 at 18:18
  • $\begingroup$ Although I still can't wrap my head around the seemingly reversed $\to$ arrows in your statements, this answer brought some interesting insights. (BTW: I have added an update in the question) $\endgroup$
    – Marco13
    Apr 22, 2017 at 19:44
2
$\begingroup$

In these kind of questions, you can't just say something trivial or independent from the rules, so you have to say something that brings up the outcomes themselves and eliminates all but the desired one(s) of them by creating contradictions. If needed, give values to the possible parts of your statement depending on the outcome or the truth/falsehood. Don't forget to explore the implications of your statement being assumed to be true or false, and spot the possible contradictions.

In this particular question, we can win only B (if our statement is false) or A and B together (if it's true). Our statement could be something like "I will/won't win A and will/won't win B". Depending on whether we imply we'll win a prize or not, let's give the prizes the value 1 or 0 (let the duo be $p$, $q$). The truth value of this duo (1 if true, 0 if not) must be equal to $p$ because of the rules. Re: contradictions, if $p$, $q$ is assumed to be the false combination, then there's no way to rule it out, because there are 3 possible true versions with different $p$ and $q$s (not all are the same, that is). That means your statement will be assumed to be true first, only for then that possibility to be eliminated for contradicting the first rule (implying you won't win A, which would be true, must be the first part of your statement). Since the first part is true, the complete statement can only be false when the second one is. You can just say "I'll win neither A nor B".

Improve this answer
$\endgroup$
1
  • $\begingroup$ Similar to the other answers: This seems to rely solely on first-order logic. I'm not sure whether one would have made this assumption in a more complex/abstract problem description. (Maybe the "update" of the question is also relevant here) $\endgroup$
    – Marco13
    Apr 22, 2017 at 19:47
2
$\begingroup$

I don't know why "systematic" has to mean using a particular notation. Here's a systematic approach that I used.

First, you start with a comprehensive list of single things you can say, and their consequence:

  • I will win A - they can make this true by giving you A, but that won't gain you B. (Possible shortcut here realizing that you probably have to mention B in order to force them into giving it to you, but we're being systematic, so no leap at the moment)
  • I will not win A - this is a paradox, since if they don't give you A, it's true, requiring them to give you A, making it false, requiring them not to give you A - but none of that has any effect on giving you B (Another leap - if you said you wouldn't win anything at all, they can falsify that without getting A involved and triggering the paradox, but again we're ignoring leaps.)
  • I will win B - if they don't give you B, this is false, requiring them not to give you A either, leaving you with nothing.
  • I will not win B - they can make this true by not giving you B, which will oblige them to give you A, but that's not the point.

At this point you might be out of single statements or you might decide that "all" and "nothing" can be used in single statements.

  • I will win all the prizes - if they give you both, this is true, and consistent with getting A, but it doesn't force them to give you both: they can give you nothing, making it false, not making you get prize A
  • I will not win all the prizes - this is false if they give you both, and you can't have A when it's false, so they won't give you both. It's true if they give you nothing, or A only, so it doesn't force them to give you B.
  • I will not win nothing at all - this is true if they give you just A or just B, so they can just give you A
  • I will win nothing at all - this is false if they give you A, B, or both. Since you can't get A for a false statement, only giving you just B makes it safely false. If they try not giving you anything, that would make it true, which is incompatible with not getting A. Only giving you just B manages to be consistent.

(You could also decided that "any prize / at least one prize" or "exactly one prize" could work into these statements and generate a few more, but since I've found a winner I didn't.)

If you didn't consider "all" or "nothing" for your single statements, you could have moved on to double statements:

  • I will win A and B - same as "all" above
  • I will win A but not B - same as "I will win A" and tacking on "but not B" changes nothing. They give you A, it's true, done.
  • I will not win A but will win B - they give you nothing, it's false, done
  • I will not win A and not win B - same as "nothing at all" above
  • I will win A or B or both - same as "not nothing at all" above

At this point I've found my winning statement. If this quiz involved some other rules, so that I hadn't found a winner yet, I would think of statements that involved those rules, and systematically work through the combinations again.

Improve this answer
$\endgroup$
7
  • $\begingroup$ This seems to be based on the truth table, and on the assumption that first-order logic will be sufficient. While it sounds convincing, I'm not sure whether the assumption can be justified (BTW: I have added an update in the question regarding this point) $\endgroup$
    – Marco13
    Apr 22, 2017 at 19:45
  • $\begingroup$ It most definitely is not based on the truth table. I suppose you can look at it as a way to generate that truth table. It's systematic. I start with simple sentences that only have one statement. Since the rules mention winning A, I start with statements about winning A, of which there can really only be 2. When neither of those produces a solution, armed with a tiny insight that "the rules don't mention B so if I want to win it perhaps I should" I get 2 more statements. They still don't produce a winning statement. So I cast around for other single statements. I noted the ability to... $\endgroup$
    – Kate Gregory
    Apr 22, 2017 at 19:53
  • $\begingroup$ ... use all/none kind of things so I generated all I could think of. That produced a winner. I then imagined not thinking of those words and going to double statements. That also produced a winner. Had I been winnerless at this point I would have tried to make triple statements by coming up with something else to claim, and then crossing it against the earlier statements. This is systematic by any definition. Did I prove such a system will always lead to a solution to any problem? No, Did I show it leads to a solution to this one, and not just by co-incidence or happenstance? I say yes. $\endgroup$
    – Kate Gregory
    Apr 22, 2017 at 19:55
  • $\begingroup$ Sure, maybe there is no "algorithmic" way to solve this - I don't know, that's why I've been asking here. But ... for example, imagine the initial set of rules had included "You may not say that you will win neither A nor B" - How would you have proceeded with your approach? $\endgroup$
    – Marco13
    Apr 23, 2017 at 0:44
  • $\begingroup$ Since I had already reached "I will win nothing at all" I don't need to proceed further. But as I said, if I got to the end of all my double sentences without winning, I would have to think of a third statement I could use. This can't be random (eg "I have two hands" or "I have two heads") because the contest organizer isn't forced to give B by any statement's true or falseness. I might try adding statements about following the rules, or sentences being true, number of prizes awarded, or hypotheticals involving other contestants who get less prize Bs than me, and so on. $\endgroup$
    – Kate Gregory
    Apr 23, 2017 at 0:51
2
$\begingroup$

There is no systematic way to find the solution, because the given solution is inadequate, because the rules as stated [at least in their present form] do not allow for a solution that does not involve additional assumptions.

Although the proposed solution seems clever, it is simply a potential "liar's paradox", and an assumption is being made that the universe is bound to conspire to prevent a liar's paradox situation from taking place if there is a way to do so, and simply because such a way does exist.

Illustration:

Once upon a time, there ruled in the kingdom of Cigolli a king and queen who had two daughters - Anna and Bella. Princess Bella was beautiful, virtuous and intelligent, and the king had promised her hand in marriage to the equally brave, just and noble Sir Right. Princess Anna, however, was an unkempt, unreasonable and fierce shrew.

One morning, in a fit of rage, the Queen announced in court, "Anna's tantrums have become unbearable for the royal palace. She shall be married to the next man who utters a statement that holds true."

The court fell silent.

"And just to be clear," the Queen added, "She won't be married to him who says that which proves false."

Looking around the court, the Queen found that the guard Xor-a-dap standing next to her throne had fallen asleep. She picked up her staff and struck him soundly on his head, so that he woke up with a fright.

"What say you about marrying the princess, Xor-a-dap?" said the Queen.

"Huh... Wha...?" the dazed guard replied, "Your majesty, mere guard that I am, I shall never marry a princess of this kingdom."

"That's right," said the Queen, "And that means that you shall be the one to marry Princess Anna... No, wait... that makes your statement false, and so you can't be married to her... But then... Dang it!". After a bit of thought she finally concluded, "Very well then, Xor-a-dap, you shall marry Princess Bella."

"Wait... what?" said Princess Bella. "Um... dear, what?" said the King. "Your highness!" Sir Right gasped, "But didn't we have a deal? And what of Princess Bella's pride and happiness?"

"Deal schmeal" the Queen replied. "Although a monarch's word of honour, the pride of the princess, and the happiness of a daughter are indeed important, the universe is currently shaken by the nature of Xor-a-dap's statement. And in this age, there is nothing more important than being able to assign a definite truth value to a statement, no matter the assumptions or sacrifices that may need to be made in that regard. For if I should not be able to do so, the people shall not Like it, and the kingdom shall be a-twitter with the news of my indecision."

The wise vizier stood up and bowed. "Your majesty," he said, "Had Princess Bella never existed, how would we have dealt with Xor-a-dap's statement?"

"Well I suppose," the Queen replied, "That it would have had to remain indeterminate, and we would have no option save to give him a lashing."

"Indeed, your majesty," said the vizier, "Then there is no reason that the mere availability of Princess Bella should compel us to act otherwise. And as for reacting to Xor-a-dap's statement, just say that '@Xor-a-dap is a #blockhead' - the commonfolk really Like that kind of thing."

The Queen smiled. "What you say is absolutely true! ... And for that you shall now be married to Princess Anna."

And they all - with the exception of the vizier - lived happily every after.

Improve this answer
$\endgroup$
4
  • $\begingroup$ A nice, extended story-version of the original puzzle. Not relevant to the question, though... $\endgroup$
    – Marco13
    Apr 23, 2017 at 13:10
  • $\begingroup$ You would be right if it were not for the very first bullet in the question which establishes that B is a winnable prize. Your tale omits that, and is therefore insoluble. This question doesn't match your tale, so your tale isn't an answer to this question. $\endgroup$
    – Kate Gregory
    Apr 23, 2017 at 14:20
  • $\begingroup$ @Marco13: I'm saying that the reason you're unable to find a systematic way to reach the solution, is because it is not a solution. $\endgroup$
    – KeyboardWielder
    Apr 23, 2017 at 16:04
  • $\begingroup$ @KateGregory: I don't see a distinction. The first bullet doesn't say that B is a winnable prize, and even if so it does not say that it can be won merely by making statements as A can. In the story too, B is winnable (ignore the betrothal to Sir Right if that helps). Something needs to be added to the question to make the proposed solution valid, and that missing ingredient probably holds the starting point for what the OP is looking for. $\endgroup$
    – KeyboardWielder
    Apr 23, 2017 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.