OMB - OMB 2014 Finale MIDI Question 4

OMB 2014 Finale MIDI Question 4

2788 vues | Retourner à la liste des questions

Dans une classe de $n$ élèves, l'amitié est symétrique : si $A$ est l'ami de $B$ , alors $B$ est l'ami de $A$ ; de plus, $A$ n'est pas considéré comme un ami de $A$ . Est-il toujours vrai que :

(a) Si $n\geq2$ , au moins deux élèves ont le même nombre d'amis ?

(b) Le nombre d'élèves ayant un nombre pair d'amis est impair ?

(c) Le nombre d'élèves ayant un nombre impair d'amis est pair ?

(d) Si chaque élève a au moins deux amis, alors il existe un élève $A$ qui est un ami d'un ami d'un ami... d'un ami de $A$ lui-même, les amis impliqués dans cette chaine en dehors de $A$ , tous distincts, étant au moins $2$ ?

(e) S'il y a strictement plus de $(n-1)(n-2)/2$ paires d'amis dans la classe, alors pour deux élèves $A$ et $B$ distincts quelconques, $A$ est un ami d'un ami d'un ami... d'un ami de $B$ , le nombre d'amis impliqués dans cette chaine en dehors de $A$ et de $B$ étant au moins $0$ ?

Solution(s) proposée(s) :

Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.

Anonyme	Posté le : 24/4/2014 18:07 Mis à jour : 24/4/2014
Je pense avoir bon au 2 dernières propositions mais les 3 premières j'ai utilisé un argument qui est en fait faux du coup j'ai faux T_T Le pire c'est que je m'en suis rendu compte au soir du coup j'étais frustré :/

Anonyme	Posté le : 21/5/2014 11:07 Mis à jour : 21/5/2014
Existe-t-il une solution officielle

Anonyme	Posté le : 25/12/2018 19:54 Mis à jour : 25/12/2018
a) Au pire des cas, chaque personne possede un nombre d ami different. Or il n existe que n possibilites (0,1,2,...,n-1). Comme il ne peut pas arriver que quelqu un ait 0 ami et un autre n-1 amis, vu que ca voudrait dire que la personne a n-1 amis est amie avec quelqu un qui n a pas d ami. En d autres termes, il reste moins de n possibilites pour n personnes, ce qui se traduit par le fait qu au moins 2 personnes ont le meme nombre d ami. :-D

Anonyme	Posté le : 25/12/2018 20:00 Mis à jour : 25/12/2018
b) un contre exemple flagrant: si il y a 4 personnes qui n ont chacune aucun ami, il est clair qu il y a un nombre pair de personne avec un nombre pair d ami (0 etant pair)

Anonyme	Posté le : 25/12/2018 20:04 Mis à jour : 25/12/2018
c) Vu que chaque lien d amitie augmente le nombre d ami de 2 personnes +1, on fait +2 au nombre d ami total (la somme du nombre d ami de chacun). Ce nombre total est donc pair. Or, si il y a un nombre impair de personne au nombre impair d ami, ce total serait impair, ce qui est impossible, donc la proposition est vraie

Anonyme	Posté le : 25/12/2018 20:13 Mis à jour : 25/12/2018
d) la classe pourrait tres bien etre divisee en plusieurs groupes sans lien d amitie entre 2 personnes de groupe different. En revanche au sein de chaque groupe, il n existe pas d eleve avec un seul ami (tout le monde en a au moins 2), il n y a donc pas de "bout" a ces groupes mais bien des cycles (on represente les eleves comme des points et les liens comme des segments entre ces points, on peut des lors se balader d eleve en eleve d un mm groupe sans faire demi tour). Il existe donc des cycle, le plus petit etant a 3 points, il suffit de prendre un point A d un tel cycle (3,4, ... points), et on se rend compte que la propriete est verifiee.

Anonyme	Posté le : 25/12/2018 20:49 Mis à jour : 25/12/2018
e) il existe au maximum (n(n-1))/2 liens pour n eleves. Or, cela voudrait dire que pour plus de ((n-1)(n-2))/2 liens, on a retire moins de n-1 liens. Or en partant du cas avec le max de liens, on ne sait pas isoler d eleves en enlevant moins de n-1 liens (car chaque eleve possede n-1 liens qui partent de lui). On se rend des lors compte qu il est possible d aller d un point A a un point B en suivant les liens sans aucun soucis.