Logique

[anthony_06]

Bonsoir,

Voici un problème que j'ai dû résoudre il y a quelques années et dont je ne suis pas certain de la réponse.

Adeline dit à Bill :
« Ce sac contient 123 billes de couleurs différentes. Si tu tires
au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes, mais ce n’est pas sûr si tu en
tires seulement 99 ».
Combien Bill doit-il tirer de billes au hasard, au minimum,
pour être certain d’avoir des billes d’au moins 3
couleurs différentes ?

Je suis intéressé de découvrir vos réponses.

Merci
-----

[Lechero]

Bonsoir !

67 ?

[Xoxopixo]

J'ai failli répondre comme Lechero.
Apres reflexion, je dirais 99.

Il y a 33 billes de la même couleur x 3, soit 99
Les 24 restantes sont d'un couleur quelconque autre que celle des 3 groupes de 33.
Ce qui permet d'affirmer qu'en prennant 99+1, il est certain d'avoir 4 couleurs.

D'apres cette affirmation

tu peux être certain d’avoir 4 billes de couleurs différentes, mais ce n’est pas sûr si tu en tires seulement 99

Si il suffisait de prendre 1 bille pour passer de 4 couleurs non certaines à 4 couleurs certaines.
Ceci veut dire qu'on avait à ce point déja 3 couleurs certaines en ayant prélevé 99 billes.

Donc on doit prélever 99 billes pour être certain d'avoir 3 couleurs.

[Lechero]

J'ai failli répondre comme Lechero.
Apres reflexion, je dirais 99.

Ça veut dire que je n'ai pas réfléchi ? Effectivement !

[A voir en vidéo sur Futura]

[anthony_06]

Si il suffisait de prendre 1 bille pour passer de 4 couleurs non certaines à 4 couleurs certaines.
Ceci veut dire qu'on avait à ce point déja 3 couleurs certaines en ayant prélevé 99 billes.

Donc on doit prélever 99 billes pour être certain d'avoir 3 couleurs.

Il est clair qu'avec 99 billes on est sûr et certain d'avoir trois couleurs. Mais ici, on veut le nombre de billes minimum que Bill doit tirer pour avoir 3 couleurs. Le résultat sera alors certainement inférieur à 99.

[KeM]

Il y a 33 billes de la même couleur x 3, soit 99

C'est faux. Prenons par exemple un sac étant constitué de 97 billes de couleur rouge et le reste de 26 billes de couleurs différentes (donc 1 bille bleu, 1 bille noir, 1 bille rose, etc ...)
Ce sac vérifie toutes les hypothèses posées et est donc succeptible d'être le sac en question mais tu peux constater qu'il n'y a pas 33 billes de la même couleur.

[shokin]

« Ce sac contient 123 billes de couleurs différentes. Si tu tires
au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes, mais ce n’est pas sûr si tu en
tires seulement 99 ».

La question intermédiaire non énoncée est : combien y a-t-il de couleurs ?

Avec cette information, on sait que :

- en tirant 100 billes, tu es sûr d'avoir (au moins ou exactement ? [à préciser éventuellement]) quatre couleurs différentes,
- en tirant 99 billets, il est possible d'avoir seulement trois couleurs.

Cela signifie qu'il existe au moins un groupe de trois couleurs tel que la somme des billes dans une de ces trois couleurs égale 99 exactement. [On sous-entend l'hypothèse que chaque bille n'a qu'une couleur.]

Cela a pour conséquence, comme il y a 123 billes, que les autres billes sont d'une couleur autre que les trois couleurs. Appelons P, Q et R les ensembles des trois couleurs initiales. 123-99 = 24. Il y a donc 24 billes qui n'appartiennent ni à P, ni à Q, ni à R.

Voyons donc maintenant les ensembles P, Q, R (dont la somme des cardinaux égale 99). Rien n'implique a priori que leurs trois cardinaux (le cardinal d'un ensemble fini est son nombre d'éléments) sont égaux. Cela dit, aucun des cardinaux de P, de Q ou de R ne peut être nul, sinon la couleur n'existerait pas (dans le cas de cet exercice).

Si les écarts entre les cardinaux sont minimaux, les cardinaux de P, de Q et de R seront égaux dans le cas où leur somme est un multiple de 3, ce qui est le cas. Card(P)=Card(Q)=Card(R)=33 = 99/3. Si c'était le cas, pour être sûr d'avoir au moins trois couleurs différentes, il faudrait prendre la somme des deux cardinaux les plus grands et lui ajouter un. Dans ce cas, ce serait 33 + 33 + 1 = 67. On voit que, ce sont les plus grands cardinaux qui sont importants.

