Forum de mathématiques - Bibm@th.net

Mathadora

Invité

Dénombrement

Bonjour à tous,

En ce samedi froid et gris, je me suis décidé à faire un peu de dénombrement.

J'ai un exercice sur lequel je peine à trouver la solution :

Nous avons 6 enfants qui font face à un paquet contenant 13 bonbons tous différents.

Ils tirent simultanément les uns après les autres un nombre x de bonbons puis les remettent dans le paquet. Ils notent sur une feuille les bonbons tirés.

Combien de bonbons les enfants doivent tirer au minimum afin qu'ils aient tous au moins un bonbon identique ?

Quelqu'un pourrait m'aider ?

Merci d'avance pour vos retours.

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 220

Re : Dénombrement

Bonjour,
Il me semble que lorsque ce nombre de bonbons est compris entre 1 et 6, au moins 2 enfants peuvent avoir des bonbons tous différents...
Par conséquent ce nombre minimum de bonbons devrait être compris entre 7 et 13 inclus..

Dernière modification par Zebulor (23-11-2024 17:27:19)

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 862

Re : Dénombrement

Bonsoir à tous !

Je pense à l'événement contraire ...

"Au pire" si un enfants tire trize fois, il peut avoir 13 bonbons différents.

Donc il faut en tirer quatorze fois pour être sur d'avoir un bonbon tdentique ...

Et cela pour les six enfants ...

Bernard-maths

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Dénombrement

Combien de bonbons les enfants doivent tirer au minimum afin qu'ils aient tous au moins un bonbon identique ?

Bonsoir,

Moi je dirais treize. Chacun n'a qu'à prendre les treize et les remettre, comme ça ils ont la certitude d'avoir un bonbon identique, forcément.

Si un seul n'en prenait par exemple que douze, il risque de devoir multiplier les tirages avant de tomber sur le treizième commun aux cinq autres enfants, et dans ce cas-là il n'y a pas de minimum exact puisqu'il peut continuement jouer de malchance.

Pire, s'ils sont plusieurs à en tirer moins de treize, la probabilité d'avoir un bonbon identique commun diminue sérieusement, le pire étant quand chacun n'en tire qu'un seul et le remet...

