Two different integers from 1 to N are chosen. Sam is given the sum and Pat is given the product. Sam and Pat take turns stating whether they can determine the numbers
Sam: I don't know the numbers.
Pat: I don't know the numbers.
Sam: I don't know the numbers.
Pat: I don't know the numbers.
.
.
.
.
Sam and Pat continue like this until one of them realizes that it is impossible for either of them to determine the numbers. What is the smallest possible N for which this can happen?
(In reply to
...Huh? by George)
Let's take an example of an N which is too small for the lockout to occur (that is, no matter what pair of numbers is chosen, one or the other will always figure it out). Make it 6 to be sufficiently interesting. My computer-generated table shows, for N = 6:
N1 N2 sum prod
6 Sam says 1 2 3 2 in turn 1
6 Sam says 1 3 4 3 in turn 1
6 Sam says 4 6 10 24 in turn 1
6 Sam says 5 6 11 30 in turn 1
6 Pat says 1 4 5 4 in turn 2
6 Pat says 1 5 6 5 in turn 2
6 Pat says 2 4 6 8 in turn 2
6 Pat says 2 5 7 10 in turn 2
6 Pat says 3 5 8 15 in turn 2
6 Pat says 3 6 9 18 in turn 2
6 Pat says 4 5 9 20 in turn 2
6 Sam says 2 3 5 6 in turn 3
6 Sam says 2 6 8 12 in turn 3
6 Pat says 1 6 7 6 in turn 4
6 Pat says 3 4 7 12 in turn 4
There are C(6,2) = 15 possible choices for the two numbers, N1 and N2, and all are accounted for here as being identified by one player or the other. In the table, the smaller one is always shown as N1 and the larger as N2.
At the very beginning, on Sam's first turn, if the numbers chosen had been 1,2 or 1,3 or 4,6 or 5,6, Sam would realize, from the total (3, 4, 10 or 11 respectively) what the two numbers would be, as these are the only pairs from the possible set that produce the respective sums.
In Pat's first turn (turn 2), a product of 4 tells her that the two numbers must be 1 and 4, as those are the only unequal numbers of 6 or lower that could produce that product. There are various other unique products shown for turn 2 identification, which Pat could also identify if they had turned up.
If Pat says she can't figure it out, it must be that she was not given any of these products. So if Sam had the sum 5, or 8, he now knows that the pair couldn't be 1,4, or 3,5, respectively, as otherwise Pat would have identified the pair previously. That leaves only 2,3 for the total of 5 or 2,6 for the sum of 8.
Similar deductive logic enables Pat to identify a product of 6 as representing 1x6, rather than 2x3, if it comes to Sam having said for a second time he could not identify the number pair. Likewise she could identify 12 as being 3x4, rather than 2x6, as otherwise Sam could have identified it in his turn just before.
It is similarly done for larger values of N, until, when N is 12, after 8 turns have gone by, and neither has identified the number pair, each realizes that it's insoluble.
Here are the ambiguous cases as listed at the bottom of the section for N=12:
N1 N2 sum prod
1 10 11 10
1 12 13 12
2 5 7 10
2 12 14 24
3 4 7 12
3 8 11 24
3 10 13 30
4 10 14 40
5 6 11 30
5 8 13 40
As one particular example, say the pair had been 1,10, so that Sam sees the sum is 11 and Pat sees the product is 10. But Sam knows that 11 could be 1+10 or 3+8 or 5+6, the other possibilities already having had an opportunity for being identified by the process defined above for N=6. Similarly, Pat, knowing the product is 10, can't decide between 1,10 and 2,5.
In addition to not being able to decide between or among their respective remaining possibilities, each knows that each of those possibilities is also ambiguous for the other person, as each of them is a perfect logician, who has this table in his/her head. The smallest N for which this happens is N=12, in the case that the two numbers of the pair are different. Previous comments had been based on the false assumption that the two numbers might be equal, in which case this situation presents itself already at N=9.
Edited on March 18, 2007, 3:01 pm
|
|
Posted by Charlie
on 2007-03-18 15:00:07 |
re: ...Huh?
