On the 16th of July.
These exercises develop attention to details.
They only look hard, but are really very easy to solve.
The most important here is to analyse all the facts given.
All that John knows is the month. For every month he has different date,
and therefore he cannot know when Sam was actually born.
On the other hand, Paul could know the date only if Sam has told him 18th or 19th, as these are the only dates that do not repeat.
If John knows that Paul also doesn't have the correct date, that means 18th and 19th are not the correct dates,
which in its turn means that May and June are not the correct months.
Thus the correct month would be either July or August.
And that means that John already understands that Paul was told either July or August.
This means that John knows the number that Sam told him and knows that it is either July or August.
This also means that John was given 15th, 16th or 17th. Because if he was given 14th, than he wouldn't know if it was July or August, as 14th was given for the both remaining months.
Therefore Paul dismissed all the other dates and came to conclusion that the only correct dates would be 16th July, 15th August or 17th August.
And because he knows the correct month and can see all these dates, he concluded that Sam was born in July. And the only remaining date for July is the 16th.