Voyons maintenant, si les écarts sont au maximum, histoire de maximiser les cardinaux des deux couleurs dont sont colorées le plus de billes. Comme le minimum de chaque cardinal de couleur existante est 1, parmi P et Q et R, il faudrait que l'un vaille 97 et les deux autres 1. Il y aurait par exemple 97 billes de la couleur P, 1 bille de la couleur Q et 1 bille de la couleur R. Les deux plus grands cardinaux seraient alors 97 et 24 (les 24 billes restantes ; où on admet le cas où elles sont toutes de la même couleur). Il faudrait alors 97+24+1 =122 billes pour être sûrs qu'elles soient de la même couleur.

On voit alors qu'on aurait pu raisonner autrement :

On sait qu'il y a au moins 4 couleurs. En revanche, on ne connaît pas la répartition de ces billes au total. L'idée reste toujours de maximiser la somme des deux plus grands cardinaux (des deux couleurs dont le plus de billes sont colorées). Comme une couleur existante a au moins 1 bille, si l'on cherche à maximiser cette somme des deux plus grands cardinaux, il faut minimiser le nombre de couleurs, soit 4 exactement.

Il faut donc que deux couleurs maximisent et deux couleurs minimisent. Les deux petits cardinaux seront 1 et 1. Leur somme 2. Reste 121 billes réparties dans les deux cardinaux les plus grands. Reste à ajouter une bille pour être sûr de sortir une nouvelle couleur. Donc il faut 122 boules.

Remarque : le raisonnement est valable quel que soit le nombre entier non nul de boules d'une couleur autre que P, Q ou R.

Autre manière de raisonner pour ce problème : comme on ne connaît pas la répartition de ces quatre couleurs (on prend le minimum de couleurs pour maximiser la somme des deux plus grands cardinaux non nuls), il suffit de considérer que trois cardinaux valent 1, et que le dernier cardinal prenne les boules restantes, soit 123-1-1-1 =120 boules.

Remarque : on voit alors que, comme l'on n'a aucune information précise sur la répartition des couleurs, la réponse à la question du problème était indépendante de l'information citée tout en haut. (information qui ne nous indique pas assez sur la répartition des boules de couleurs P, Q et R, et rien du tout sur la répartition des autres couleurs)



Shokin

[KeM]

Notations
Soit le nombre de billes d'une couleur que l'on nommera .
Il y a couleurs d'après l'énoncé. (on peut prendre un sac où il y a seulement 4 couleurs, ou un sac où il y a 102 couleurs etc...)


Définition de l'ensemble des sacs
Soit l'ensemble des sacs vérifiants les propositions suivantes :

"Ce sac contient 123 billes de couleurs différentes."

"Si tu tiresau hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes" pour tout distincts dans

"mais ce n’est pas sûr si tu entires seulement 99" il existe distincts dans tels que


Exemples
Rappelons que nous cherchons le minimum de billes à tirer pour être sûr de chopper 3 billes de couleurs différentes : cela revient à chercher : pour tout

Rien de mieux maintenant que quelques exemples :
Soit le sac suivant :
On a 5 couleurs différentes réparties comme il suit : et .
Leur somme est égale à , quelque soit choisies on aura toujours une somme inférieur ou égale à 100, et enfin il existe tels que la somme soit égale à 100. On a montré que .
Il est évident que


Soit le sac suivant :
On a 27 couleurs différentes réparties comme il suit : et
De même que précedemment on montre facilement que .
Ensuite il vient que

Conclusion
"Combien Bill doit-il tirer de billes au hasard, au minimum,
pour être certain d’avoir des billes d’au moins 3
couleurs différentes ?"

Ceci équivaut à dire quel est le minimum de n'importe quel élement de . Or comme on l'a vu par deux exemples qui n'étaient que des éléments de cela varie selon différents paramètres on peut très bien avoir pour le même énoncé un minimum de 75 comme un minimum de 99. Ainsi ton énoncé est incomplet ou ta question pas assez précise (il faudrait donner des paramètres comme et ) CQFD

[anthony_06]

Malheureusement, ta démonstration, KeM, est fausse car ton équation est mal posée. En effet, ce n'est pas la somme des billes de 4 couleurs qui est égal à 100, mais la somme des billes de 3 couleurs + 1. En équation, ça donne :
ou .

