Dénombrement

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Dénombrement

par Sara1999 » 16 Aoû 2021, 11:15

Bonjour,
Je n’arrive pas à voir clairement comment procéder pour répondre à cette exercice, merci de m’aider;
Une grille carrée de 20 lignes et 20 colonnes est colorée de telle manière à ce que chaque ligne et chaque colonne est colorée par au plus 7 couleurs.
Quel est le maximum de couleurs qu’on peut utiliser pour colorier cette grille.



beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Dénombrement

par beagle » 16 Aoû 2021, 12:30

…………………………...
Modifié en dernier par beagle le 16 Aoû 2021, 14:45, modifié 3 fois.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 12:32

Je précise un peu, les cellules de chaque ligne et chaque colonne sont coloriés par au plus 7 couleurs.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Dénombrement

par beagle » 16 Aoû 2021, 12:33

………………………..
Modifié en dernier par beagle le 16 Aoû 2021, 14:45, modifié 1 fois.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 14 Juin 2019, 23:42

Re: Dénombrement

par lyceen95 » 16 Aoû 2021, 12:35

Je te rassure, l'exercice est compliqué. Et je n'ai pas la solution !
C'est plus une énigme, un exercice de recherche, qu'un exercice scolaire.
Déjà, on peut donner un encadrement.
La grille fait 20x20, donc on pourra au plus caser 20x20=400 couleurs :) Mais on voit vite que c'est beaucoup moins. On voit vite que au mieux, on pourra avoir 20x7=140 couleurs. Mais même ce nombre, ça paraît très optimiste.
On peut aussi donner assez facilement un minorant. Je te laisse donner un minorant évident.

Après, peut-être qu'en regardant comment ça marche avec des grilles plus petites (grilles 6x6, et maxi 3 couleurs par ligne ou par colonne) .. peut-être qu'on peut deviner la forme générale de la formule ?

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 13:26

Je suis parfaitement d’accord avec vous , c’est loin d’être évident . J’ai bien compris votre raisonnement, et je vous en remercie. Je continue sur ce que vous avez dit et je propose que 140 sera le nombre maximal .
Car si l’on compte la configuration où chaque ligne est coloriée de 7 couleurs différentes de la précédente, le nombre de façons pour colorier la grille de cette façon serait: C(7,n).C(7,n-7).C(7, n-14)……..C(7,n-133) ce qui impose que n-133>=7 donc n>=140
Donc n =140. Est ce que vous voyez que c’est correct ?

Skullkid
Habitué(e)
Messages: 3075
Enregistré le: 08 Aoû 2007, 19:08

Re: Dénombrement

par Skullkid » 16 Aoû 2021, 13:53

Bonjour, je n'ai pas non plus la solution, mais comme lyceen95 j'ai l'impression que 140 est un majorant impossible à atteindre. En tout cas je ne vois pas comment on pourrait colorier chaque ligne en utilisant 7 nouvelles couleurs : une fois arrivé à la 8ème ligne on ne pourra pas respecter la contrainte sur les colonnes.

Pour l'instant, sauf erreur de ma part, mes tentatives les plus fructueuses m'ont conduit à un coloriage avec 117 (edit : en fait 113, voir plus bas) couleurs, mais ce n'est peut-être pas le maximum.
Modifié en dernier par Skullkid le 16 Aoû 2021, 15:16, modifié 1 fois.

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 14:07

Oui, vous avez raison car je n’ai pas pensé à la contrainte des colonnes, pourriez-vous m’expliquer votre raisonnement pour arriver à 117

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 14 Juin 2019, 23:42

Re: Dénombrement

par lyceen95 » 16 Aoû 2021, 14:54

117 !
Intuitivement, j'aurais dit peut-être 60, je suis loin du compte.

On a un minorant facile : 49.
La bonne réponse est quelque part entre 49 et 140. C'est la seule chose dont je sois sûr pour l'instant.

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 15:03

Pourquoi 60?

Skullkid
Habitué(e)
Messages: 3075
Enregistré le: 08 Aoû 2007, 19:08

Re: Dénombrement

par Skullkid » 16 Aoû 2021, 15:15

Je vois déjà que je me suis trompé dans une simple addition, mon coloriage fait 113 couleurs et non 117, ça m'apprendra à taper des calculs simples avec mes doigts maladroits. En espérant qu'il n'y ait aucune autre erreur, on découpe 3 carrés 6x6 et 1 carré 2x2 sur la diagonale. On colorie temporairement ces 112 cases en noir, le reste de la grille en blanc.

Image

Dans cette configuration, une ligne/colonne contient au plus 6 cases noires, donc on peut recolorier les cases noires avec 112 nouvelles couleurs, ce qui donne un coloriage à 113 couleurs.

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 15:57

J’ai très bien compris le 113, reste à voir si c’est le maximum, un ami m’a dit qu’il serait peut-être intéressant d’utiliser la théorie des graphes, mais sincèrement je ne vous pas encore comment.
Grand Merci pour votre soutien. Cet exercice m’a beaucoup intrigué.

