Salut,
J'imagine que:
-c'est "exactement" p autre.
-connaitre quelqu'un est ici une relation symetrique. (tu dis "se connaitre" donc ca semble naturel)
Si oui c'est rigolo mais je n'avais jamais remarqué que parfois ce n'était pas possible. (ie s'il y a 3 personnes elles ne peuvent pas chacune en connaitre exactement une)

Je suppose que si A connait B, B connait A.
De plus le nombre maximum dépend de la relation de connaissance elle-même et que donc on cherche justement l'organisation du groupe qui permet d'obtenir le plus grand nombre.

Dans ce cas, je pense que le maximum est atteint lorsque l'organisation est la suivante:
Je fais des groupes de p personnes.
Je regroupe ces groupes par paire. Chaque personne du premier groupe connait chaque personne du deuxième groupe de la paire.
Chacun connait bien p personnes (dans l'autre groupe) mais ne connait personne de son groupe. Ces p personnes ne se connaissent pas entre elles ni ne connaissent quelqu'un d'un groupe d'une autre paire.
On peut donc choisir un groupe de p personnes par paire.

Donc si N=2kp, on peut avec cette disposition choisir kp (N/2) personnes qui ne se connaissent pas.
Il reste le cas du reste de la division de N par 2p à traiter.
Je vais essayer d'y réfléchir plus.
(Il doit y avoir un rapport avec les graphes bipartites bicolores mais je ne vois pas trop quel résultat utiliser)...

En plus du "UP", je rajoute quelques remarques qui introduisent deux questions subsidiaires. Je vais ajouter 24 heures et me casser la tête avec vous

Petites réflexions sur le sujet (je chercherai plus en détail ce soir)

Si N et p sont impairs, alors un tel groupe ne peut pas exister.
En effet, on représente tout ça par un graphe; le nombre d'arêtes est N.p/2 (chaque personne en connait p, donc N.p; mais chaque relation étant réciproque elle est comptée deux fois)

Pour la suite je parle à chaque fois du cas optimal
Pour p=0 la réponse est N
Pour p=1 la réponse est N/2 (pour N pair)
Pour p=2 la réponse est E(N/2). Dans un cas non optimal on peut descendre jusqu'à N/3 dans les cas où N est un multiple de 3
Pour p=Pi > Pj la réponse optimale est nécessairement inférieure ou égale à celle de Pj (puisque sinon, en enlevant des arêtes de la solution Pi on ne crée pas de nouvelle connaissances donc la réponse serait alors applicable à Pj aussi)

Lorsque l'on constitue le groupe des personnes qui ne se connaissent pas, la première personne que l'on met dedans élimine forcément p personnes. La deuxième personne en élimine d'autre uniquement si elle connait d'autres personnes que la première.
Pour constituer le plus gros groupe de personnes qui ne se connaissent pas, l'idéal est de constituer des paires de groupes de p personnes où chaque personne de premier groupe de la paire connait chaque personne du 2eme groupe de la paire.



Comme nous avons n*p/2 couples de relation, nous savons qu'il y a un entier pair parmi n et p.
Montrons que cette condition est suffisante tout en construisant un gros groupe de personnes qui ne se connaissent pas.

Essayons de faire des paires de groupes de p personnes n = 2p*q+r,  0<= r <2p
Si r = 0.
Pour chaque paire de groupe de p personnes nous établissons les relations de manière optimale comme dit plus haut et nous pouvons prendre 1 groupe de chaque paire pour le groupe final. Soit le maximum possible : n/2.
Si 0< r < p.
Nous faisons q-1 paires de groupe de p personnes de manière optimale. Il nous reste 2 groupes de p personnes (P1, P2) et un groupe de r personnes (R1).
Chaque personne de R1 fait connaissance avec chaque personne de P1.
Toutes les personnes de R1 connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P1 connaissent r personnes et ne se connaissent pas entre elles.
Chaque personne de P1 fait connaissance avec p-r personnes de P2 de la manière suivante :
La première personne de P1 fait connaissance avec la première personne de P2 et les p-r-1 suivantes.
La deuxième personne de P1 fait connaissance avec la 2eme personne de P2 et les p-r-1 suivantes.
La dernière personne de P1 fait connaissance avec la dernière personne de P2 et les p-r-1 premières.
Toutes les personnes de P1 connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P2 connaissent p-r personnes.
Il nous reste a ajouter r relations aux p personnes de P2. On le fait récursivement car si p est impair, alors r est pair.
De plus on peut rajouter toutes les personnes de P1 dans l'ensemble final dont la taille sera q * p soit strictement entre n/3 (si q ->0) et n/2 (si q grand)
Si r = p
p est forcément pair.
Nous faisons q-1 paires de groupes de p personnes de manière optimale. Il nous reste 3 groupes de p personnes (P1, P2, P3).
On présente la première moitié de P1 a chaque personne de P2 et la deuxième moitié de P1 a chaque personne de P3.
Toutes les personnes de P1 connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P2 et P3 connaissent p/2 personnes et ne se connaissent pas entre elles.
Il reste a attribuer P/2 relations a un groupe de 2p personnes qui se résout récursivement de manière optimale.
On constitue encore un groupe de n/2
Sinon p < r < 2p
Nous faisons q paires de groupes de p personnes de manière optimale. Il nous reste 1 groupe de p personnes P1 et un groupe de r-p personnes R1.
Chaque personne de R1 fait connaissance avec chaque personne de P1.
Toutes les personnes de R1  connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P1 connaissent r-p personnes et ne se connaissent pas entre elles.
Il reste a attribuer 2p-r relations a un groupe de p personnes qui se résout récursivement car si p est impair, alors r est pair et 2p-r aussi.
Au final nous constituons un groupe de (q*p + r-p) personnes