A Variation On The "when Is Cheryl's Birthday?" Problem

[jim360]

I was just given this nasty-sounding variation on the birthday problem that's been bugging the internet for the last few days. It goes like this:

Person A chooses a pair of numbers between and including 2 and 99, and finds their sum (S) and Product (P). He then tells one person only the product f the two numbers, and nothing else, and the other person is only toldtheir sum.

Person P says: I do not know what the two numbers are.
Person S says: I already knew that.
Person P says: Oh, then I know what the two numbers are now.
Person S says: Then so do I, now.

What are the two numbers?

[Bazile]

Driving home late the other night , that was discussed on the bbc's radia 4 , late night programme - the one where they have guests from other countries .

Unfortunately i arrived home before they started talking about it , so i missed the answer .

I now await , the answer with much anticipation .

[jim360]

Was that the birthday problem they discussed or the numbers one?

[Bazile]

the numbers one

[jim360]

Really? Wow.

It's been floating around for a while, to be fair, but I wasn't expecting it to make its way into the mainstream as it is rather a lot harder! Must try to find the Radio programme in question -- do you know the name of the programme?

[Bazile]

I can't recall the name - it's one that starts round about 1 o'clock in the morning , where they talk mainly about economics and political matters in other countries .

I dont know if they actually said what the answer is or whether they were just talking about the question

[Jonathan-Joe]

I have seen discussion of this, the number problem, in one of my books. I remember the analysis requires application of the "Goldbach conjecture" - not bread and butter stuff for the amateur mathematician! If I can find the reference, it's probably in a Martin Gardner book, I'll post more later.

[Old_Geezer]

Before I give it any thought, do they have to be different numbers ?

[Gizmonster]

OG - there is only 1 solution to this and yea both numbers are different :)

[Old_Geezer]

Ok, cheers.

Not sure I'm going to get far but we need a product that is not unique to start with.

Next I got to work out why person S knew they were not unique. S can not have unique numbers too as otherwise they'd know the answer.

S must have a small number of possibilities one pair of which must have a product that is not unique.

So all I have to do is make a blooming large table and scour for those conditions ? Sounds like too much fun to me.

[Old_Geezer]

Is this mental arithmetic by any chance ?

[Jonathan-Joe]

Discussion here - http://mathforum.org/library/drmath/view/51609.html .

[jim360]

It's not mental arithmetic, there is a certain logic to it -- unfortunately, there is also some level of having to check various cases against each other.

[jim360]

While Gizmonster is correct that the two numbers are different, they don't have to be -- it is possible to logically exclude that option.

[Old_Geezer]

I spent a short time on this and then recoiled, pointing out to myself sometimes life is too short. Maybe I'll return at some point, perhaps when I have a eureka moment.

[Old_Geezer]

Maybe if I ignored all the large products, started at the smallest, and simply checked each out in turn ? Bit of a cheat but folk have said there is only one combination that works so once found, one can stop.

[jim360]

The problem with that approach is that it's sort of cheating -- I 'know' properties of the answer so will assume without proof. It's a more interesting exercise to derive it.

One way of starting on a journey to the solution is to pick a couple of possible pairs and see how the logic would apply to them, or not. We can classify such pairs in the following way: prime and prime; prime and not prime; not prime and not prime. Then:

For two prime numbers p q, the product pq can be easily factorised straight away, so in fact the guy who knew the product would know the two numbers instantly (in this puzzle, one has to assume that the people P and S are fully capable of arithmetic and logic). Hence without any further work, we can see that at least one of the numbers isn't prime.

On the other hand, suppose both numbers are not prime, eg 24 and 45. Their product also admits factorisations such as 12 and 90, 72 and 15, 36 and 30 etc; while their sum also admits a huge range of options. Although this part of the logic turns out to be unnecessary, it also hopefully serves to illustrate that the solution is unlikely to be two non-primes either; for how, in that case, could one extra piece of information -- that the sum was enough to know that the product was inconclusive -- be enough to separate all of the possible options?

It then appears to follow that one of the two numbers is prime, and the other is not. We can do better, and logically prove that this statement is true, but it's enough to hint that there are better ways to solve this puzzle than by exhaustively searching through all of the c. 5,000 different pairs.

I'll post the rest of the solution later.

[Old_Geezer]

Probably need to write the answer in up-side-down type on page two ;-)

[Old_Geezer]

Anyway a list of 25 primes seems a decent reduction of the issue.

[Old_Geezer]

It has just occurred to me that the method I suggested isn't really cheating at all. The only property info we know is, as Giz said, that there is only one solution. That has to be or P and S can not claim to know THE answer: merely AN answer.

But for sure it'd be nice to find a way not to simply try each in turn. That's still a fairly long job.

[jim360]

You're half-right -- specifically, I meant that the assumption that the numbers are different is not needed, so shouldn't be assumed. It turns out that they are -- and, indeed, have to be.