(on notera qu'ici, le bonbon identique est entendu comme étant le même pour tout le monde)

Dernière modification par Ernst (23-11-2024 18:51:03)

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Dénombrement

Si maintenant on considère que le bonbon commun peut être différent avec chaque enfant, un tirage de sept devrait suffire : le cas le plus défavorable est, dès le deuxième enfant, de prendre les six bonbons non pris parmi les treize, mais même dans ce cas le septième sera forcément commun.

Glozi

Invité

Re : Dénombrement

Bonjour,
Je comprends la question comme :
- on numérote les enfants de $i=1$ à $i=6$
- L'enfant $i$ "choisi" un sous ensemble $E_i \subset \{1,2,\dots,13\}$ de cardinal $N$.
- On veut que quelque soient les choix des $E_i$ alors l'intersection des $E_i$ soit non vide ($\cap_{1\leq i \leq 6}E_i \neq \emptyset$). Cela signifie qu'il y a un bonbon qui est le même pour tous les enfants.

On visualise $13$ colonnes vides qui représentent les 13 bonbons. On met une pierre dans chaque colonne pour chaque enfant dont le bonbon correspondant à la colonne fait partie de sa sélection (ie la colonne $j$ contient $\text{Card}(\{i\ |\ j\in E_i\})$ pierres). Alors les enfants ont un bonbon commun si l'une des colonnes contient 6 pierres. Si toutes les colonnes contiennent moins de 5 pierres c'est qu'il y a au total moins de $13\times 5$ pierres. Or le nombre de puces est de $6\times N$. Donc dès que $6\times N> 13\times 5$ c'est qu'il y a forcément un bonbon en commun. Puisque $N$ est entier, ça donne $N\geq 11$.
Pour $N=10$ on vérifie aisément qu'il est possible qu'il n'y ait aucun bonbon partagé par tous les enfants.

Autre manière de voir le problème, notons $R=13-N$, le nombre de bonbons que les enfants laissent dans le sachet, alors si $F_i$ représente l'ensemble des bonbons laissés dans le sachet par l'enfant $i$, on peut dire qu'il y a un bonbon commun partagé par tous les enfant si $\text{Card}\left(\bigcup_{1\leq i  \leq 6} F_i \right) \leq 12$ (le bonbon qui n'est pas dans l'union a été choisi par tous les enfants). Or, on peut majorer ce cardinal par $6R$ on veut donc $6R\leq12$ donc $R\leq 2$ donc $N\geq 11$.

Bonne soirée

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Dénombrement

Bonjour Glozi, bonjour tout le monde,

Alors là, chapeau ! Je me suis amusé à > programmer la chose <, avec dix millions de tirages on n'obtient effectivement dix millions de succès qu'à partir de x=11.

Donc bravo, vraiment, j'aurais été bien incapable de trouver ce résultat !

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Dénombrement

Bonsoir,

Aïe. J’ai voulu lancer un grand nombre de simulations et faire autre chose en attendant, quand je suis revenu le calcul a repris à l’endroit où je l’avais laissé, pas top.

J’ai donc modifié le code javascript pour que le calcul puisse maintenant se faire en tâche de fond, et également bénéficier du parallélisme. J’ai un i7, en mono avec N=11 je calcule un million de tirages en 4.65 secondes, en multi-threading je tombe à 0.52 s.

Tout ça dans un navigateur, c’est quand même pas mal je trouve...

Glozi

Invité

Re : Dénombrement

Bonsoir,
Je vois que tu as un joli site Ernst ! C'est chouette d'avoir des simulations (en plus elles sont rapides) pour observer un résultat surtout si celui ci surprend ! (après rien ne vaut une démo !)
Bonne soirée

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Dénombrement

Bonjour Glozi,

Le site, c’est parce qu’à chaque fois que je fais une simu, je filais le code et un site pour pouvoir l’exécuter, mais pour des codes un peu sérieux c’était trop lourd. J’ai donc créé ce site pour y mettre les programmes. Borassus a parlé un jour de javascript, j’ai découvert sa puissance, c’est hallucinant, plus besoin d’.exe, même pas besoin de fichier .js, tout encapsulé en .html à la portée de n’importe quel navigateur, trop bien.

Pour les formules, quand j’ai lu ton post déjà je n’ai pas compris grand-chose, tu tombais deux fois sur N ≥ 11, j’ai voulu vérifier, c’était ça ! Alors là, total respect, et je ne me suis pas senti fier des bêtises que j’ai pu écrire il faut bien le dire.

Enfin j’ai cherché une explication « logique » à ce onze tout droit sorti d’un chapeau, un peu à la façon des pseudo-experts toujours prêts à expliquer de façon rationnelle tout événement imprévisible une fois qu’il a eu lieu. En fait si chaque enfant laisse deux bonbons, les bonbons non pris auront beau être tous différents, cela ne fera jamais que douze, et comme il y en a treize, c’est donc que forcément il y a un bonbon qui a été pris par tout le monde.

(ce que tu exprimes dans ton autre manière de voir le problème avec les formules qui vont bien, je pense)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Dénombrement

Pour $N=10$ on vérifie aisément qu'il est possible qu'il n'y ait aucun bonbon partagé par tous les enfants.

Bonjour,
Juste pour indiquer une manière de faire qui, je pense, éclaire un peu le problème.
Numérotons les bonbons de 0 à 12.
Le premier enfant prend les bonbons 0 à 9
Le deuxième les bonbons 10 à 19 (modulo 13)
...
Le sixième les bonbons 50 à 59 (modulo 13)
59 = 4 x 13 + 7
Les bonbons 0 à 7 ont été pris 5 fois, ceux de 8 à 12 ont été pris 4 fois.