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?
The below summarizes the conclusions that Sam or Pat can make on turn x, where Sam gets the odd turns and Pat the even ones. The first number on each line is the value of N. The four numbers in the middle are the two numbers chosen and their sum and product.
So, for example, the line that says
4 Sam says 1 4 5 4 in turn 3
indicates that if, when N is 4, the chosen numbers are 1 and 4, Sam will guess it on turn 3 (his own second turn), as he has seen that Pat did not guess 2,3 on her turn (the other possible sum of 5), because Pat must have seen a product of 4, which for her was ambiguous between 1,4 and 2,2.
With N less than 9, all possible pairs of numbers are accounted for (they are guessed). When N is 9, once turn 10 passes (each player has had 5 opportunities), they both know that no one will get it. Of course Pat knows this first, as she is the one to say the final "I don't know".
3 Sam says 1 1 2 1 in turn 1
3 Sam says 1 2 3 2 in turn 1
3 Sam says 2 3 5 6 in turn 1
3 Sam says 3 3 6 9 in turn 1
3 Pat says 1 3 4 3 in turn 2
3 Pat says 2 2 4 4 in turn 2
4 Sam says 1 1 2 1 in turn 1
4 Sam says 1 2 3 2 in turn 1
4 Sam says 3 4 7 12 in turn 1
4 Sam says 4 4 8 16 in turn 1
4 Pat says 1 3 4 3 in turn 2
4 Pat says 2 3 5 6 in turn 2
4 Pat says 2 4 6 8 in turn 2
4 Pat says 3 3 6 9 in turn 2
4 Sam says 1 4 5 4 in turn 3
4 Sam says 2 2 4 4 in turn 3
5 Sam says 1 1 2 1 in turn 1
5 Sam says 1 2 3 2 in turn 1
5 Sam says 4 5 9 20 in turn 1
5 Sam says 5 5 10 25 in turn 1
5 Pat says 1 3 4 3 in turn 2
5 Pat says 1 5 6 5 in turn 2
5 Pat says 2 3 5 6 in turn 2
5 Pat says 2 4 6 8 in turn 2
5 Pat says 2 5 7 10 in turn 2
5 Pat says 3 3 6 9 in turn 2
5 Pat says 3 4 7 12 in turn 2
5 Pat says 3 5 8 15 in turn 2
5 Pat says 4 4 8 16 in turn 2
5 Sam says 1 4 5 4 in turn 3
5 Sam says 2 2 4 4 in turn 3
6 Sam says 1 1 2 1 in turn 1
6 Sam says 1 2 3 2 in turn 1
6 Sam says 5 6 11 30 in turn 1
6 Sam says 6 6 12 36 in turn 1
6 Pat says 1 3 4 3 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 3 6 9 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 4 8 16 in turn 2
6 Pat says 4 5 9 20 in turn 2
6 Pat says 4 6 10 24 in turn 2
6 Pat says 5 5 10 25 in turn 2
6 Sam says 2 2 4 4 in turn 3
6 Sam says 2 6 8 12 in turn 3
6 Pat says 1 4 5 4 in turn 4
6 Pat says 3 4 7 12 in turn 4
6 Sam says 1 6 7 6 in turn 5
6 Sam says 2 3 5 6 in turn 5
7 Sam says 1 1 2 1 in turn 1
7 Sam says 1 2 3 2 in turn 1
7 Sam says 6 7 13 42 in turn 1
7 Sam says 7 7 14 49 in turn 1
7 Pat says 1 3 4 3 in turn 2
7 Pat says 1 5 6 5 in turn 2
7 Pat says 1 7 8 7 in turn 2
7 Pat says 2 4 6 8 in turn 2
7 Pat says 2 5 7 10 in turn 2
7 Pat says 2 7 9 14 in turn 2
7 Pat says 3 3 6 9 in turn 2
7 Pat says 3 5 8 15 in turn 2
7 Pat says 3 6 9 18 in turn 2
7 Pat says 3 7 10 21 in turn 2
7 Pat says 4 4 8 16 in turn 2
7 Pat says 4 5 9 20 in turn 2
7 Pat says 4 6 10 24 in turn 2
7 Pat says 4 7 11 28 in turn 2
7 Pat says 5 5 10 25 in turn 2
7 Pat says 5 6 11 30 in turn 2
7 Pat says 5 7 12 35 in turn 2
7 Pat says 6 6 12 36 in turn 2
7 Sam says 2 2 4 4 in turn 3
7 Sam says 2 6 8 12 in turn 3
7 Pat says 1 4 5 4 in turn 4
7 Pat says 3 4 7 12 in turn 4
7 Sam says 1 6 7 6 in turn 5
7 Sam says 2 3 5 6 in turn 5
8 Sam says 1 1 2 1 in turn 1
8 Sam says 1 2 3 2 in turn 1
8 Sam says 7 8 15 56 in turn 1
8 Sam says 8 8 16 64 in turn 1
8 Pat says 1 3 4 3 in turn 2
8 Pat says 1 5 6 5 in turn 2
8 Pat says 1 7 8 7 in turn 2
8 Pat says 2 5 7 10 in turn 2
8 Pat says 2 7 9 14 in turn 2
8 Pat says 3 3 6 9 in turn 2
8 Pat says 3 5 8 15 in turn 2
8 Pat says 3 6 9 18 in turn 2
8 Pat says 3 7 10 21 in turn 2
8 Pat says 4 5 9 20 in turn 2
8 Pat says 4 7 11 28 in turn 2
8 Pat says 4 8 12 32 in turn 2
8 Pat says 5 5 10 25 in turn 2
8 Pat says 5 6 11 30 in turn 2
8 Pat says 5 7 12 35 in turn 2
8 Pat says 5 8 13 40 in turn 2
8 Pat says 6 6 12 36 in turn 2
8 Pat says 6 7 13 42 in turn 2
8 Pat says 6 8 14 48 in turn 2
8 Pat says 7 7 14 49 in turn 2
8 Sam says 1 8 9 8 in turn 3
8 Sam says 2 2 4 4 in turn 3
8 Sam says 2 4 6 8 in turn 3
8 Sam says 3 8 11 24 in turn 3
8 Pat says 1 4 5 4 in turn 4
8 Pat says 4 6 10 24 in turn 4
8 Sam says 2 3 5 6 in turn 5
8 Sam says 2 8 10 16 in turn 5
8 Pat says 1 6 7 6 in turn 6
8 Pat says 4 4 8 16 in turn 6
8 Sam says 2 6 8 12 in turn 7
8 Sam says 3 4 7 12 in turn 7
9 Sam says 1 1 2 1 in turn 1
9 Sam says 1 2 3 2 in turn 1
9 Sam says 8 9 17 72 in turn 1
9 Sam says 9 9 18 81 in turn 1
9 Pat says 1 3 4 3 in turn 2
9 Pat says 1 5 6 5 in turn 2
9 Pat says 1 7 8 7 in turn 2
9 Pat says 2 5 7 10 in turn 2
9 Pat says 2 7 9 14 in turn 2
9 Pat says 3 5 8 15 in turn 2
9 Pat says 3 7 10 21 in turn 2
9 Pat says 3 9 12 27 in turn 2
9 Pat says 4 5 9 20 in turn 2
9 Pat says 4 7 11 28 in turn 2
9 Pat says 4 8 12 32 in turn 2
9 Pat says 5 5 10 25 in turn 2
9 Pat says 5 6 11 30 in turn 2
9 Pat says 5 7 12 35 in turn 2
9 Pat says 5 8 13 40 in turn 2
9 Pat says 5 9 14 45 in turn 2
9 Pat says 6 7 13 42 in turn 2
9 Pat says 6 8 14 48 in turn 2
9 Pat says 6 9 15 54 in turn 2
9 Pat says 7 7 14 49 in turn 2
9 Pat says 7 8 15 56 in turn 2
9 Pat says 7 9 16 63 in turn 2
9 Pat says 8 8 16 64 in turn 2
9 Sam says 2 2 4 4 in turn 3
9 Sam says 4 9 13 36 in turn 3
9 Sam says 6 6 12 36 in turn 3
9 Pat says 1 4 5 4 in turn 4
9 Sam says 2 3 5 6 in turn 5
9 Pat says 1 6 7 6 in turn 6
9 Sam says 3 4 7 12 in turn 7
9 Pat says 2 6 8 12 in turn 8
9 Sam says 4 4 8 16 in turn 9
9 Pat says 2 8 10 16 in turn 10
9
1 8 9 8
1 9 10 9
2 4 6 8
2 9 11 18
3 3 6 9
3 6 9 18
3 8 11 24
4 6 10 24
So when Pat gets her fifth turn (turn 10 of the game) she knows that she doesn't know the answer, and that neither does Sam. In each of the possible sums and products there are two choices for the pair of numbers.
The program for the above is in Visual Basic 5.0 (only the procedural portion shown):
Dim n1(), n2(), tot(), prod(), i, n, subLim, turn
Dim prodPtr(), totPtr()
Private Sub cmdStart_Click()
Open "two logicians lockout.txt" For Output As #2
ReDim n1(6), n2(6), tot(6), prod(6), prodPtr(6), totPtr(6)
n1(1) = 1: n2(1) = 1: tot(1) = 2: prod(1) = 1
n1(2) = 1: n2(2) = 2: tot(2) = 3: prod(2) = 2
n1(3) = 1: n2(3) = 3: tot(3) = 4: prod(3) = 3
n1(4) = 2: n2(4) = 2: tot(4) = 4: prod(4) = 4
n1(5) = 2: n2(5) = 3: tot(5) = 5: prod(5) = 6
n1(6) = 3: n2(6) = 3: tot(6) = 6: prod(6) = 9
For i = 1 To 6
prodPtr(i) = i: totPtr(i) = i
Next
n = 3
subLim = 6
Do
For i = 1 To subLim
prodPtr(i) = i: totPtr(i) = i
Next
' Shell sorts for prod and tot arrays
span = Int(subLim / 3)
Do
For i = 1 To subLim - span
j = i
Do While prod(prodPtr(j)) < prod(prodPtr(j + span))
swap prodPtr(j), prodPtr(j + span)
j = j - span
If j <= 0 Then Exit Do
Loop
Next
oldSpan = span
span = Int(span / 3)
If oldSpan > 1 And span < 1 Then span = 1
Loop Until oldSpan = 1
span = Int(subLim / 3)
Do
For i = 1 To subLim - span
j = i
Do While tot(totPtr(j)) < tot(totPtr(j + span))
swap totPtr(j), totPtr(j + span)
j = j - span
If j <= 0 Then Exit Do
Loop
Next
oldSpan = span
span = Int(span / 3)
If oldSpan > 1 And span < 1 Then span = 1
Loop Until oldSpan = 1
remain = subLim
turn = 0
Do
pRemain = remain
turn = turn + 1
pFound = 0: nFound = 0: pSub = 0: largestNo = 0
For i = 1 To subLim
t = tot(totPtr(i))
If t > 0 Then
If t = pFound Then
nFound = nFound + 1
Else
If nFound > largestNo Then largestNo = nFound
If nFound = 1 Then
tot(totPtr(pSub)) = -1
remain = remain - 1
End If
nFound = 1
pFound = t
End If
pSub = i
End If
Next
If nFound = 1 Then
tot(totPtr(pSub)) = -1
remain = remain - 1
End If
For i = 1 To subLim
If tot(i) = -1 Then
Call found("Sam")
End If
Next
For i = 1 To subLim
If tot(i) = -1 Then prod(i) = 0: tot(i) = 0
Next
turn = turn + 1
pFound = 0: nFound = 0: pSub = 0: largestNo = 0
For i = 1 To subLim
t = prod(prodPtr(i))
If t > 0 Then
If t = pFound Then
nFound = nFound + 1
Else
If nFound > largestNo Then largestNo = nFound
If nFound = 1 Then
prod(prodPtr(pSub)) = -1
remain = remain - 1
End If
nFound = 1
pFound = t
End If
pSub = i
End If
Next
If nFound = 1 Then
prod(prodPtr(pSub)) = -1
remain = remain - 1
End If
For i = 1 To subLim
If prod(i) = -1 Then
Call found("Pat")
End If
Next
For i = 1 To subLim
If prod(i) = -1 Then tot(i) = 0: prod(i) = 0
Next
Loop Until pRemain = remain
If remain > 1 Then
Print n
Print #2, n
For i = 1 To subLim
If tot(i) > 0 Then
Print n1(i); n2(i); tot(i); prod(i)
Print #2, n1(i); n2(i); tot(i); prod(i)
End If
Next
DoEvents
Close
Exit Sub
End If
n = n + 1
subLim = n * (n - 1) / 2 + n
ReDim n1(subLim), n2(subLim), tot(subLim), prod(subLim)
ReDim prodPtr(subLim), totPtr(subLim)
i = 1
For a = 1 To n: For b = a To n
n1(i) = a: n2(i) = b: tot(i) = a + b: prod(i) = a * b
i = i + 1
Next: Next
Print
Print #2,
Loop
Close
End Sub
Sub swap(a, b)
h = a: a = b: b = h
End Sub
Sub found(pers$)
Print n; pers$; " says ";
Print n1(i); n2(i); n1(i) + n2(i); n1(i) * n2(i); "in turn"; turn
Print #2, n; pers$; " says ";
Print #2, n1(i); n2(i); n1(i) + n2(i); n1(i) * n2(i); "in turn"; turn
End Sub
It uses internal Shell sorts to place arrays of pointers to the pairs of numbers, in the order of the sums, and of the products, of the pointed-at pairs.
|
|
Posted by Charlie
on 2007-03-14 09:04:00 |
computer solution
