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?

It seems it is hard to say explicitly, for any particular sum/product, how many turns it will be guessed in if this number gets big, so calculating the table seems to be the easiest solution.

One way to look at the data Charlie has computed is as an undirected graph. Let a N-graph be a graph consisting of "sum nodes" and "product nodes", and let there be an edge between a sum node and product node if and only if there are a pair distinct numbers 1 to N, where there sum is the sum node, and their product is the product node.

For each pair of numbers, one edge will corrospond to that pair of numbers (by connecting Sam's sum node with Pat's product node); Sam knows possiblilities for Pat's product, given his sum, and Pat knows possiblities for Sam's sum, given his product. (These possiblities are other "product nodes" connected to Sam's sum node, and other "sum nodes" connected to Pat's product node.)

So if Sam's sum node has only one edge leaving it, there is only has one choice for Pat's product node, and thus can figure out what the numbers are. (Thus, label each node by the the fewest number of nodes it is from one of these end nodes, thus one of these end nodes would be a 0-node, and any non-end-node connecting would be a 1-node, and so on.)

If not, that still gives Pat information, since Sam is a perfect logician. Pat can eliminate all sum nodes connected to the product node which are 0-nodes, leaving all other nodes , since Sam said he didn't know. If he has a 0-node himself, or only one sum node is left, that must be it. Otherwise, Pat won't know either.

Thus, Sam can eliminate all product nodes which are 0-nodes or 1-nodes. leaving only 2-nodes, 3-nodes, and so on. In each turn, each removes possiblities to which the other would have guessed last turn if were it.


So the question of "when will they never be able to figure out the numbers" is answered when a node is unable to be labelled with a number, as labelling of a number indicates it will be eliminated at some point. This happens when a cycle is introduced into the graph, as there is more than one possible edge from every sum or product node in that graph.

Since a N-graph contains all the edges of a N-1 graph, N-2 graph... then we just need to find when an edge is added which would form a cycle. By examining the data found, we find that when N = 12 two cycles are added: ( The depiction (Sum node)-two numbers-which form edge-[Product node] is used to show the alternate route.)

When (13)-1-12-[12] is added, (13)-3-10-[30]-5-6-(11)-1-10-[10]-2-5-(7)-3-4-[12] forms an alternate route.

When (14)-2-14-[24] is added,
(14)-4-10-[40]-5-8-(13)-3-10-[30]-5-6-(11)-3-8-[24] forms an alternate route.


So if the sum is 7, 11, 13, or 14, or equivalently, the product is 10, 12, 24, 30, or 40, neither Sam nor Pat will ever be able to eliminate all but one possiblity for what the two numbers are, and thus neither one will ever be able know what they are.

Posted by Gamer on 2007-03-18 16:46:56