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

Home > Logic
Two Logicians Lockout (Posted on 2007-03-13) Difficulty: 3 of 5
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.)
Some Thoughts 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information