Fog Creek Software
Discussion Board

Three "don't knows" makes a "do know"

Here is a problem that is a bit like the daughters' ages, but goes further.  It's based on a problem I was given in college, but I had a vauge memory of the details so I reinvented it with a new story.

A certain company makes an incredibly powerful parallel computer.  The suprising power of the design is hinged on  arranging the processors in a 2D grid of X by Y.

Two industrial spies have made some observations to try to determine X and Y so that they can sell that information to competitors.  Peter bribed the power supply component accountant.  He now knows the system's electical power usage and has been able to determine the total number of processors.  Sam photographed the system motherboard assembly line.  He knows the perimiter of the processor area on motherboard and the size of each processor.  A leaked corporate email makes it widely known that X and Y are each between 2 and 9 (inclusive) and that X != Y.

The two spies then had the following discussion.

Sam:  I know the sum.
Peter: I know the product.
Sam: I have thought about it carefully, but I don't know X and Y.
Peter: I also thought about it, and what you just said, and I don't know X and Y either.
Sam: Just a sec... Darn!  I still don't know.
Peter: Ha. Thanks dude, now I know X and Y.

Jason Robbins
Thursday, March 24, 2005

Woops, I hit "Post Message" too soon.

The overall question is: What are X and Y?  If they cannot be determined, can you list the possiblities?

Jason Robbins
Thursday, March 24, 2005

Peter does not know the numbers even though he knows the product. So this product must be
12: 2x6 (sum8) or 3x4 (sum7)
18: 2x9 (sum11) or 3x6 (sum9)
24: 6x4 (sum10) or 3x8 (sum11)

when peter tells sam he doesnt know,

Sam sees filters out the possibilities that do not match his sum.

When Sam says he does not know, we all now know that Sam's sum must have been 11 and cannot figure if its 2,9 or 3,8 for if his sum was different he would then know.

Peter who knows the product can determine which it is but Sam and the rest of us are still in the dark as to what the numbers are and only know that the sum is 11

I heard another version where after the one person figures it out, the other one uses this information to figure it all out.  something like

P: i know the product
S: i know the sum
P: i dont know the the sum
S: i dont know the product
P: i still dont know the sum
S: i still dont know the product either

(a few hours pass)
P: I now know the sum
S: I now know the product

Thursday, March 24, 2005

WanFactory, your answer is correct.  Actually, it implicitly points out the the first admission by Sam is not really helpful to Peter.

In your version, what is the significance of a few hours passing?

Jason Robbins
Friday, March 25, 2005

i think I found the original problem:

Monday, March 28, 2005

Try this one (public knowledge: both numbers are between 2 and 100 and may or may not be equal):

P: I know the product.
S: I know the sum, it's too bad you don't know the numbers.
P: But I do now.
S: As do I.
P: And every else who has heard our conversation.

Monday, April 4, 2005

*  Recent Topics

*  Fog Creek Home