En conséquence, tu remarqueras que ton premier exemple est faux. Le deuxième, lui, avec de la chance donne une réponse juste, malgré un développement faux.

C'est dommage car ton raisonnement est juste et montre bien les limites du problème, que je n'ai pas inventé, mais qui figurait dans un concours international de mathématiques pour des jeunes de 14-15 ans, auquel j'avais participé.

La réponse officiel était alors 67, ce qui faux.

En outre, même si l'énoncé du problème semble incomplète, on pourrait quand même essayer de le résoudre en se mettant à la place de Bill, qui, ne sachant ni le nombre de couleurs, ni le nombre de billes par couleur mais ayant l'information mentionnée dans le problème (100 : sûr d'avoir 4 couleurs, 99 : pas sûr), doit chercher le nombre minimum de billes qu'il doit tirer pour être sûr et certain d'avoir 3 billes de couleurs différentes. La réponse serait alors 99.

[KeM]

Malheureusement, ta démonstration, KeM, est fausse car ton équation est mal posée. En effet, ce n'est pas la somme des billes de 4 couleurs qui est égal à 100, mais la somme des billes de 3 couleurs + 1. En équation, ça donne :
ou .

En conséquence, tu remarqueras que ton premier exemple est faux. Le deuxième, lui, avec de la chance donne une réponse juste, malgré un développement faux.

C'est dommage car ton raisonnement est juste et montre bien les limites du problème, que je n'ai pas inventé, mais qui figurait dans un concours international de mathématiques pour des jeunes de 14-15 ans, auquel j'avais participé.

La réponse officiel était alors 67, ce qui faux.

En outre, même si l'énoncé du problème semble incomplète, on pourrait quand même essayer de le résoudre en se mettant à la place de Bill, qui, ne sachant ni le nombre de couleurs, ni le nombre de billes par couleur mais ayant l'information mentionnée dans le problème (100 : sûr d'avoir 4 couleurs, 99 : pas sûr), doit chercher le nombre minimum de billes qu'il doit tirer pour être sûr et certain d'avoir 3 billes de couleurs différentes. La réponse serait alors 99.

Salut, j'ai bien foiré en effet

Je corrige donc la 4ème proposition de l'ensemble : "mais ce n’est pas sûr si tu entires seulement 99" .
Après tout roule enfaite, on montre par un encadrement qu'il existe et que c'est le majorant de l'ensemble de tous les triplets de couleurs et donc le minimum sera toujours de 99 billes. L'enoncé est même trop complet non ? car avec un nombre de billes supérieur ou égal à 100 ca marche tout le temps.

[shokin]

Autre manière de raisonner pour ce problème : comme on ne connaît pas la répartition de ces quatre couleurs (on prend le minimum de couleurs pour maximiser la somme des deux plus grands cardinaux non nuls), il suffit de considérer que trois cardinaux valent 1, et que le dernier cardinal prenne les boules restantes, soit 123-1-1-1 =120 boules.

J'ai oublié de terminer :

Le plus grand cardinal vaut 120 (il y a 120 boules d'une même couleur). Comme l'on veut trois couleurs, il faut ajouter deux couleurs, dont deux boules restantes. 120 + 2 = 122.

La réponse serait alors 99.

Contre-exemples :

A) Imagine un sac avec :

97 boules rouges
1 boule verte
1 boule bleue
24 boules blanches

Si tu veux au moins au trois couleurs, tu dois considérer les deux plus grands cardinaux (97 et 24), les additionner puis ajouter 1, ce qui fait 97+24+1 = 122.

C'est le contre-exemple "extrême", celui où la somme des deux plus grands cardinaux est la plus grande. C'est donc celui-ci qu'il faut considérer, étant donné que nous n'avons pas plus d'informations.

B) Maintenant, s'il y a :

90 boules rouges
6 boules vertes
3 boules bleues
24 boules blanches

Avec le même procédé, 90+24+1 = 115 boules à tirer au minimum pour avoir au moins trois couleurs. Mais ce n'est pas la situation extrême.

C) Dernier exemple :

31 boules rouges
31 boules vertes
31 boules bleus
30 boules blanches

Les deux cardinaux les plus grands ont pour somme 31 + 31 = 62. Il faut donc 63 boules. C'est le nombre minimal de boules qu'il faut au minimum pour obtenir trois couleurs.

