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
or
X=4,Y=9...  => P=36 => could have (6,6) or (4,9)...  Max doesn't know
or
X=5,Y=8...  => P=40 => could have (4,10) or (5,8)... Max doesn't know
or
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
E-mail: levin@hmc.edu