Cody

# Problem 44377. Five steps to enlightenment

This problem asks you to identify valid variations of the famous sum and product puzzle. The original sum and product puzzle goes somewhat like this:

Scott and Priscilla are asked to guess two numbers X and Y, ranging between 2 and 100 and with X<Y. Scott is told their sum S (=X+Y) and Priscilla is told their product P (=X*Y). After this, they have the following conversation:

```Scott:      I don't know X and Y                                                (Step 1)
Priscilla:  Neither do I                                                        (Step 2)
Scott:      Before our conversation I already knew that you didn't know         (Step 3)
Priscilla:  But now I do know X and Y                                           (Step 4)
Scott:      And so do I!                                                        (Step 5)
```

The original puzzle asks you to deduce the value of X and Y from the above information

To solve this puzzle you may assume that: a) Scott and Priscilla are perfect mathematicians/logicians and always speak the truth; b) they are aware of each other circumstances (Scott knows that Priscilla has been told the product of X and Y, and Priscilla knows that Scott has been told the sum of X and Y before the beginning of their conversation); and c) the third sentence refers to Scott and Priscilla state before the beginning of the conversation (i.e. Scott already knew -at the outset of this conversation- that Priscilla did not know the solution -at the time-)

Briefly, the deduction for this seemingly impossible puzzle starts with all possible pairs of values of X and Y, and uses the information in the sentences above to sequentially reduce the range of possible (X,Y) pairs to those that would be consistent with each sentence (see figure below; blue dots represent (X,Y) pairs still possible after each of the sentences/steps above; plot uses matrix convention with origin at the upper-left corner, X in vertical axis, and Y in horizontal axis; upper triangular segment represents all possible X<Y pairs before the start of S&P conversation). For example, in Step 1 after S says "I don't know X and Y" we learn that the pair (X,Y) = (2,3) (and a few others) are no longer possible, since otherwise S would have known the solution as soon as he was told their sum (X+Y=5), which takes a unique value among all possible (X,Y) pairs. Similarly, in Step 2, after P says "Neither do I", the pair (X,Y) = (5,7) (and many others) are no longer possible, since otherwise P would have known the solution as soon as she was told their product X*Y=35, which turns out to be unique among all remaining X,Y pairs. In Step 3, S asserting "I knew that you didn't know" tells us that, knowing only X+Y, he was able to determine beforehand that it would be impossible for P to know both X and Y from their product X*Y alone, which, again, rules out a considerable number of (X,Y) pairs (e.g. all solutions with X+Y=12 can be ruled out, because if S was told that X+Y=12 he could not have possibly dismissed beforehand the possibility that perhaps X=5 and Y=7 which would have allowed P to know both X and Y as soon as she was told their product X*Y=35). In Step 4, P suddenly become aware of the solution after S revelation informs us that, unlike in Step 2, she is now (after step-3 crop in possible X,Y pairs) able to uniquely determine the solution (X,Y) from their product (X*Y). This allows us to rule out many (X,Y) pairs among the remaining possible values, such as (X,Y)=(2,15) or (5,6), because P would not have been able to uniquely identify the solution at this point if she was told that the product X*Y was 30. Last, in Step 5, S suddenly becoming aware of the solution after P revelation, again allows us to rule out any remaining (X,Y) pair where knowing the sum S would still not suffice to uniquely identify the solution.

This puzzle is very neat because, somewhat surprisingly, after sequentially reducing the range of possible (X,Y) pairs from the five sentences/steps above, only one possible pair remains. The solution X=4 and Y=13, which Priscilla learns after the third sentence, Scott learns after the fourth sentence, and you, the reader, learn after the fifth sentence.

Key to the existence of a unique solution to this puzzle is the initial range of possible (X,Y) pairs that we are told to consider. If, for example, instead of considering all X,Y values between 2 and 100, we were told to consider all X,Y values between 1 and 100, the puzzle would not be solvable, as in this case there will be multiple possible solutions that would all be consistent with the five sentences above (see figure below; at Step 5 there still exist 6 different possible solutions to this puzzle). Similarly, if we were told to consider all X,Y values between 2 and 50, the puzzle would again not be solvable, as in this case there would be no solution consistent with all five sentences (perhaps surprisingly, since the X=4 Y=13 solution above is in fact within the stated range). On the other hand, if we were told to consider X and Y values ranging between 1 and 24, for example, the puzzle would again become solvable, now with a new unique solution X=1 and Y=6. In this problem you are tasked to create a function that would determine whether a particular variation of this puzzle would work or not. Specifically, given an initial set of possible (X,Y) pairs (entered as a Nx2 matrix and representing the full set of possible X,Y pairs that Scott and Priscilla are told to consider), you should determine whether it is possible to solve this puzzle (i.e. whether one, and only one, (X,Y) pair is consistent with the five sequential sentences above). Your function should simply return 1 (or true) if the puzzle is solvable, and 0 (or false) otherwise.

Good luck!

### Solution Stats

28.67% Correct | 71.33% Incorrect
Last solution submitted on May 23, 2019