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!
Interesting and fun challenge, Alfonso! However, it seems to me that some of the given answers are incorrect. I did tests #14 and #15 by hand (pen and paper), and got a different outcome, corresponding to the outcome of my solution 1288362; and I suspect that the given answers of tests #3, #8, #11, #16 and #17 are also incorrect. (If I have understood the description correctly, Scott and Priscilla are perfect logicians, hence when Priscilla answers "Neither do I", she's already taken Scott's first answer into account.)
@Alfonso: By the way, I have to give you kudos for presenting such a neat and elaborate problem description, with excellent graphs that illustrate/explain the theory so well. It must have been a lot of work to compose this all together.
I've just verified (by solving by hand/pen+paper) that the given answer of test #17 is also incorrect; after step 4, there are three possible solutions left ((X,Y) = (1,10), (3,8) or (5,6)), but since these solutions result in the same value of X+Y (and in different values of X*Y), there's no way that Scott can take step 5 and claim that he knows the solution too. Hence none of the three remaining potential solutions is consistent with all five steps in test #17.
@yurenchu thank you for the feedback! I have corrected the testsuite now. Two important clarifications: 1) when, in step 2, Priscilla says that she does not know the answer, she is now assumed to know the product P AND she is also assumed to know that S does not know the answer himself (I believe this is what you were referring to, if I am interpreting correctly, and I agree that this makes sense given the way we are presenting the puzzle; the previous/original testsuite was assuming that these two statements were somewhat simultaneous); 2) when, in step 3, Scott says that he already knew that Priscilla would not know, it is assumed that he already knew this as soon as he was told the sum S, without any foreknowledge of how the conversation would go (compared to "he already knew that Priscilla would not know the answer even after he would tell her that he himself did not know the answer"). Let me know if this makes sense
looking at your solution 1288362, the two things still not allowing that to work in the testsuite are: 1) elim3 is being computed assuming that P already knows that S does not know the solution (i.e. elim3 should use an alternative elim2 vector computed without the "P(elim1)=nan" line); and 2) the 'binMethods','integer' option of histcounts is somewhat misleading, in that if the number of bins is too large it will revert to larger-than-one-integer bins (which is happening in a few of the testsuite cases in your code). Hope this helps and thanks again for the feedback!
@Alfonso, Thank you for your replies. I wasn't at all aware of the 'BinMethod'-'integers' pitfall, so thanks for pointing that out; I'll have to find a way around that. Regarding the elim3 calculation: I think this is a key issue, possibly depending on interpretation; but I think it's essentially correct. For example, in the case of the new test #17 (which I've just solved by hand :-) ), with the conveniently small value range of {4,6,8,12,16,18}, my solution code doesn't find a consistent solution while the given answer implies there is a unique and consistent solution. I'm assuming the intended solution was (X,Y) = (6,16), which means that Scott knew that X+Y = 22 and Priscilla knew that X*Y = 96. In my view, if Scott is a perfect logician, he can't truthfully claim at step 3 that he knew from the start (after knowing that X+Y=22) that Priscilla wouldn't know the solution; because for all he knew she could have received "X*Y=72", in which case she would have been able to deduce (after step 1) that the answer (in that case) would have been (X,Y) = (4,18). Therefore I think the solution (X,Y) = (6,16) should not be considered consistent with the five sentences when uttered by perfect logicians S & P.
Another way to look at it (still in the context of new test #17): Suppose that right after step 1, the police/FBI/CIA/whatever interrupts the game and arrests Priscilla, on the charge that she knows the "secret code" (X,Y) and that she mustn't reveal it because the X,Y code needs to remain secret. So she's immediately taken to prison and never gets to say the line "Neither do I" (step 2). Can Scott at that point then truthfully claim that they must release her because he is completely certain that she actually doesn't know the code?
@yurenchu. Thank you for your thoughtful comments. The way I interpret the "I knew you wouldn't know" sentence, it reflects what Scott knew BEFORE Step 1 (only armed with the knowledge of the sum S) about what Priscilla knew also BEFORE Step 1 (only armed with the knowledge of the product P). You are interpreting the sentence "I knew you wouldn't know" to reflect what Scott knew before or after Step 1 (armed with the knowledge of the sum S) about what Priscilla knew or would know AFTER Step 1 (armed with the knowledge of the product P as well as with the knowledge of Scott not knowing the solution). In the [4,6,8,12,16,18] example, the reason why Scott, after being told that S=22 (so he knows at that point that the solution is either (6,16) or (4,18)), can claim with certainty that Priscilla does to know the answer (before Priscilla learns about Scott not knowing the answer himself) is because, he argues, if Priscilla is told that the product is 96, she still cannot discern between the (6,16) case and the (8,12) case (since unlike Scott, Priscilla has not yet been able to rule out that case; she will later be able to rule out (8,12) after she learns that Scott does not know the solution, but that is another story...) Last, in your "police interrupts the scene" scenario, Scott could truthfully claim that if the police interrupts the game before the conversation takes place (when S knows only the sum, P knows only the product, and the S&P conversation is not planned to occur at any point in the future). In any way, I imagine this is really ultimately a matter of me having not been clear enough with the phrasing of the "I new you wouldn't know" sentence, which I agree leaves too much ambiguity and it could well be interpreted as a statement about what Scott would predict Priscilla would say after she learns about Scott not knowing the solution (your interpretation), just as a statement about what Scott would predict Priscilla would know after each was told the sum/product. Any thoughts about how to better phrase this to try to avoid ambiguity? (I am perfectly happy changing the problem to match your interpretation, I just would like to avoid ambiguity so others don't run into the same issues; and again thanks for your help&comments, they are really appreciated)
"I had already realized at the outset that ...". Bam!
I've given a try to a few clarifying sentences in the problem's description, let me know if those help. Thanks!
you guys' comments are really helpful, at very beginning, I was quite confused what time point does "knew" refer to. Now I know that is before S spoke out.
@Alfonso Thanks for your elaborate clarifications, in your reply comments as well in the problem description! I was preparing a lengthy response with some additional arguments and other thoughts, but I notice that you've now resolved the issue by simply changing the word "wouldn't" in Step 3 into "didn't", which is one of the suggestions that I was going to make. I think Step 3 would be even clearer and more natural when Priscilla's line at Step 2 is also changed into "I didn't either and I still don't." So the conversation would be like this:
Scott: "I don't know X and Y." / Priscilla: "I didn't either and I still don't." / Scott: "I already knew that you didn't." / Priscilla: "In that case I guess I know X and Y now." / Scott: "Oh really? Then so do I!" [Now if only I could think of a workaround for that pesky 'BinMethod' issue... :-) (I think I've found one, but I've yet to try and see if it works.)]
It is possible to check test case 17? I have done it by hand and what I got is that It is not possible for Scott to assert statement 5, because are are two possible solutions: [4,18] and [6,16]. Thank you very much.
It is possible to check test case 17? I have done it by hand and what I got is that It is not possible for Scott to assert statement 5, because are are two possible solutions: [4,18] and [6,16]. I am also getting the same result of two possible solutions in cases 14 and 18. Thank you very much.
in test case 17 (with X,Y =[4,6,8,12,16,18]), the solution [4,18] is ruled out first in Step 2, because, if Priscilla was told that the product was 72 (this would have left her with only two options: [4,18] or [6,12] at that point), as soon as she heard in Step 1 that Scott does not know the solution she could immediately have ruled out [6,12] (because that would have resulted in Scott knowing the solution from the unique sum S=18), leaving her knowing the solution in Step 2, contrary to her assertion. Let me know if that clarifies. Just for completion, in test case 17, after Step 1 valid solutions are [4,16],[4,18],[6,16],[6,18],[8,12], or [8,16] (associated with sum S = 20, 22, or 24); after Step 2 valid solutions are [6,16], or [8,12] (associated with product P = 96); and after Step 3 the only possible solution is [6,16] (the other solution, [8,12], can be ruled out because if Scott was told that S=20 he could not have possibly dismissed the possibility of [4,16], which would have allowed Priscilla to know the answer immediately from the product P=64 alone). Let me know if this makes sense
Thank you very much! I was missing that condition, but I have fixed it now.
@Alfonso Wait a minute... in the case of Test #17 (now #18; with value range {4,6,8,12,16,18}), why would Scott wait until after Step 4 before deducing what X and Y are? Couldn't he already deduce the solution right after Step 2, one step before Priscilla figures it out? (I haven't investigated if this issue also exists in other test cases, although I'm reasonably sure it doesn't automatically apply to all test cases.)
@yurenchu you are right, there are a number of scenarios that are somewhat peculiar in that the order in which Scott/Priscilla/you learn the solution differs from the typical scenario: in a typical scenario Priscilla learns the solution after step 3, Scott after step 4, and you after step 5. In testcase #17 and above Scott learns it after step 2, and both Priscilla and the reader learn it after step 3. For the sake of this Cody problem I considered these cases as valid because they did not introduce any logical inconsistency (e.g. Scott could choose to say "I already knew that you didn't know" sentence even if he already knew the answer at that point). I guess one could argue that the phrasing of sentences 4 and 5 seems to imply that they just learned the solution at those points, perhaps I should go with the less ambiguous "I know X and Y now" for both sentences? (or ideally something less robotic-sounding)
@Alfonso Thanks for your reply! I think sentence 4 is okay as it is, because in any case Priscilla can't know the answer before step 4 (unless she was lying at step 2). You're right that Scott can still say "I already knew that you didn't know" at step 3 in test #17/#18 without being logically inconsistent. I think it's mostly step 5 that seems inconsistent, because the word "then" in sentence 5 seems to imply that Scott needs Priscilla's line at step 4 before he can figure out the answer, as is the case in the "normal" test cases. (Although one could indeed argue that the mathematical definition of "then" -in its strictest sense- is not inconsistent with a case where Scott unnecessarily waits two steps before revealing he already knows X and Y; but it does sound odd to "non-mathematical" ears.) Maybe changing sentence 5 into "Oh really? Well, so do I!" would cover situations such as test #17/#18 better.
@yurenchu "Well, so do I!" it is (I liked your suggestion!) and thank you very much again for all your very helpful comments
@alfonso Consider the problem statement as the Diophantine equations X+Y=S & X*Y=P ⇔ x^2-S*X+P = 0; (X,Y)∈ℤ. In some of the test cases the list of tuples degenerates to 2, I have noticed for these scenarios both of the tuples satisfy these Diophantine equations, yet the correct solutions is thrown as true when the sum of each tuple is unique and the product of the tuples is equal, and false when the product of the tuples is unique and the sum of each tuple is equal. Is this consistent with your problem statement/explanation above?
I might be missing something, but I disagree with step 3 of test case 24. [6;16] is the correct solution, Scott knows the sum 22. In Step 1, he identifies [6;16] and [4;18] as possible. But in Step 3, he would stumble over 4*18 = 72, which would have allowed Priscilla to identify the pair in Step 2. (6*12=72 having been ruled out it Step 1). Therefore, his statement in Step 3 is false, and my admissible solution set is empty.
So what I am missing, or am I reading the problem wrong?
@Thomas, this is certainly a source of cofusion (see most comments above). To clarify, Scott statement in Step 3 refers to his knowledge state at the onset of this exchange about what Priscilla knew at that same time. In other words, Scott learns at the onset that the sum is 22. He considers that the pairs must be either (4,18) or (6,16). He then works each of these two cases and deduces that, if the pair was (4,18), then Priscilla would have been told P=72, and with this information she would only know that the solution is either (4,18) or (6,12); and if the pair was instead (6,16) then Priscilla would have been told P=96, and with that information she would only know that the solution is either (6,16) or (8,12). In both cases Priscilla could not have deduced the solution from knowing the product P alone, so Scott can safely deduce that Priscilla did not know the solution at the onset (which is what he states at Step 3; he already knew that she did not know). After Scott states that he does not know the solution in Step 1, Priscilla learns some new information, which allows her to rule out (6,12), which changes the logic above, but that information is not part of Step 3 statement (Scott is not saying that he knew that Priscilla could not have known the solution after hearing Scott's statement #1, he is saying that he knew that Priscilla could not have known the solution at the onset). Hope this clarifies
OK, so that absolutely requires rephrasing. You cannot say that "I already knew that you didn't know." when in the other person might have known at that point. The phrase should: "I knew from the start that you did not know at the start" (but I observer that you still do not know). That is semantically very different, and not what the exchange actually says. Luckily it should be easy to change in the algorithm...
@Thomas: fair enough, I changed the wording of the third sentence to try to make it less ambiguous (also note that there are several clarifications in the text regarding how to properly interpret sentence #3, starting from "and c) the third sentence refers to ..." as well as "In Step 3, S asserting ... tells us that ...")
Very interesting and well set out problem. I had a lot of fun working through this one. My first couple of attempts passed most of the tests but I had trouble with tests 21 and 24. The big thing I was missing was realising that Priscilla still doesn't know the answer in step 2, even after taking into account Scott's statement in step 1. After realising that, it all fell into place.
Interesting...
Took a bit to get my code to work on bigger Matrices.
almost there, I added a few comments in the testsuite in tests 21-26 to help you debug
Thank you Alfonso, I just saw this comment today. I'm now trying to learn from your solutions to other problems :)
added a few more test cases to discourage look-up table solutions
The same exact solution intermittently passes and fails the test suite number 24 (the one that employs randi). All the other cases are always pass. Are you sure that the result should be false for any randi output?
thanks for pointing this out, I fixed that now
added a few test cases to discourage this sort of solutions
congrats on finishing all Cody5:hard problems! I have to say, your solutions are consistently impressive and instructive, thanks for sharing!!
thank you, alfonso. your solutions never fail to enlightening me!