omb
Menu principal
Sujets d'articles
OMB 2014 Finale MIDI Question 4 Informations | BxMO 2017 | SBPM  
OMB 2014 Finale MIDI Question 4
1867 vues  | Retourner à la liste des questions

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

(a) Si , 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 qui est un ami d'un ami d'un ami... d'un ami de lui-même, les amis impliqués dans cette chaine en dehors de , tous distincts, étant au moins ?

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



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.
Membres
Prénom :

Nom :

Mot de passe : 

Conserver la connexion

Récupérer mot de passe
Recherche
Le site officiel de l'Olympiade Mathématique Belge
Contact webmasters :