Two logicians
Two perfect logicians, S and P, are told that integers x and y have been chosen such that 1 < x < y and x+y < 100. S is given the value x +y and P is given the value xy.
They then have the following
conversation.
P: I cannot determine the two numbers.
S: I knew that.
P: Now I can determine them.
S: So can I.
Given that the above statements are true, what are the two numbers?
Soln :
First of all, trivially, xy cannot be prime . It also cannot be the square of a prime, for that would imply x = y.
We now deduce as much as possible from each of the logicians' statements. We have only public information: the problem statement, the logicians' statements, and the knowledge that the logicians, being perfect, will always make correct and complete deductions. Each logician has, in addition, one piece of private information: sum or
product.
P: I cannot determine the two numbers.
P's statement implies that xy cannot have exactly two distinct proper factors whose sum is less than 100. Call such a pair of factors eligible.
For example, xy cannot be the product of two distinct primes, for then P could deduce the numbers. Likewise, xy cannot be the cube of a prime, such as 33 = 27, for then 3×9 would be a unique factorization; or the fourth power of a prime.
Other combinations are ruled out by the fact that the sum of the two
factors must be less than 100. For example, xy cannot be 242 = 2×112,
since 11×22 is the unique eligible factorization; 2×121 being
ineligible. Similarly for xy = 318 = 2×3×53.
S: I knew that.
If S was sure that P could not deduce the numbers, then none of the possible summands of x+y can be such that their product has exactly
one pair of eligible factors. For example, x+y could not be 51, since
summands 17 and 34 produce xy = 578, which would permit P to deduce
the numbers.
We can generate a list of values of x+y that are never the sum of
precisely two eligible factors. The following list is generated by
JavaScript; the function may be inspected by viewing
Eligible sums: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53 .
P: Now I can determine them.
P now knows that x+y is one of the values listed above. If this
enables P to deduce x and y, then, of the eligible factorizations of
xy, there must be precisely one for which the sum of the factors is in
the list. The table below shows all such xy, together with the
corresponding x, y, and x+y. The table is sorted by sum and then
product.
Note that a product may be absent from the table for one of two
reasons. Either none of its eligible factorizations appears in the
above list of eligible sums (example: 12 = 2×6 and 3×4; sums 8 and 7),
or more than one such factorization appears (example: 30 = 2×15 and
5×6; sums 17 and 11.)
S: So can I.
If S can deduce the numbers from the table below, there must be a sum
that appears exactly once in the table. Checking the table, we find
just one such sum: 17.
Therefore, we are able to deduce that the numbers are x = 4 and y =
13.
Eligible products and sums
Product x y Sum
18 2 9 11
24 3 8 11
28 4 7 11
52 4 13 17
76 4 19 23
112 7 16 23
130 10 13 23
50 2 25 27
92 4 23 27
110 5 22 27
140 7 20 27
152 8 19 27
162 9 18 27
170 10 17 27
176 11 16 27
182 13 14 27
54 2 27 29
100 4 25 29
138 6 23 29
154 7 22 29
168 8 21 29
190 10 19 29
198 11 18 29
204 12 17 29
208 13 16 29
96 3 32 35
124 4 31 35
150 5 30 35
174 6 29 35
196 7 28 35
216 8 27 35
234 9 26 35
250 10 25 35
276 12 23 35
294 14 21 35
304 16 19 35
306 17 18 35
160 5 32 37
186 6 31 37
232 8 29 37
252 9 28 37
270 10 27 37
322 14 23 37
336 16 21 37
340 17 20 37
180 5 36 41
114 3 38 41
148 4 37 41
238 7 34 41
288 9 32 41
310 10 31 41
348 12 29 41
364 13 28 41
378 14 27 41
390 15 26 41
400 16 25 41
408 17 24 41
414 18 23 41
418 19 22 41
132 3 44 47
172 4 43 47
246 6 41 47
280 7 40 47
370 10 37 47
396 11 36 47
442 13 34 47
462 14 33 47
480 15 32 47
496 16 31 47
510 17 30 47
522 18 29 47
532 19 28 47
540 20 27 47
546 21 26 47
550 22 25 47
552 23 24 47
conversation.
P: I cannot determine the two numbers.
S: I knew that.
P: Now I can determine them.
S: So can I.
Given that the above statements are true, what are the two numbers?
Soln :
First of all, trivially, xy cannot be prime . It also cannot be the square of a prime, for that would imply x = y.
We now deduce as much as possible from each of the logicians' statements. We have only public information: the problem statement, the logicians' statements, and the knowledge that the logicians, being perfect, will always make correct and complete deductions. Each logician has, in addition, one piece of private information: sum or
product.
P: I cannot determine the two numbers.
P's statement implies that xy cannot have exactly two distinct proper factors whose sum is less than 100. Call such a pair of factors eligible.
For example, xy cannot be the product of two distinct primes, for then P could deduce the numbers. Likewise, xy cannot be the cube of a prime, such as 33 = 27, for then 3×9 would be a unique factorization; or the fourth power of a prime.
Other combinations are ruled out by the fact that the sum of the two
factors must be less than 100. For example, xy cannot be 242 = 2×112,
since 11×22 is the unique eligible factorization; 2×121 being
ineligible. Similarly for xy = 318 = 2×3×53.
S: I knew that.
If S was sure that P could not deduce the numbers, then none of the possible summands of x+y can be such that their product has exactly
one pair of eligible factors. For example, x+y could not be 51, since
summands 17 and 34 produce xy = 578, which would permit P to deduce
the numbers.
We can generate a list of values of x+y that are never the sum of
precisely two eligible factors. The following list is generated by
JavaScript; the function may be inspected by viewing
Eligible sums: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53 .
P: Now I can determine them.
P now knows that x+y is one of the values listed above. If this
enables P to deduce x and y, then, of the eligible factorizations of
xy, there must be precisely one for which the sum of the factors is in
the list. The table below shows all such xy, together with the
corresponding x, y, and x+y. The table is sorted by sum and then
product.
Note that a product may be absent from the table for one of two
reasons. Either none of its eligible factorizations appears in the
above list of eligible sums (example: 12 = 2×6 and 3×4; sums 8 and 7),
or more than one such factorization appears (example: 30 = 2×15 and
5×6; sums 17 and 11.)
S: So can I.
If S can deduce the numbers from the table below, there must be a sum
that appears exactly once in the table. Checking the table, we find
just one such sum: 17.
Therefore, we are able to deduce that the numbers are x = 4 and y =
13.
Eligible products and sums
Product x y Sum
18 2 9 11
24 3 8 11
28 4 7 11
52 4 13 17
76 4 19 23
112 7 16 23
130 10 13 23
50 2 25 27
92 4 23 27
110 5 22 27
140 7 20 27
152 8 19 27
162 9 18 27
170 10 17 27
176 11 16 27
182 13 14 27
54 2 27 29
100 4 25 29
138 6 23 29
154 7 22 29
168 8 21 29
190 10 19 29
198 11 18 29
204 12 17 29
208 13 16 29
96 3 32 35
124 4 31 35
150 5 30 35
174 6 29 35
196 7 28 35
216 8 27 35
234 9 26 35
250 10 25 35
276 12 23 35
294 14 21 35
304 16 19 35
306 17 18 35
160 5 32 37
186 6 31 37
232 8 29 37
252 9 28 37
270 10 27 37
322 14 23 37
336 16 21 37
340 17 20 37
180 5 36 41
114 3 38 41
148 4 37 41
238 7 34 41
288 9 32 41
310 10 31 41
348 12 29 41
364 13 28 41
378 14 27 41
390 15 26 41
400 16 25 41
408 17 24 41
414 18 23 41
418 19 22 41
132 3 44 47
172 4 43 47
246 6 41 47
280 7 40 47
370 10 37 47
396 11 36 47
442 13 34 47
462 14 33 47
480 15 32 47
496 16 31 47
510 17 30 47
522 18 29 47
532 19 28 47
540 20 27 47
546 21 26 47
550 22 25 47
552 23 24 47
No comments:
Post a Comment