CA CS CIMA Prakash Somani (Landmark Group) (23502 Points)
09 September 2008Two 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? (Computer assistance allowed.)
Amresh Choudhary
(M.Sc. (Maths) MBA LLB (DU))
(694 Points)
Replied 09 September 2008
| Originally posted by :CA Prakash Somani | ||
| " | 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? (Computer assistance allowed.) |
" |
Dear, here is the solution:-
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. 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 belwo 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.
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
114
3
38
41
148
4
37
41
180
5
36
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
CA Rajesh S
(Chartered Accountant)
(1581 Points)
Replied 09 September 2008
quite complicated!!!!!!!!!!!!
CAclubindia
