HMC Math 55: Discrete Mathematics
Hint for Martian problem

	The first question you need to ask is, for what sums S can Sam say to 
Max "You don't know what X & Y are"?  How about S=10?  Well, if S=10, for all
Sam knows he might have...
X=3,Y=7... => P=21. 
But if P=21, Max knows X=3,Y=7.  So Sam can't make the claim he did with certainty,
because X & Y might be (3,7).
On the other hand, if S=13...

X=3,Y=10... => P=30 => could have (5,6) or (3,10)... Max doesn't know
X=4,Y=9...  => P=36 => could have (6,6) or (4,9)...  Max doesn't know
X=5,Y=8...  => P=40 => could have (4,10) or (5,8)... Max doesn't know
X=6,Y=7...  => P=42 => could have (3,14) or (6,7)... Max doesn't know

Regardless, if S=13, Sam can say with certainty that Max doesn't know X & Y 
based on P.  Of course, there are other values of S for which this is true.  
This is how figuring out the problem STARTS (there's still a lot of work ahead,
and the solution is more brute force than it is elegant ;-)
	Also, something known as Goldbach's conjecture might come in handy.

	Hope this helps.

Return to: Discrete Homework * Discrete Main Page * Professor Greg's Page