You have Plato and Socrates, two transhuman intelligences, over for tea.
You roll two 100-sided dice, producing two numbers x and y, both between 1 and 100.
You tell Plato the product, and Socrates the sum of the numbers, and they have the following dialogue:
Plato: I don’t know the values x and y.
Socrates: I knew you didn’t know. I don’t know them either.
Plato: Now I know x and y.
Socrates: Now I know them too.
How did they work it out? What were x and y?
Wednesday, August 18, 2010
Subscribe to:
Post Comments (Atom)
Before the next person comes up to me and says triumphantly "a number and another number", it's not quite the same question as the Microsoft one.
ReplyDeleteAnd the answer is slightly more complicated.
Alternatively some more people have said that they don't understand the Microsoft solution. One way to understand it (and to check that you understand it) is to adapt it to the question above.
I have a program which solves this general sort of question, which I wrote mainly on intuition. I'll post it on my Clojure blog when I've figured out how to explain it, and put a link to it here.
Plato's statement tells us that at least one of x, y is not prime, due to the fundamental theorem of arithmetic or algebra, or whichever one it is.
ReplyDeleteSocrates's statement tells us that he knew at least one of x, y is not prime, so x+y isn't even (from Goldbach's), and it can't be 2 greater than a prime (because that would make x,y both prime). I can't be bothered to look for all numbers less than 101 that satisfy that - there must be at least 20.
Presumably of all the ways there are of factorising xy, there's only one decomposition that sums to a number on Socrates' list. Which is how Plato knew x and y. But how can he know which is x and which is y? Multiplication commutes.
I guess Socrates uses the uniqueness of Plato's solution to examine all possible sums from his original reduced list, to check that there's only one that satisfies the product conditions. But again, as addition commutes, he can work out {x,y}={a,b}, but he can't work out x=a and y=b.
Or perhaps Plato and Socrates are lying transhuman intelligent bastards, and they haven't got a clue what x and y are.
I shall now go and Google the Microsoft problem and answer.