Je ne pense pas qu'il soit bien dur de trouver une solution, mais je veux bien voir vos raisonnements, voire vos preuves si vous en trouvez.

Dans une assemblée de N personnes, on sait que chaque personne en connaît p autres. Combien peut-on rassembler de personnes qui ne se connaissent pas du tout ?

EDIT 5 juillet, 17h35 :

Je précise, pour Clydevil notamment, que :
- "se connaître" est supposé être une relation symétrique (mais la symétrie n'est probablement pas indispensable pour trouver le plus grand nombre d'inconnus que l'on peut rassembler... pour la question subsidiaire, probablement).
- quand je dis "chaque personne en connaît p autres", ça veut dire qu'elle en connaît effectivement p autres, ni plus ni moins (ça a l'air bête, mais bon...)

Et, euh, ah oui ! la question subsidiaire (soufflée par Frank) :

Dans le "pire des cas" (à savoir les liens d'amitié qui "nous arrangent le moins", combien de personnes peut-on rassembler qui ne se connaissent pas ?

La réponse 0 est refusée d'office, ne serait-ce que parce qu'en isolant une personne, on obtient un sous-ensemble de la population de départ dans lequel on ne peut pas trouver deux personnes qui se connaissent. Donc 1 est un minorant de la réponse attendue

Je précise aussi, suite à une remarque de Clydevil (encore lui), que n'importe quelle couple (N,p) ne peut pas être possible, ce qui m'amène à une deuxième question subsidiaire :

Comment caractériser les couples (N,p) tels qu'il est possible que chacune des N personnes en connaisse exactement p autres, sachant que la relation "se connaître" est symétrique ("si je connais quelqu'un, il me connait, et vice-versa") ?

Je n'ai pas encore vraiment réfléchi à ces deux questions. A vue d'œil, je tenterais d'utiliser de la théorie des graphes pour la première, et de la combinatoire pour la deuxième, mais je ne peux pas dire que je suis sûr de moi...