Sum and Product Puzzle and Prime Factors

Question

Suppose we have two number $X$ and $Y,$ such that $1 < X < Y < 100,$ and $X + Y ≤ 100.$ Sue is given $S = X + Y$ and Pete is given $P = XY.$ They then have the following conversation:

Pete: 'I do not know the two numbers.'

Sue: 'I knew you didn’t know. I don’t know either.'

Pete: 'Now I know the two numbers.'

Sue: 'Now I know the two numbers.'

From this conversation, we can work out $X, Y, S$ and $P$.

According to this paper, which highlights a similar situation, after Sue's statement, we know that the prime factor $q$ of any product of $X$ and $Y$ must be $\le 50$.

I don't understand this, and how the corollary is that the sums must be $\lt 55$. Nor do I understand why when $S = p + 2$ we can safely exclude that sum as Sue's possible number.

I'm trying to implement this in Prolog but I have no idea how to do it if I don't know the thought process for arriving at this conclusion.

Also, if anyone could tell me how applicable this conclusion is with larger numbers, i.e., when $X + Y ≤ 500,$ or $X + Y ≤ 1000.$

Thanks in advance

Answer 1

We know that the prime factors must be $\lt 50$ after Pete's opening statement. If there's a prime factor $\ge 50$ then that must be one of the numbers, which determines the other number.

Example: suppose the product $p$ is 212. Prime factors for this are 53,2,2 - but 106 is not a possible number, so 53 must be one number and 4 the other.

Sue's statement, "I knew you didn't know", eliminates a great many possibilities. It requires that the sum $s=X+Y$ she is looking at can only be produced in cases where the product will be ambiguous. In particular the sum cannot be decomposed into two primes, so it is odd, and cannot be greater than any prime $\gt 50$, so is $53$ or less.

Example: Suppose Sue's number is some even number like 46. Then $X$ and $Y$ might have been, say, 17 and 29 - two primes - so she couldn't have known that Pete wouldn't already know the numbers. Or suppose Sue's number was odd and bigger than 53 - then the numbers might have been 53 and $(s-53)$, in which case Pete would have known the numbers already.

Note that if Sue's number is actually $53$, there isn't a large enough prime smaller than that to make a product that Pete can definitely decompose into $X$ and $Y$. For example, getting $s=53$ from $(6,47)$ would give $p=282$ which could also be from $(3,94)$.