Skullkid
Habitué(e)
Messages: 3075
Enregistré le: 08 Aoû 2007, 19:08

Re: Dénombrement

par Skullkid » 16 Aoû 2021, 18:19

Une nouvelle tentative, à 121 couleurs cette fois (4 carrés 5x5 sur la diagonale + 4 morceaux de sous-diagonales de 5 cases chacun). On peut peut-être encore se rapprocher de 140 (voire l'atteindre ?)

Image

Si on admet que le problème qui consiste à colorier un maximum de cases en noir de sorte à ce que les lignes/colonnes contiennent au plus 6 cases noires est équivalent au problème de départ, alors cette configuration, qui a exactement 6 cases noires par ligne/colonne, a un goût d'optimalité. Bien sûr il faudrait le prouver proprement...

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 18:40

Pardon s’il vous plaît, mais si l’on divise la grille comme ce que vous avez fait au début en 2 carrés7x7 et un carré6x6 en diagonale, de telle sorte à ce qu’on utilise 7 couleurs différentes dans chaque ligne et dans chaque colonne des deux carrés 7x7 et 6 couleurs différentes pour chaque ligne et pour chaque colonne du carré 6x6, cela ne fera-t-il pas par hasard 134 couleurs ? Merci de me corriger.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 14 Juin 2019, 23:42

Re: Dénombrement

par lyceen95 » 16 Aoû 2021, 19:44

Si tu fais des carrés 7x7, il reste 13 cases à la fin des 7 premières lignes, il faut colorier ces 13 cases ... en reprenant une des couleurs déjà utilisées.

Edit : je disais 60 ... c'était un ordre de grandeur, j'aurais aussi bien pu dire 62 ou 65.

Sara1999
Membre Naturel
Messages: 95
Enregistré le: 02 Juil 2021, 14:02

Re: Dénombrement

par Sara1999 » 16 Aoû 2021, 20:16

Pardon, je retire ma remarque, j’ai eu soudainement une confusion , je crois que la dernière proposition de Skullkid est très raisonnable, encore faut-il la prouver . Je vous en remercie.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Dénombrement

par beagle » 17 Aoû 2021, 08:09

Bonjour à tous,
d'abord merci à sara1999 pour ce joli problème à la fois simple (7 couleurs ) et compliqué dans la résolution.
Ensuite bravo à Skullkid pour ses deux exemples à 121.

121 est bien le max.
Je vais mettre sur le site de Pierre ce matin ou ce midi, une possible voie de démonstration
puisque les ensembles permettent les équations et leur variation,
il me semble.
a+
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Vassillia

Re: Dénombrement

par Vassillia » 17 Aoû 2021, 09:00

Bonjour Sara1999,

Je me permets d'intervenir car je trouve le discours de Beagle inadmissible, il n'a pas à faire la promotion d'un site rempli d'inepsies auprès d'étudiants.

Je t'explique, le site de Pierre est un site où se réunissent les 2 ou 3 personnes bannies des forums car ils sont notoirement incompétents et insultants. Certains d'entre nous continuent de le lire pour l'amusement en tant que parodie. Si Beagle est en mesure de faire une démonstration, il pourrait la faire ici mais jusqu'à preuve du contraire, il n'en a pas. Comme tu peux le voir Beagle a la fâcheuse habitude d'effacer ses messages, cela te permet sûrement de comprendre pourquoi il se sent mieux sur un forum de bouffoneries que sur un forum sérieux. Les fois où il n'efface pas ses messages, cela donne ceci que tu te fasses une idée de son niveau enigmes/netflix-maths-saison-t231953.html

Ceci dit je le rejoins sur le fait que c'est un beau problème sur lequel Skullkid a fait un très joli travail. Je n'ai pas de démonstration et en écrire une proprement ne me paraît pas du tout évident mais bon courage et je lirai avec plaisir la suite.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Dénombrement

par beagle » 17 Aoû 2021, 09:38

Mauvais exemple s'il faut comparer les fils de discussion Netflix sur les deux sites:
celui de Pierre:
https://dlz9.forumactif.com/t913-netflix_maths-saison-2
celui de maths forum:
enigmes/netflix-maths-saison-t231953.html

pour moi le fil de discussion maths forum est un tissu de trollitude
le fil de discussion sur le site de Pierre est lisible car clairement développé.
Mais chacun peut en juger autrement.

Sur l'absence de démonstration de ce problème ci,
ceux que cela intéresse pourront juger.
J'ai dit je donne une façon de faire et il doit y en avoir mille autres, et je ne donne que les clés.
Donc oui cela n'est pas sur ce site justement à cause des agressions inutiles comme celle de Vassillia ce matin.
Si je mets sur le site de Pierre c'est que Dattier du site de Pierre est un sage et il m'a aidé à prendre cette décision (ne plus aller sur lesmathélatiques.net , et ne pas trop frotter sur maths forum)
J'ai adoré ce problème, je n'aurais pas du me connecter sur ce site sans doute, mais bon...
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Dénombrement

par beagle » 17 Aoû 2021, 11:58

L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : novicemaths et 42 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite