|
x = 4, y= 13
S1 and P2 are the knaves.
Explanation We begin by looking at P2’s first statement that x+y = 33.
Suppose this were true. Since P2 has knowledge of both the product and sum of x and y; he is in a position to determine x and y individually. Thus, P2 would have to be in a position to determine x and y from their product.
One way this could happen is if the product, xy, were the product of two primes. The only possibility along these lines giving a sum of 33 is xy = 62, with x=2, y= 31.
But there is also another possibility; namely, if there were only one unique way to breakdown in product into two factors, each greater than 1 and less than 100. This occurs for the product 242 = 2 * 11^2, which has three prime factors, but for which x= 11, y=22 is the only permissible solution.
All other products constructed from a pair of summands of 33 would not allow P2 to make his statement with such confidence. For instance, if here were looking at the product of 140 (=5*28), the sum could just as easily be 24 (=10 +14) as 33.
So, if P2 is telling the truth, then xy = 62 or xy = 242. But both these possibilities contradict both S1 and S2, one of whom must be a knight.
Hence, P2 is a knave.
Next, consider S1’s follow up statement. This contradicts what we have already shown. Therefore , after the initial phase it is public knowledge that S1 is a knave, and P1 and S2 are the knights.
Now, as we’ve seen, P1’s statement in the initial phase tells us something about x and y:
- at least one of x,y must be a composite number
- more generally, it must be possible to breakdown xy into two factors at least two ways, where each of the factors is less than 100.
In addition, we can exclude various other possibilities for the product, p = xy. Thus
- p must be at least 6 (corresponding to x=2, y= 3) and at most 2450 (corresponding to x= 49, y = 50).
- p cannot be a prime, since it has two factors > 1.
- p cannot be the square of a prime, since p must have multiple, distinct factors greater than 1
- p cannot be the cube of a prime, q, since then we could conclude that x = q, y = q^2
- p cannot be the fourth power of a prime, since then we could conclude that x = q, y = q^3
The products that still remain after eliminating all such cases are called “possible products”.
Next, we turn to S2’s initial statement. Let s = x+y and suppose there were some integer, N, such that the product (s – N)*N could be decomposed in only one allowable way. For instance, suppose s = 16. Then, with N=3 we get the product 13*3 which would allow P1 to make a unique factorisation, contradicting P1’s initial statement. Hence, we can eliminate from consideration as sums all numbers which admit products (s-N)*N that have only a single permissible decomposition.
This eliminates many possibilities for the sum, for instance 32 (= 29 +3) and 57 (= 53 + 4). A little hand calculation shows that the only possibilities for the sum, s, are:
11, 17, 23, 27, 29, 35, 37, 41, 47, 53.
In fact, P1 can make a further deduction from S2’s initial statement, since he can restrict the possible products of the form (s-N)*N, where s is one of the ten values listed above. Some calculation (here, a computer comes in handy), allows P1 to determine that S2 knew all 131 values that remain valid possibilities for p.
Now, among these 131 possible products some of them could correspond to multiple values of s. For instance, p=120 can be associated with both s = 29 = 5 + 24 and s = 23 = 8 + 15; whereas p =208 admits only the single possibility s = 29 = 13 + 16. Let’s call the possible values of p, like 120, which admit to different possibilities among the ten candidate sums “non-determinative values”; and possibilities which fix a unique sum as “determinative values”.
Next, we consider P1’s position after the initial phase. He knows that S2 is his fellow knight, and, can conclude that s = x + y must be one of the ten possibilities listed above. P2 then tells us that knowing this is enough to allow him to determine x and y.
S2 is, therefore, able to deduce that p is one of the determinative values (like 208) and not one of the non-determinative, admitting multiple sums. There are 100 determinative values, but S2 tells us he can go further, reducing the number of possible products down to just one. This information is enough to allow us to make the same deduction for x and y. Here is how:
Each of the ten possible sums, s, admit some combination of determinative and non-determinative possibilities for the product, p. For instance, s= 23 admits three determinative possibilities: 76, 112 and 130; and seven non-determinative possibilities: 42, 60, 90, 102, 120, 126, and 132. Now, if x + y added together to 23, S2 would be unable to determine between each of the three determinative values for the product. Hence, S2 would not be able to posit his claim that he can determine x and y. Among the ten possible sums, s = 17 is unique, in that it admit only one single determinative product, corresponding to x=4, y = 13. |
