All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Two Logicians Lockout (Posted on 2007-03-13)
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?

 See The Solution Submitted by Brian Smith Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 2 of 9 |

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

 Search: Search body:
Forums (0)