Mais ce dernier exemple ne respecte pas la donnée suivante :

Si tu tires au hasard 100 billes de ce sac, tu peux être certain d’avoir 4 billes de couleurs différentes, mais ce n’est pas sûr si tu en tires seulement 99

Celle-ci s'avère en fait inutile, dans ton problème, car pas assez précise. La réponse eût été la même sans cette "contrainte".



En gros, si tu à n billes de diverses couleurs sans que tu aies d'informations sur leur répartition ni sur le nombre de couleurs, il peut y avoir de 1 à n couleurs.

Si on te demande alors combien tu dois tirer de billes pour avoir au moins m couleurs, on doit supposer deux cas :

- celui où c'est impossible : si m>2, mais toutes les billes sont de la même couleur,
- celui où c'est possible : il existe au moins un groupe de m billes de couleurs différentes entre elles.

Dans ce dernier cas, nous devons considérer le cas extrême où les n-m autres billes sont de la même couleur qu'une des m billes initiales.

Il y a donc n-m+1 billes d'une même couleur P.
Et donc m-1 billes uniques en leurs couleurs (donc m-1 couleurs différentes de la couleur P).

Comme on veut m couleurs différentes, il faut déjà prendre toutes les boules de la couleur P.
Une fois celles-ci prises, nous avons n-m+1 billes et 1 couleur.

Mais comme nous voulons m couleurs, il nous faut encore m-1 couleurs, donc toutes les billes restantes. Donc il faut n billes (toutes les billes) pour être sûr d'avoir m couleurs, ce qui est logique.

Alors pourquoi est-ce différent du problème initial du premier message où je trouve 122 et non 123 selon mon raisonnement de ce message ?

« Ce sac contient 123 billes de couleurs différentes. Si tu tires
au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes, mais ce n’est pas sûr si tu en
tires seulement 99 ».
Combien Bill doit-il tirer de billes au hasard, au minimum,
pour être certain d’avoir des billes d’au moins 3
couleurs différentes ?

La différence est que l'on sait qu'il y au moins 4 couleurs dans ce problème (et pas seulement au moins 1 couleur). Or ce nombre est plus grand que le nombre de couleurs demandées.

Généralisons alors le problème :

J'ai n billes. Je sais qu'il y a au moins p couleurs. Et je veux au moins m couleurs. Je connais donc les nombres naturels non nuls m, n et p.

