20 people in a room. 40% chance two people share a birthday.

That's basically a graph connectedness question.

Basically, set up relationships between people as lines connecting them.

Do a cut that contains 3 people.
- all connected: they all know each other
- all unconnected: they don't know each other
- 2 connected, 1 isol: okay

So basically the question is, what's the largest number composed entirely of that third option. Plus 1.

3 people: possible. A knows B, neither know C.
Inductive: try to add a person so that none of the possible sets of 3 gain someone attached to the pair.
ie. 4th person must know C.
4 people: A knows B, C knows D.
Try again. How do we add a 5th person? If we add it to an existing group (knowing any of the 4) that forms 3 who know each other. If we add it outside, we get 3 who know nothing about anyone else in the group.

So... 5 people.

I'll just leave this here.

 spoiler...

The point is that you have to guarantee that there exists at least one group of 4 in which ONE person has to know (or not know) the rest. This can happen with 6, but not 5 (you can know 2 and don't know the other 2, but if you're given 5 people, you have to either know or not know 3).