Forum de mathématiques - Bibm@th.net

elmaths

Membre

Inscription : 04-12-2019

Messages : 25

Joli problème.

Bonjour mes amis.
J'ai bloqué sur le problème suivant :

Il y a 20 élèves dans une classe d'école secondaire et chaque élève a exactement trois amis intimes dans la classe.
Cinq des élèves ont acheté des billets pour une concert à venir.
Si un élève voit que deux ou plusieurs de ses trois amis intimes ont acheté des billets, il en achètera un aussi.
Est-il possible que tous les élèves de la classe achètent des billets pour le concert?
On suppose que l'amitié est mutuelle, si l'élève A est un ami intime de l'élève B, alors B est un ami intime de A

Moi, j'ai trouvé 15 élèves (achètent des billets)

Dernière modification par elmaths (01-03-2024 17:38:02)

Eust_4che

Membre

Inscription : 09-12-2021

Messages : 152

Re : Joli problème.

Bonjour à tous les deux,

Je me demande le contexte de l'exercice. Avec les hypothèses faîtes, il ne me parait pas de stratégies "immédiate" pour un être résoluble pour un collégien ou un lycéen. On a très peu d'informations. Pour s'en sortir, il faudrait au moins connaître le nombre de personnes dont l'élève $A$ est l'ami intime, et non le nombre d'élèves avec qui $A$ est intime. La relation "$A$ est intime avec $B$" est-elle supposée impliquer la relation "$B$ est intime avec $A$" ?

Là, par exemple, je vois pas comment démontrer que les cinq élèves ayant acheté leur ticket ont pu en influencer 15.

E.

Dernière modification par Eust_4che (01-03-2024 16:17:54)

elmaths

Membre

Inscription : 04-12-2019

Messages : 25

Re : Joli problème.

Les premiers cinq  élèves qui achèteront des billets seront choisis au hasard. 
Les autres achèteront le billet si leurs amis intimes (deux ou plus) achètent des billets.

Avec la condition :
[tex]
A ~intime ~de~ B~ \Leftrightarrow~
B~ intime ~de ~A
[/tex]

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 618

Re : Joli problème.

Bonsoir,

Je répondrai qu'il n'est pas possible que tous les élèves de la classe achètent des billets.

Mais je ne suis pas certain.

En tout cas, j'ai l'impression qu'il n'y a pas beaucoup de configurations où chaque élève a exactement trois amis intimes. La seule configuration que j'entrevois est celle formée par 5 groupes de 4 élèves (disons A, B, C et D) avec les relations d'amitiés entre
A-B
A-C
B-C
B-D
C-D
Ainsi, B et C ont leurs 3 amis parmi ce groupe alors que A et D n'en ont que deux. Leurs derniers amis feront partie d'un autre groupe, par exemple en mettant les groupes de façon cyclique :
...-(A_0,B_0,C_0,D_0)-(A_1,B_1,C_1,D_1)-...

Si on veut que 5 billets permettent que tout le monde en achète ensuite (avec la règle énoncée), il faudrait a minima qu'une personne par groupe ait initialement un billet, mais ce n'est pas suffisant !

Roro.

Dernière modification par Roro (01-03-2024 21:09:39)

Glozi

Invité

Re : Joli problème.

Bonsoir,
Imaginons qu'on représente les 20 élèves comme 20 pions, chacun ayant trois bras. En reliant les bras des pions avec des bouts de ficelle on voit apparaître la structure d'amitié de la classe, deux pions sont reliés par un fil si et seulement si ils représentent deux élèves qui sont intimes.

Maintenant, pour ton problème, on part d'un échiquier avec juste 5 pions dessus qui ont chacun les trois bras libres (aucune ficelle pour le moment), ces pions sur l'échiquier représentent les élèves qui initialement ont acheté les billets pour le concert.

On peut rajouter de la ficelle et/ou des pions sur l'échiquier de l'une des deux manière suivante :
Option 1 : on déclare que deux des pions sur l'échiquier (qui ont chacun encore au moins un bras libre) sont amis intimes et on met juste un bout de ficelle entre ces deux pions.
Option 2 : on déclare que deux des pions sur l'échiquier ont un ami intime commun qui n'est pas encore sur l'échiquier. On rajoute alors un nouveau pion sur l'échiquier relié par deux ficelles à ces deux pions qui l'ont influencé.

A la fin, l'échiquier contiendra exactement tous les pions qui vont au cinéma.

Il y a deux quantités qui nous intéressent : la quantité $A$ qui représente le nombre total de pions sur l'échiquier, la quantité $B$ qui représente le nombre total de bras libres des pions sur l'échiquier.

Initialement, on a donc $A=5$ et $B=3\times 5=15$.

Si on fait l'option 1, alors $A$ ne change pas, mais $B$ diminue de $2$.
Si on fait l'option 2, alors $A$ augmente de $1$, mais $B$ diminue de $1$ ($B$ diminue de $2$ mais augmente de $1$ grace au nouveau pion).

Notons qu'il est impossible de faire l'option 2 si la valeur de $B$ actuelle est inférieur ou égale à $1$.

Ainsi, dans le meilleur des cas on ne fait que l'option 2, $B$ diminue de $1$, $14$ fois jusqu'à valoir $1$, mais alors $A$ à augmenté de $14$ et vaut $19$.

