October 19, 2003
ewd666 part one
I don't know how many parts there will be about ewd666. It's a wicked puzzle, tough to crack. I found it on the website that collects Edsger W. Dijkstra's notes (a wonderful collection btw).
Let's state the problem again:
Of two unknown integer numbers in the range [2..99] inclusive Paul is told the product P and Sam is told the sum S. When asked whether they know the numbers, the following dialogue takes place between Paul and Sam:
Paul: "I don't know them."
Sam: "I already knew that."
Paul: "Then I now know the numbers."
Sam: "Then I now know them too."
The problem is to determine the two numbers from the above data and to prove that the solution is unique.
Spoiler alert: don't continue to read if you want to find your own solution (also don't read more than page one from the pdf file above). I don't have a solution yet, these are pretty raw ideas. Like I said, it's a tough one for me.
Paul says he doesn't know the numbers. He knows the value of the product P = x * y and has two unknowns in x and y. His problem is cleary underdetermined. We should ask ourselves in what cases would Paul know the numbers ie in what cases the problem becomes determined.
We can use the integer factorization of P. If the integer factorization for example yields P = p * q, with p, q primes it's clear that Paul knows the numbers. Are there any other cases ? Here's an example: P = 318, integer factorization of P is in this case P = 318 = 2 * 3 * 53. The only solution that keeps the numbers in the range [2..99] is x = 2 * 3 and y = 53 (interchanging x and y values is considered the same solution).
Refining this idea we get that P = x * y is a unique solution if
forall e: e | x => e * y > 99
( e | x means that e is divisor of x).
The proof is done by contradiction: assume there exists an e | x with e * y <= 99. Then it is clear that x1 -> x / e and y1 -> y * e is another solution of P in contradiction with our assumption that P = x * y is unique.
Paul doesn't know the numbers. So there
exists e: e | x and e * y <= 99.
e is a true divisor of x, x is in the range [2..99] so e can only be in the range [2..49]. e * y <= 99 so y can only be in the range [2..49]. This means that the sum cannot be bigger than 99 + 49 if there's more than one solution to Paul's problem. The sum S <= 148 is therefore a necessary condition. It is not a sufficient condition though (consider x = 2, y = 3, S = 5 < 148 but P = x * y is unique and Paul would know the numbers).
So where does all this leave us ?
We have to find a property (*) of the sum value S so that
(*) => exists e: e | x and e * y <= 99.
...to be continued (hopefully)
Posted by Uwe Hoffmann at October 19, 2003 10:32 PM