Sam and Polly and How I Know the Answer.

So anyway, I’m too lazy to write an original post, so I’ll just copy a draft of my report that I turned in for this project.

The Problem:

An alien appears to two mathematicians, Sam and Polly.  The alien says, “I’m thinking of two numbers, X and Y with 3 <= X <= Y <= 97.  I will tell their sum to Sam and their product to Polly.”  The alien does this and then disappears.  The following conversation occurs:
Sam:  You don’t know what X and Y are.
Polly:  That’s true, but now I do.
Sam:  And now I do too.
Find X and Y.

The Solution:

In solving this problem it is important to first understand what information we’re given from the conversation.  Let’s start by examining the first two statements made in the conversation.  Sam first states that Polly does not know the numbers and Polly responds confirming this.  How could Sam know this?  Let’s first consider pairs of numbers which have only one possible product in the range [3, 97].  Since Polly is a mathematician we assume that she knows how to factor integers, so she could factor her product into a product of primes.  If Polly’s product (we’ll call it P) has only 2 prime factors then it is obvious that she would know the pair of numbers since the prime factorization is unique.  But products that have two prime factors are not the only ones which would permit Polly to find the pair given only P.  An example of one of these products is 318 whose prime factorization is 2*3*53.  These prime factors can be grouped into pairs in 3 different ways: 6*53, 2*159, and 3*106.  However, two of these products are invalid, since one of their terms lies outside of [3, 97].  So Polly could deduce the pair from this product.

So what does it mean about Sam’s sum if he knows that Polly cannot deduce the pair from her product?  For a given sum, S, Sam can enumerate all possible pairs which could result in that sum.  For each candidate pair he can compute the product and determine whether or not Polly could know the pair given only the product.  Since he states that Polly does not know the pair, we know that none of his candidate pairs could have a product expressible in only one valid way.  We can determine which possible sums possess this property using a brute-force approach.  This approach is feasible in this case due to the relatively small scale of the problem.  Doing this, we find that there are, in fact, only 10 possible sums (see attached) which have this property.

Based on the second two statements of the conversation we know that initially neither Sam nor Polly could figure out the pair from the information they were given.  Using this we can compute a list of candidate pairs such that neither Sam nor Polly could deduce the pair from their sum or product.  Using the above result, we can further reduce the number of candidate pairs by eliminating those whose sum is not one of the 10 possible.

Next we consider the fact that Polly can figure out the answer after hearing Sam’s first statement.  This can be done by grouping the candidate pairs found above according to their product.  Each group contains pairs with equal products.  The groups which only have 1 pair contain the pairs that Polly could figure out based on Sam’s first statement and her own product.  This is valid because Polly could compute the possible sums just as we did above and use that information to eliminate all but one of her possible pairs.

Similarly, the remaining pairs can be grouped according to their sum and those groups that have only one pair are those that Sam could figure out given that Polly figured out her answer.  He can do this following the same analysis that we have.  What we find is that only one group contains a single pair and that pair is X = 13, Y = 16.  This must, therefore, be the solution.

The Code

First we define a function which will give all pairs of divisors of a given number.  For example, given 24 it would return {{1, 24}, {2, 12}, {3, 8}, {4, 6}}.  There’s a second version of the function which will only return those divisor pairs such that both numbers fall in a specific range.

DivisorPairs[n_] := Module[{d = Divisors[n]},
   Union[Sort /@ Transpose[{d, Reverse[d]}]]];
DivisorPairs[n_, {lo_, hi_}] :=
  Select[DivisorPairs[n], lo <= #[[1]] <= #[[2]] <= hi &];

Create a function which returns addend pairs for a given value.  Given 5, this returns {{1, 4}, {2, 3}}.  Similarly, this function can also return only those pairs that fall within a specific range.

AddendPairs[n_, {lo_, hi_}] := Table[{i, n - i}, {i, Max[lo, n - hi], n/2}];
AddendPairs[n_] := AddendPairs[n, {1, n}];

List of possible sums such that Sam knows that Polly can’t know the number pair.  These are all the sums such that all potential pairs have products that can be represented in more than one way.  For each potential sum, we compute the addend pairs of that sum and check the divisor pairs of the product of each.  If there’s only one divisor pair for one of the products that means that Sam couldn’t be 100% sure that Polly doesn’t know the pair.

possibleSums = Select[
  Table[i, {i, 6, 194}],
  Min[
     (Length[DivisorPairs[Times @@ #, {3, 97}]] &) /@
      AddendPairs[#, {3, 97}]
     ] > 1 &
  ]
{13, 19, 25, 29, 31, 37, 43, 49, 53, 55}

Possible pairs such that neither Sam nor Polly could know the pair given their sum and product.  These are all the pairs such that both their sum and product can be represented more than one way with different pairs.

candidatePairs =
  Select[Flatten[
      Table[{AddendPairs[i + j, {3, 97}],
        DivisorPairs[i j, {3, 97}], {i, j}}, {i, 3, 97}, {j, i, 97}], {2, 1}],
     Length[#[[1]]] > 1 && Length[#[[2]]] > 1 &][[All, 3]] // Sort;

Now select only those pairs whose sum is one of the possible sums computed above.

candidatePairs2 = Select[candidatePairs, MemberQ[possibleSums, Total[#]] &]

Now eliminate those pairs whose product shows up more than once in this list.  This accounts for the fact that Polly can actually figure out the numbers after she finds out that Sam knows that she doesn’t know the numbers.

candidatePairs3 = Flatten[
  Select[Split[SortBy[candidatePairs2, Times @@ # &],
    Times @@ #1 == Times @@ #2 &], Length[#] == 1 &], {2, 1}];

We now have a list of pairs which the alien could have picked which Sam and Polly don’t know.  However, Sam knows that Polly doesn’t know and this information is sufficient for Polly to figure out the pair.  We now need to account for the information that since Polly was able to figure out the answer Sam can too.  We do this by eliminating those pairs whose sums appear more than once like done above with the products.

candidatePairs4 = Flatten[
   Select[Split[SortBy[candidatePairs3, Total], Total[#1] == Total[#2] &],
    Length[#] == 1 &], {2, 1}]
{{13, 16}}

This leaves only one pair in our list, so this must be the answer.

2 Responses to “Sam and Polly and How I Know the Answer.”

  1. Ladislav says:

    Hey Yourself! I bet you’ll like this. I found the following problem recently, I find it really intriguing and beautiful, I have just started attempting to solve it. If you happen to think about it, let me know if you solved it, how much time did you need, etc.

    Problem:
    a) Two positive integers are chosen. The sum is revealed to logician A, and the sum of squares is revealed to logician B. Both A and B are given this information and the information contained in this sentence. The conversation between A and B goes as follows: B starts

    B: ` I can’t tell what they are.’
    A: ` I can’t tell what they are.’
    B: ` I can’t tell what they are.’
    A: ` I can’t tell what they are.’
    B: ` I can’t tell what they are.’
    A: ` I can’t tell what they are.’
    B: ` Now I can tell what they are.’

    What are the two numbers?

    b) When B first says that he cannot tell what the two numbers are, A receives a large amount of information. But when A first says that he cannot tell what the two numbers are, B already knows that A cannot tell what the two numbers are. What good does it do B to listen to A?

  2. Andrew says:

    @Ladislav: when B can’t tell what they are, A learns a lot. When A can’t tell what they are (the first time), B learns that A couldn’t figure it out with what B knew, and this removes a few possibilities. I suppose it works like this over and over again until eventually, one possibility is left.