Si p est plus petit ou égal à m, m me suffit (on suppose que c'est possible). Et l'on arrive à la solution décrite juste avant, soit n.

Si p est strictement plus grand que m, reprenons depuis le début :

Il existe au moins un ensemble de p boules de p couleurs différentes. Les n-p boules restantes seront d'une couleur commune à l'une des p boules initiales. Appelons cette couleur P.

Il y a donc n-p+1 boules de la couleur P.
Et p-1 boules chacune unique en sa couleur et différente de P.

Je veux au moins m couleurs :

Je dois déjà tirer toutes les billes de couleur P.
ça me fait n-p+1 boules et 1 couleur.

Il me manque alors m-1 couleurs :

Je tire alors m-1 boules (heureusement m<p) de m-1 couleurs.
ça me fait (n-p+1)+(m-1) boules et m couleurs.
ça me fait (n-p+m) boules et m couleurs.

Dans le problème initial :

n = 123
m = 3
p = 4

n-p+m = 123 - 4 + 3 = 122.



Shokin

[shokin]

Après tout roule enfaite, on montre par un encadrement qu'il existe et que c'est le majorant de l'ensemble de tous les triplets de couleurs et donc le minimum sera toujours de 99 billes. L'enoncé est même trop complet non ? car avec un nombre de billes supérieur ou égal à 100 ca marche tout le temps.

Non, 99 est le nombre maximum de billes que tu peux tirer en ayant une chance de ne pas avoir plus de trois couleurs. En tirer 99 n'exclut pas qu'elles seront d'au moins 4 couleurs différentes.

Si tu n'as aucune information précise sur la répartition des couleurs parmi les boules, les informations pertinentes sont :

(1) le nombre de boules au total (que j'ai appelé n),
(2) le nombre de couleurs qu'il y a (que j'ai appelé p),
(3) le nombre de couleurs que tu veux (que j'ai appelé m).

99 ou 100 était une information inutile car pas assez précise et pas accompagnée d'autres informations assez précises.



Shokin

[KeM]

Contre-exemples :

A) Imagine un sac avec :

97 boules rouges
1 boule verte
1 boule bleue
24 boules blanches

Ouai mais si on tire 100 billes on est pas sur à 100% d'avoir 4 couleurs : imagine que tu tire 97 boules rouges et 3 boules blanches donc ce sac ne vérifie pas les hypothèses de départ.

[Xoxopixo]

Remarque : on voit alors que, comme l'on n'a aucune information précise sur la répartition des couleurs, la réponse à la question du problème était indépendante de l'information citée tout en haut. (information qui ne nous indique pas assez sur la répartition des boules de couleurs P, Q et R, et rien du tout sur la répartition des autres couleurs)

Tout à fait, c'est ce que je me suis dit apres coup aussi.
La répartition en nombre de couleurs importe peu.

Le fait essentiel est comme déja énnoncé :

Si tu tires au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes, mais ce n’est pas sûr si tu en
tires seulement 99 ».

C'est l'énoncé, il est censé être vrai, quel quel soit le nombre de couleurs, quel que soit les parametres.
On peut considerer tout ceci comme etant mysterieux et le mettre de coté.

Je maintient donc que, si l'enoncé est vrai : On passe à 4 couleurs differentes certaines en ajoutant 1 seule bille (on a alors 100 billes), c'est qu'on avait au moins 3 couleurs differentes certaines lorsqu'on avait 99 billes.

Sinon c'est illogique.

Si on n'est pas certain d'avoir 3 billes de couleurs differentes en en ayant pris 99, comment peut-on être certain d'avoir 4 couleurs differentes en ajoutant 1 seule bille ?
Ce serait impossible.

[KeM]

Non, 99 est le nombre maximum de billes que tu peux tirer en ayant une chance de ne pas avoir plus de trois couleurs. En tirer 99 n'exclut pas qu'elles seront d'au moins 4 couleurs différentes

Je ne sais pas si j'ai bien compris ce que tu voulais dire mais j'ai bien mis "il existe" ce qui signifie que ce triplet de couleur est le cas particulier qui fait que ce n'est pas sur.
Par exemple en tirant 99 billes on a plein de cas possibles avec plus de 4 couleurs (comme tu le précise) mais il existe au moins un cas de 3 couleurs (pas moins car sinon l'hypothèse 4 couleurs tirés sûr avec 100 billes ne serait plus vérifiée) qui fait l'incertitude de tirer 4+ couleurs avec 99 billes.

[shokin]

Ouai mais si on tire 100 billes on est pas sur à 100% d'avoir 4 couleurs : imagine que tu tire 97 boules rouges et 3 boules blanches donc ce sac ne vérifie pas les hypothèses de départ.

Oups ! je n'ai pas pensé à cela. Il faut que je corrige. Tu peux mettre de côté tout ce que j'ai écrit précédemment alors.

« Ce sac contient 123 billes de couleurs différentes. Si tu tires
au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes, mais ce n’est pas sûr si tu en
tires seulement 99 ».

Si je tire 100 billes parmi 123, je suis sûr d'avoir au moins un groupe de 4 billes de 4 couleurs.

Si je tire 99 billes, il est possible que je n'y arrive pas, que je n'aie que trois couleurs.

Ah ! oui ! je crois voir où je me suis trompé.

Si je tire 100 billes et suis sûr alors d'avoir 4 couleurs, c'est que j'ai réussi à éliminer les trois plus grands cardinaux + une boule d'une autre couleur quelconque.

Donc, dans le problème, les trois plus grands cardinaux ont pour somme 100-1 = 99.

Comme dans le problème, il y a 24 (123-99) autres boules, il faut que chacun des trois cardinaux soit plus plus grand ou égal à 24, car il faut considérer le cas extrême où ces 24 autres boules sont d'une seule et même couleur.

Pour la répartition de ces trois cardinaux les plus grands, on a donc le cas équilibré : 33+33+33. Dans ce cas, pour tirer trois boules de couleurs différentes, il faudrait 33+33+1=67 boules.
Si l'on prend le cas - extrême - où l'on maximise l'un de ces trois cardinaux, mais qui doivent être supérieurs ou égaux à 24, on a 24+24+51. Alors il faut 51+24+1 boules, donc 76 boules ! Augmenter l'un de ces 24 ne changerait rien puisque ça diminuerait d'autant le 51.

J'ai bon ?



Shokin

[Xoxopixo]

Si je tire 99 billes, il est possible que je n'y arrive pas, que je n'aie que trois couleurs.

A partir de là, on peut remonter dans l'autre sens et en déduire le principe de la répartition.

Ce dont on est sur :
En prennant 99 billes, on est sur d'avoir 3 couleurs differentes.
+
On prend une 100eme bille et on est sur d'avoir 4 couleurs.

=> les 123-99=24 billes sont d'une couleur autre (que les 99)
Ce point est nécessaire pour rendre l'assertion initiale toujours vraie.

On a donc:
3 Couleurs se répartissent parmi 99.
Ceci ne dit rien sur la répartition des 3 couleurs parmi 99, mais ce n'est pas la question posée.

Exemple:
Admettons que les 3 couleurs sont bleu, blanc, rouge (cocorico )
on peut avoir 97 billes bleues, 1 bille blanche, 1 bille rouge, par exemple.

Oui, mais on peut se dire, si on prend 97 billes, il se peut que toutes ne soient pas bleues.(on peut remplacer bleu par blanc, par rouge, c'est sans importance)

C'est exact.
Donc pour que l'assertion initiale reste vraie, à tous les coups, les 24 billes restantes doivent toutes être de couleur differente.

Deux cas extremes possibles :
* Si on pioche uniquement parmi les 24, on a les 4 billes de couleur differentes en 4 tirage...

* Si on ne pioche jamais (cas inverse) parmi les 24, (c'est un cas extreme), on aura pris toutes les billes (99) bleues+blanc+rouge, soit 3 couleurs de manièere certaine.
La 100eme sera une 4eme couleur à coup sur.

Les cas intermediaires donnent le même résultat.

Je pense que pour comprendre, il faut distinguer les deux groupes.
Le groupe des 3 couleurs.
Les groupe des 24 couleurs.

[anthony_06]

Xoxopixo et Shokin donnent chacun une réponse différente. Pourtant, aucune des deux n'est selon moi fausse. En effet, ces différentes réponses sont dues à la manière dont on comprend la question, plus précisément, le passage

Si tu tires au hasard 100 billes de ce sac, tu peux être certain d’avoir 4 billes de couleurs différentes.

Il y a deux manières d'interpréter "4 billes de couleurs différentes".

La première est de penser qu'en tirant 100 billes du sac, on aura des billes d'au moins 4 couleurs. Il se peut alors qu'il y ait plus que 4 couleurs. C'est le raisonnement de Xoxopixo avec ses 97 billes de la même couleur et ses 26 autres billes qui ont toutes une couleurs différentes.

La deuxième est de penser qu'en tirant 100 billes du sac, on aura toujours le même nombre de couleurs différentes : 4. Et non pas 4, 5, 6,7...27, comme dans le raisonnement de Xoxopixo. Ceci est donc le raisonnement de Shokin avec 3x24 billes chacunes d'une certaine couleur et 51 billes d'une quatrième couleur.

On remarque alors que cette différence de compréhension de l'énoncé provoque des réponses complétement différentes : 99 pour Xoxopixo et 76 pour Shokin. Après, il appartient à chacun d'interpréter cette énoncé imprécis à sa façon.

[Tryss]

J'ai bon ?

Non, un sac contenant 97 billes d'une couleur et 26 autres billes de couleurs distinctes deux à deux respecte l'énoncé et nécessite 99 tirages pour être sur d'avoir 3 billes de couleur distinctes

Ton raisonnement n'est valable que si il n'y a que 4 couleurs.

[shokin]

Non, un sac contenant 97 billes d'une couleur et 26 autres billes de couleurs distinctes deux à deux respecte l'énoncé et nécessite 99 tirages pour être sur d'avoir 3 billes de couleur distinctes

Ton raisonnement n'est valable que si il n'y a que 4 couleurs.

Justement, il y a au moins quatre couleurs parmi les 123 billes, c'est indiqué dans la donnée du problème.

Si tu tires au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes,

Par contre, si on ne savait pas du tout le nombre de couleurs, mon premier long message aurait presque été bon (presque mais toujours pas juste).

Il y a deux manières d'interpréter "4 billes de couleurs différentes".

La première est de penser qu'en tirant 100 billes du sac, on aura des billes d'au moins 4 couleurs. Il se peut alors qu'il y ait plus que 4 couleurs. C'est le raisonnement de Xoxopixo avec ses 97 billes de la même couleur et ses 26 autres billes qui ont toutes une couleurs différentes.

La deuxième est de penser qu'en tirant 100 billes du sac, on aura toujours le même nombre de couleurs différentes : 4. Et non pas 4, 5, 6,7...27, comme dans le raisonnement de Xoxopixo. Ceci est donc le raisonnement de Shokin avec 3x24 billes chacunes d'une certaine couleur et 51 billes d'une quatrième couleur.

Voici mon avis à ce sujet :

A priori, quand on lit le problème, on se dit bien qu'il y a au moins quatre couleurs.

Mais quand on lit :

« Ce sac contient 123 billes de couleurs différentes. Si tu tires
au hasard 100 billes de ce sac, tu peux être certain d’avoir
4 billes de couleurs différentes, mais ce n’est pas sûr si tu en
tires seulement 99 ».

Cela signifie qu'avec 99 billes, il est possible de n'avoir que trois couleurs. Admettons un tel cas : si je tire, ensuite, une 100ème bille, il ne pourra y avoir que 3+1 couleurs, étant donné que j'ai tiré une seule bille après avoir récolté les 99 billes des trois couleurs initiales.

Bien sûr, on peut toujours imaginer qu'il y ait plus de 4 couleurs, c'est possible (par exemple, que la 101ème bille sera d'une cinquième couleur). Mais comme on n'en est pas sûr, nous devons imaginer tous les cas. Or, si le nombre total de billes ne change pas, pour maximiser la somme de t cardinaux, nous devons réduire le nombre de couleurs, et le minimum, c'est 4.



Shokin

[Tryss]

Bien sûr, on peut toujours imaginer qu'il y ait plus de 4 couleurs, c'est possible (par exemple, que la 101ème bille sera d'une cinquième couleur). Mais comme on n'en est pas sûr, nous devons imaginer tous les cas. Or, si le nombre total de billes ne change pas, pour maximiser la somme de t cardinaux, nous devons réduire le nombre de couleurs, et le minimum, c'est 4.

Sauf qu'on ne sait pas le nombre de couleurs.

On demande le nombre minimal de billes que l'on devra tirer pour être sur que l'on ai 3 billes de couleurs différentes.

Si il n'y a que 4 couleurs, tu as raison, 76 billes suffisent.

Problème, si il y a plus de 4 couleurs et une configuration défavorable, 76 billes ne suffisent plus! Au contraire, plus il y a de couleurs et plus il faut de billes, ainsi au lieu de minimiser le nombre de couleurs, il aurait fallu que tu le maximise!


D’ailleurs on a un contre-exemple : 97 billes d'une couleur et 26 autres 2 à 2 distinctes est une configuration qui respecte les conditions du problème, pourtant 76 billes ne suffisent pas pour obtenir a coup sur 3 billes de couleur distinctes

[shokin]

Sauf qu'on ne sait pas le nombre de couleurs.

On demande le nombre minimal de billes que l'on devra tirer pour être sur que l'on ai 3 billes de couleurs différentes.

Si il n'y a que 4 couleurs, tu as raison, 76 billes suffisent.

Problème, si il y a plus de 4 couleurs et une configuration défavorable, 76 billes ne suffisent plus! Au contraire, plus il y a de couleurs et plus il faut de billes, ainsi au lieu de minimiser le nombre de couleurs, il aurait fallu que tu le maximise!

Là, je ne suis pas d'accord. Plus il y a de couleurs, moins il y aura de billes par couleur en moyenne.

Essaie avec un 123 billes d'au moins cinq couleurs.

D’ailleurs on a un contre-exemple : 97 billes d'une couleur et 26 autres 2 à 2 distinctes est une configuration qui respecte les conditions du problème, pourtant 76 billes ne suffisent pas pour obtenir a coup sur 3 billes de couleur distinctes

Je ne suis pas d'accord.

Tu veux dire par exemple : 97 billes rouges, 2 billes bleues, 2 billes vertes, ... ?

100 billes alors ne suffisent pas pour obtenir 4 couleurs : je prends 97 billes rouges, 2 billes bleues et 1 bille verte...

Mais il est vrai que j'ai oublié de regarder les cas où il y aurait beaucoup de couleurs parmi les 24 restantes... je vais revoir ça.

Bigre ! (ça se voit que je n'aurais pas dû arrêter le concours organisé de la FFJM, j'ai perdu la main...)



Shokin

[Tryss]

Je ne suis pas d'accord.

Tu veux dire par exemple : 97 billes rouges, 2 billes bleues, 2 billes vertes, ... ?

100 billes alors ne suffisent pas pour obtenir 4 couleurs : je prends 97 billes rouges, 2 billes bleues et 1 bille verte...

Mais il est vrai que j'ai oublié de regarder les cas où il y aurait beaucoup de couleurs parmi les 24 restantes... je vais revoir ça.

Bigre ! (ça se voit que je n'aurais pas dû arrêter le concours organisé de la FFJM, j'ai perdu la main...)



Shokin

Non, je n'ai pas dit ça

Rappel :
"Deux à deux distinctes" ça veut dire que si on en prend 2, elles seront de couleurs distinctes (je pensais que c'était du vocabulaire classique mathématique)

Donc a part les 97 billes d'une couleur, chaque bille est unique

Avec cette configuration, 99 billes est le nombre minimum pour être sur d'en avoir 3 différentes, et 100 billes est le nombre minimum pour être sur d'en avoir 4 différentes

Au passage, avec exactement 5 couleurs différentes, il faut au moins 87 billes pour en avoir 3 différentes avec cette configuration :
- 73 rouges
- 13 bleues
- 13 vertes
- 12 jaunes
- 12 noires

73+13+13 = 99
73+13 = 86

[shokin]

Okay, pour ton dernier message, Tryss.



Je reprends :

Soit Ai l'ensemble de billes d'une même couleur.
Soit C(Ai) le cardinal de l'ensemble Ai.

Soient A1, A2 et A3 les trois plus grands ensembles, les trois couleurs les plus représentées en quantité parmi les 123 billes.

C(A1)+C(A2)+C(A3)=99 (ça, j'en suis sûr)

Pour tout Ai non élément de {A1;A2;A3} et pour tout Aj élément de {A1;A2;A3}, alors Ai<=Aj. Cela si signifie que pour les 24 autres billes :

- aucune de ces 24 billes n'est de couleur A1, A2 ou A3,
- tout ensemble de billes de même couleur parmi ces 24 billes est a un cardinal plus petit ou égal à chaque cardinal parmi A1, A2 et A3.

Par conséquent, plus le cardinal le plus petit parmi C(A1), C(A2) et C(A3) [qui restent les plus grands] est petit, plus le nombre de billes d'une quatrième couleur quelconque aura un maximum petit. Appelons ce maximum M (qui sera égal au cardinal le plus petit parmi C(A1), C(A2) et C(A3).

Cherchons le M maximum, c'est 99/3 = 33. Comme 33>24, le cardinal de toute couleur des 24 billes restantes sera toujours plus petit que le M théoriquement atteignable. Et, quelle que soit la répartition des couleurs parmi ces 24 billes, le nombre minimal de billes pour avoir trois couleurs différentes sera 33+33+1 = 67. Cela vaut pour tout m entier dans l'intervalle [24;33]. Exemple :

Si les trois plus grands cardinaux valent 32, 33 et 34, alors 32 est le plus petit 32 = M, la somme des deux plus grands vaut 67. Il faut donc 68 billes. Donc si M est dans [24;33], le nombre de billes nécessaires est 99-M+1 = 100-M.

Que se passe-t-il quand M descend à 23 ? Étant donné que parmi les 24 boules, il ne peut y avoir aucun groupe de billes strictement plus grand que 23 (nous avons défini C(A1), C(A2) et C(A3) comme les trois plus grands cardinaux). Il y a forcément au moins deux couleurs parmi ces 24 billes. Quant aux trois plus grands cardinaux, l'un vaudra 23 et la somme des deux autres (chacun plus grand ou égal à 23) sera 76 . Peu importe leur répartition, la somme des deux plus grands cardinaux sera 76. Il faudra donc 77 billes.

Quand M = 13, la somme des deux plus grands cardinaux sera 86, il faudra alors 87 billes pour avoir au moins trois couleurs.
Et on peut descendre ainsi au moins jusqu'à ce que M=12, où il faudra alors 88 billes.

A partir de 11, la formule 100-M ne change toujours pas. C'est seulement le nombre de couleurs minimal parmi les 24 qui augmente au fur et à mesure que M diminue (que M passe sous chaque diviseur de 24).

Jusqu'à ce qu'on arrive à ton cas : 97 billes d'une même couleur et 26 billes de 26 autres couleurs.

Alors les deux plus grands cardinaux sont 97 ; 1. M = 1, donc il faut tirer 100-M=100-1=99 billes pour être sûr de tirer au moins trois couleurs.



Shokin