Here’s a further link with explanation and solution to the puzzle above, for those interested.
I’m not sure if the birthday puzzle is necessarily related. This type of logic puzzle is fairly common, in my experience, and I suspect much older than 1969 (which is where your puzzle comes from.)
As for how to make them, I assume you’d start with something like my “near-trivial” example above, and build up from there.
And there’s no limit on complexity. Here’s one you won’t want to attempt by hand:
~ ~ ~ ~ ~ ~ ~
Dr. Socrates is testing two of his expert logicians, Samuel and Patricia, while Anthony listens on. You are working on a 3-D Sudoku but your ears perk up when you realize Dr. Socrates is presenting a difficult puzzle.
“I’ve picked two different integers and want you two to figure out what they are. I’ll tell Samuel the sum which is positive and no bigger than (mumble). I’ll tell Patricia the product which is larger than the sum.”
Here Dr. Socrates whispers a number in Samuel’s ear and another number in Patricia’s ear. Samuel, Patricia, and Anthony all heard the integer the Doctor imposed as a bound on the sum, but you were still daydreaming and missed it.
Now Patricia says “I don’t know the numbers.”
Samuel says “I already knew you didn’t; I don’t know them either.”
Patricia says “I still don’t know the numbers.”
Samuel says “And still neither do I.”
Patricia says “Oh? Now I DO know the numbers.”
Samuel says “And now, so do I.”
Anthony says “Interesting. Patricia’s product was a 3-digit number but, to achieve the same result with a larger 3-digit product, the bound on the sum would have needed to be increased, and the first available such 3-digit product would have been some hundreds bigger than Patricia’s product.”
What was the bound Dr. Socrates mumbled? What were the numbers?
Here’s what they would have said if they fully explained themselves.
Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know too {because I know the month does not contain a unique date, such as May and June}.
Bernard: At first I don’t know when Cheryl’s birthday is, but I know now {because the day is unique to the only remaining months}.
Albert: Then I also know when Cheryl’s birthday is {Because the month I was given only had two possibilities and if the day were 14, Bernard would not have been able to deduce the complete date}.
It must be July 16.
Its not too hard, you just decide what statement you want that passes on the information (such as A knows B doesn’t know the date) and then create a set of situations that this information eliminates (singletons in May and June). Then you go on to the next piece of information (B now knows the Brithday) so make two of the dates singletons now that (May and June have been eliminated). etc.
In case it wasn’t posted, The New York Times has a good explainer:
There actually are two incorrect answers that at least had some support. Watch this video from Dr. James Grime.
Note, they are definitely both incorrect.
I was thinking some more about this yesterday and I now realize I was wrong. I focused too much on the idea that Albert and Bernard had to figure out Cheryl’s birthday from the statements they were making and I didn’t consider that each of them also had additional information. Reading the puzzle, we don’t know what month Albert was told but of course he does. So it’s possible for him to pinpoint the birthday using both the information he was given by Cheryl and the information he got from the statements.
Short version: I was wrong.
This is just absurdly difficult.
Without loss of generality, I’ll assume that a<b for all pairs [a, b].
[spoiler]“I’ve picked two different integers and want you two to figure out what they are. I’ll tell Samuel the sum which is positive and no bigger than (mumble). I’ll tell Patricia the product which is larger than the sum.”
Both the sum and product are positive, so therefore both numbers are positive. Also, since the product is larger than the sum, neither number is 0 or 1 (since 0N <= N+0 and 1N < 1+N).[/spoiler][spoiler]Now Patricia says “I don’t know the numbers.”
From this, the product cannot be the multiple of two primes (if it were 15, she would know the numbers are [3, 5] (since [1, 15] is out)).
It also can’t be the third or fourth power of a prime. 27 could only be [3, 9]. And 81 could only be [3, 27] ([9, 9] doesn’t work).
I’m probably missing some other possibility here, but I can’t think of one.[/spoiler][spoiler]Samuel says “I already knew you didn’t; I don’t know them either.”
Let’s start with the first statement. If Samuel already knew that Patricia didn’t know the numbers, then it means that whatever the sum is, all possibilities for a*(S-a) have non-unique representations (i.e., they’re not in the set that I excluded previously). I’m not sure exactly how many pairs that excludes, but we can say that the sum (and the bound) is at least 11: the possible pairs are 29=18, 38=24, 47=28, and 56=30, but each of those products have different representations, and had Patricia gotten them she couldn’t have known the answer.
I feel like it must, but I don’t see yet how the second part of the statement gives us any additional information. It means the sum could not have been 5, but we already knew that.[/spoiler]That’s all I’ve got so far. I think it demands a computer program, but I’m not even certain how to structure it. At least not efficiently. In principle, each person has to consider all the possible universes that the others belong to, and this could conceivably include their beliefs about the universes that you belong to, and so on. It seems exponential. But maybe it’s not actually that hard.
At least Anthony’s statement narrows down the possibilities for a brute-force search, though it seems like cheating to take it into account early on.
Why? That restriction isn’t in the puzzle.
I’m working on a solution and so far have learned about semi-primes and the Goldbach conjecture which are both helpful in winnowing a solution.
I’ve also restricted the product space to under 1000 though strictly I shouldn’t because that bit of information doesn’t come till later. I’m now down to 115 potential products and 250 potential sums. And I have just realised I’ve lost most of my sunny Sunday morning!
I may owe to Dopers an apology for wasting their times. But I did warn you …
I tend to err with understatement rather than exaggeration. And I did write "“won’t want (to attempt)” rather than “may not want.”
Yeah, I tried to warn you. 
Composing logic puzzles has been a hobby of mine for a while – you might even discover my true name if you peruse the 5-star puzzles in Dell Logic Puzzles. I don’t know why I composed this particular puzzle and posted it. I think it’s more masochism – it takes effort to compose – than sadism – I really thought the warning would take.
If you really insist on solving it, you might start at the Wikipedia page cited upthread which has a python program (I didn’t – I only program in C), add the two extra loops implied by my slightly more involved construction, and run the program for a range of limits instead of just limit=100. But I’m afraid even pursuing this would still be masochistic…
Although it doesn’t state it explicitly, I think we can infer that the order of the numbers is irrelevant. There’s no way to get an ordering from a sum or product, and it would be silly for Dr. Socrates to reject [3, 5] (say) as an answer because the “real” answer is [5, 3]. So I choose numeric order for simplicity in combining equivalent answers.
Nah, I’m a programmer and writing a search program is not difficult. I’m using Perl. The difficulty is in applying the constraints correctly. But I think I have a line on the answer… maybe. Thanks for the puzzle, at any rate.
And after writing a script…
Looks like I didn’t miss anything in my initial conclusion about Patricia. Between 0 and 999, there are 524 numbers which aren’t of the form p, p[sup]3[/sup], p[sup]4[/sup], or p*q, where p and q are both primes. I get the same number if I just try to count uniqueness directly.[spoiler]Samuel’s first statement seems to give a lot of information. Unless I messed up, the complete list of possible sums he has is the following (for products<1000):
11 17 23 27 29 35 37 41 47 51 53 57 59
In other words, for each number not on that list, there is at least one possibility that gives an unambiguous answer. A sum of 12 could have been 57=35. 44 could have been 341=123. But for the numbers on the list, every single product possibility had some other possible answer.[/spoiler][spoiler]From here, though, something goes wrong with my strategy.
Patricia still doesn’t know the numbers after she’s reduced the list of sums. It must be that the remaining products are still ambiguous given that list. I get the following:
30 42 60 66 70 72 78 90 102 110 114 120 126 132 150 162 168 180 196 210 264 270 286 300 306 312 322 330 342 364 378 396 408 420 462 540 546 630 660 702
And Samuel still doesn’t know, though it barely helps us–the list of sums has only been reduced to:
17 23 27 29 35 37 41 47 51 53 57 59
(we eliminated 11 since it only could have been 5*6=30)
Supposedly, though, Patricia now knows the answer. The only product which has a unique sum is 30 (which appears with a sum of 2+15=17).
But this conflicts with Anthony’s statement later. I think I need to take the bound into account earlier. Maybe try the process for all possible bounds. At least that’s the only way I can make sense of the logic.[/spoiler]
But you rejected considering a=b which as you point out in the 81 case has a potential solution [9,9] (as well as [27,3]). Actually there are only 3 numbers in this category 16, 81, 625 that would be excluded as potential products using your rule. The other perfect squares have ambiguous factor sets.
The puzzle says:
I’ve picked two different integers and want you two to figure out what they are.
So [9, 9] is out, and [27, 3] is the same as [3, 27]. And of course [1, 81] is out because 1*81 is not larger than 1+81. So if the product was 81, Patricia would know for certain that the numbers were [3, 27] based on what Dr. Socrates said to everyone.
But Albert was **told **July, **not **August, so that is how **he **knew.
We, on the other hand, had to be given that extra piece (that is was solvable by both boys) to determine the exact date.
And we were given that info when they both (somewhat smugly) said they did solve it.
It’s worth noting that these guys never do prove that they really do know the date.
I also don’t believe that you have logically excluded “True Neutral”, wherin they act for their own benefit (that is impressing Cheryl, maybe even getting to first base).
But by saying I he KNOWS that I don’t know, he is eliminating May from my list of possibilities. That’s fine, but now he knows I was told 14 or 16. The only way he can truthfully claim to KNOW I don’t know the birthday is if he KNOWS that I was told 14.
Where does he get off claiming to know my number? And if he DOESN’T claim to know that I don’t know the birthday, I’m still stuck wondering if her birthday is in May or July.
So the solution as written fails on the basis of the entirety of Albert’s initial assertion.
Piffle, if you’ll pardon the expression. If the birthday is June 17, Albert was told that the month was June. How, in your solution, did he rule out the possibility that Bernard was told the 18th?