9
$\begingroup$

Two perfect logicians Steve and Pete, who have never met, before are imprisoned by an eccentric villain. "I have two positive integer numbers x and y" he says to them. "I will tell Steve the sum x+y, and Pete the product xy. If at any point either of you know the two numbers x and y, you may shout them out, and I will release you both. You may take turns saying statements giving the other information, but you may only communicate about your state of knowledge. If any part of your statement contains any information about the numbers themselves, you'll both be shot. If any of you tries to communicate any other information not directly implied by the statements, you'll both be shot."

Can the logicians always figure out the numbers?

As an example, if the two numbers are 1 and 6, a potential conversation could go:

P: I don't know the numbers

S: I don't know the numbers

P: I don't know the numbers

S: I don't know the numbers

P: I know the numbers! They are 1 and 6! (S would have known if the numbers were 2 and 3)

Or another example, if the numbers are 2 and 4:

P: I don't know the numbers

S: I didn't know whether you knew until you said that (could have been 1 and 5, and P would obviously have known, as 5 can only be factorized as 1x5)

P: I know the numbers! They are 2 and 4! (S couldn't have said that if the numbers were 1 and 8)

Is there always some strategy like this? (Note that the logicians are not able to communicate beforehand, and each logician must attempt to give useful information based on what they know)

Edit: The question has been raised whether just saying "I don't know" until someone figures it out would work for all possible answers. It doesn't. In order to show this, all one needs to do is construct a "cycle" of possibilities, with each consecutive pair alternatively having the same sum or the same product. Those pairs would be indistinguishable for S and P for all time unless more information is given than "I don't know the numbers"

A simple cycle is given by (2,5)->(3,4)->(1,12)->(3,10)->(5,6)->(1,10)->(2,5).

One could argue that simply eliminating the possibility of having 1 as one of the numbers would solve this problem. But by merely doubling the cycle, this is shown to be false: (4,10)->(6,8)->(2,24)->(6,20)->(10,12)->(2,20)->(4,10). Thus, removing 1 only delays the problem.

Edit 2: As the condition about only talking about states of knowledge is ambiguous, I have decided that a new version is: The logicians can only say either they know/don't know the numbers, or that they knew/didn't know what the previous person just said (from which the other logician can infer that they don't know the numbers, because otherwise they would have said that)

For example, if the numbers are 3 and 4, a conversation could go:

P: I don't know the numbers (could be 1 and 12 or 2 and 6)

S: I knew you didn't (even if the numbers were 2 and 5 or 3 and 4, P wouldn't have known)

P: I didn't know that (S couldn't have said that if the numbers were 2 and 6. However, this doesn't yet eliminate 1 and 12)

S: I know the numbers! They are 3 and 4! (the previous statement eliminated the other options)

Edit 3: 02/05/2020: It's starting to seem like it still might take the logicians quite a long time to figure out the numbers, and the logic gets increasingly difficult to follow. I wouldn't be surprised if for some pairs of numbers they might not be able to figure it out. Here's a particularly interesting (solvable!) case (shortened to aid readability). The numbers are 1 and 10:

P: I know you know that I don't know the numbers

S: I know you know that I didn't know that

P: I know the numbers now! They are 1 and 10!

$\endgroup$
15
  • 1
    $\begingroup$ See discussion at artofproblemsolving.com/community/c146h150971 $\endgroup$ Apr 30, 2020 at 2:04
  • 1
    $\begingroup$ Much discussion at math.uni-bielefeld.de/~sillke/PUZZLES/sp.txt $\endgroup$ Apr 30, 2020 at 4:07
  • 1
    $\begingroup$ @LSpice, yes, positive integers $\endgroup$
    – Thomas
    Apr 30, 2020 at 4:12
  • 1
    $\begingroup$ Those seem to be about very specific cases, where there are restrictions on the sum, and the reader has to figure out the numbers. I'm asking if, given any two numbers, the logicians can figure it out. $\endgroup$
    – Thomas
    Apr 30, 2020 at 8:35
  • 1
    $\begingroup$ @FrançoisBrunault, with regards to state of knowledge. Let's say that the two logicians can only say things like "I know/don't know the numbers", and "I knew/didn't know what you just said before you said it". $\endgroup$
    – Thomas
    May 1, 2020 at 0:18

0

Your Answer

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

Browse other questions tagged or ask your own question.