- Partage ce devoir avec tes amis !
Sujet du devoir
Soit n un entier supérieur ou égal à 2. Prouver que dans une réunion de n personnes, il existe toujours deux personnes telles que, parmi les n-2 autres participants, il y ait au moins la partie entière de (n/2)-1 qui connaissent les deux personnes à la fois ou leur sont complètement étrangères.
Issu des olympiades des États-unis de 1985.
Je sèche sur ce problème depuis plusieurs mois, j'espère que l'un de ceux qui me liront trouveront la solution…
Où j'en suis dans mon devoir
Nulle part, je n'ai mené que des hypothèses n'aboutissant à rien, il en est de même pour toutes mes connaissances (élèves comme prof).
6 commentaires pour ce devoir
Bonjour,
En prend un tiroir pour chaque paire d'invités {B,C}, on a donc (2 parmi n) = n(n-1)/2 tiroirs.
Pour chaque {A,B,C}, on place A dans le tiroir si A connais les deux ou aucun.
Si A connais k personnes, il y a k(n-1-k) couples où elle connais une personne et pas l'autre et donc (2 parmi (n-1)) - k(n-1-k) couples où elle connais soit les deux soit aucune.
On a k(n-1-k) >= ((n-1)/2)² et (2 parmi (n-1))-((n-1)/2)² = (n-1)(n-3)/4
On a donc (au moins) n(n-1)(n-3)/4 objets à répartir dans n(n-1)/2 tiroirs.
D'après le principe des tiroirs, au moins un contient [ (n(n-1)(n-3)/4)/(n(n-1)/2)] = [n/2] - 1.
Merci beaucoup pour cette réponse ! ! j'avais en réalité peu d'espoir que quelqu'un réussisse à corriger ce que ma prof ne résolvait pas.
! ! Pour ceux qui auront besoin de la correction de cet exo,
Il me semble qu'il y a une petite faute dans par réponse apportée par LG124:
k(n-1-k)<=((n-1)/2)^2
et non >=
exact!
merci pour la correction.
Ils ont besoin d'aide !
- Aucun devoir trouvé, poste ton devoir maintenant.
Bonjour. Il y a n personnes, k personnes se connaissent donc n-k ne se connaissent pas, fais un tableau de variations des deux "fonctions" et compare-les, tu pourras ainsi faire ta conclusion.
Bonjour,
Je ne vois pas comment tomber sur une partie entière après…