Bilan : à la fin il y aura au plus $19$ pions sur l'échiquier et il est donc impossible que cinq élèves influencent toute la classe.

PS : ce raisonnement ne prouve pas qu'il est possible pour 5 élèves d'influencer 19 autres !
PPS : caché derrière il y a la théorie des graphes (les pions sont les sommets, les bouts de ficelle sont les arêtes), si bridgslam passe par là il pourra certainement nous en dire plus.

Bonne soirée

elmaths

Membre

Inscription : 04-12-2019

Messages : 25

Re : Joli problème.

Bonsoir,
Par exemple :

Les amis intimes d'élève (01) sont :   2    3    4
Les amis intimes d'élève (02) sont :   1    5    6
Les amis intimes d'élève (03) sont :   1    7    8
Les amis intimes d'élève (04) sont :   1    9    10
Les amis intimes d'élève (05) sont :   2    11    12
Les amis intimes d'élève (06) sont :      2    13    14
Les amis intimes d'élève (07) sont :      3    15    16
Les amis intimes d'élève (08) sont :      3    17    18
Les amis intimes d'élève (09) sont :      4    19    20
Les amis intimes d'élève (10) sont :      4    11    12
Les amis intimes d'élève (11) sont :      5    10    13
Les amis intimes d'élève (12) sont :      5    10    14
Les amis intimes d'élève (13) sont :      6    11    15
Les amis intimes d'élève (14) sont :      6    12    16
Les amis intimes d'élève (15) sont :      7    13    17
Les amis intimes d'élève (16) sont :      7    14    18
Les amis intimes d'élève (17) sont :      8    15    19
Les amis intimes d'élève (18) sont :      8    16    20
Les amis intimes d'élève (19) sont :      9    17    20
Les amis intimes d'élève (20) sont :      9    18    19

Si les élèves (1, 5, 10, 15, 20) achèteront les billets
Alors les élèves (2, 4, 11, 12) achèteront aussi car leurs intimes ont acheté des billets.

Alors les élèves (9, 13) achèteront aussi
Alors les élèves (6, 19) achèteront aussi
Alors les élèves (14, 17) achèteront aussi

Dernière modification par elmaths (02-03-2024 21:16:01)

Ernst

Membre

Inscription : 30-01-2024

Messages : 126

Re : Joli problème.

Amis des case-têtes, bonsoir.

Perso j'arrive à 17 billets de la façon suivante :

Vingt élèves, chacun a trois amis. En rouge les cinq billets d'origine. En orange les élèves qui voient deux de leurs amis avec des billets. De proche en proche, les jaunes en achètent, puis les verts, et enfin les bleus.

Borassus

Membre

Lieu : Boulogne-Billancourt

Inscription : 07-02-2023

Messages : 728

Re : Joli problème.

Bonsoir,

Glozi a montré que le maximum de billets achetés est 19.

Peut-on déterminer le minimum de billets achetés ?

---

A condition qu'elle soit gênante, l'incompréhension est la clé de la compréhension.
« Pourquoi ? » est sans doute le principal moteur de la connaissance.
L'exigence précède l'expérience.

Glozi

Invité

Re : Joli problème.

Bonsoir,
Non le maximum n'est pas 19. J'avais précisé en PS que mon argument ne montrait pas que le maximum était 19 mais qu'il était plus petit que 19 (donc en particulier pas égal à 20). Cependant, en travaillant un peu plus mon argument on peut montrer qu'on ne peut pas faire mieux que 17, or Ernst a produit une solution avec 17, le maximum est donc 17.
Pour le minimum, il est de 5 billets achetés (les cinq qui ont des billets au début). Il suffit de faire en sorte que quatre d'entre eux forment une clique (les trois amis de chacun de ces quatre sont les trois autres), cette clique n'influence personne et donc le cinquième ne pourra influencer personne a lui tout seul.

▼pourquoi pas plus de 17 ?

Imaginons qu'on a une configuration qui fait 19 personnes qui achètent les billets, en suivant mon argument on se rend compte qu'on met alors 19 pions sur l'échiquier, tous sauf un ont leurs trois bras occupés, le dernier n'ayant plus qu'un bras. Mais alors le 20 pion doit être connecté à trois autres pions ce qui est impossible.
De même, imaginons qu'on ait une configuration qui fait 18 personnes qui achètent les billets, à la fin sur l'échiquier on aura 18 pions, avec moins de deux bras libres. Il est alors impossible de rajouter les 19ème et 20ème pions et de mettre de la ficelle sur leurs bras sans "double connexion".

Bonne soirée

Ernst

Membre

Inscription : 30-01-2024

Messages : 126

Re : Joli problème.

Bonsoir tout le monde.

Merci à Glozi d'avoir montré que vingt était exclu, j'en aurais été bien incapable.

Partant de là, le maximum est bien dix-sept grâce au raisonnement suivant : s'il est impossible que tous les élèves aient un billet, c'est donc qu'il y a au moins un élève qui n'a pas de billet. Et si cet élève n'a pas de billet, c'est donc qu'il n'a pas trouvé, parmi ses trois contacts, au moins deux possesseurs de billets, sinon il en aurait acheté. Il y a donc deux élèves sans billet en plus de lui-même, ce qui fait bien un minimum de trois élèves sans billet, forcément.

Glozi

Invité

Re : Joli problème.

Très joli !
C'est bien plus direct que ce que j'avais en tête pour montrer que le max est plus petit que 17 :-)