OMB 2014 Finale MIDI Question 4 |
2788 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.
|
|
|
|
|