Un dénombrement un peu compliqué

[johnlanders]

Bonjour à tous

Je recherche un peu d'aide dans un petit exercice de dénombrement un petit peu complexe. Il serait assez facile de le faire résoudre à un ordinateur qui pourrais tester tout les cas rapidement mais n’ayant que de faible capacité de programmation et devant le manque d'élégance de cette méthode, je préférerai ne pas y avoir recours, je n'ai pas fait de maths depuis très longtemps et j'ai l'esprit un peu émoussé et j'espère que vous pourrez m'aider.

Voici l'énoncé :

Soit une grille de 9 cases (3 par 3), dont la case centrale est grisée (impossible d'y déposer un jeton) de telle sorte que seule les huit cases périphériques puissent recevoir un jeton. Les cases de cette grille sont orientées est sont donc considérés comme non équivalentes.
Sur chaque case on va déposer un jeton de tels sortes que chaque ligne et chaque colonne soit occupé par au moins 1 jetons. On déposera 5 jetons, et il est possible d'en empiler plusieurs sur une case.
Combien trouve on de configuration non équivalente ?

Pour bien illustrer l'orientation des cases, un exemple de deux configurations non équivalente du fait de l'orientation :

Cas 1-2.jpg

Ici on voit que le cas 1' est obtenu par rotation du cas 1, cependant comme les cases sont orientées il s'agit bien de deux configurations différentes

J'ai essayer de procéder avec un arbre mais on arrive à des configurations identiques par des voies différents comme dans l'exemple ci-dessous :

Cas 3-4.jpg

Ici le O représente le cinquième jeton on remarque que les deux configurations sont identiques au final mais que les configurations dont elle sont issues sont différentes. Ainsi s'il l'on procède avec un arbre on fini par obtenir pas mal de configurations identiques qui ne doivent pas entrer dans le compte final.

Voici, j'espère avoir été assez clair dans mes explications et j'attends vos réponses avec impatience.

Merci d'avance.
-----

[ansset]

bjr,
je propose le graphe suivant : en comptant par nb de cases occupées au total.
- pour 3 cases occupées les 3 premiers jetons n'ont que 4 poss de position ( dont un angle )
reste 2 jetons à poser sur ces même 3 cases :
2 sur la même case : 3 sol
2 sur 2 cases diff : 3 sol.
au total dans cette configuration 24 sol
- pour 4 cases occupées , 5 cas de figures :
---pas d'angle occupé : 1 solution , reste à placer 1 jeton sur une des 4 cases : 4 sol
---un angle seul occupé : j'obtiens 8 solutions sans doublons à multiplier par 4 pour le 5 ème jeton : 32 sol
---2 angles occupés : 8 solutions aussi sans doublon tj à multiplier par 4 : 32 sol
---3 angles occupés : pas de sol ( il manquera tj une ligne ou colonne )
---4 angles occupés : 1 sol tj à multiplier par 4 : 4 sol
-pour 5 cases occupées : pas de choix compliqué C(8;5)=56 sol
au total
24+(4+32+32+4)+56=152.

à vérifier bien sur...

[ansset]

une première erreur, j'ai trop de solutions avec 5 jetons séparés car certaines ne couvrent pas toutes les lignes et colonnes.....
il faut donc déduire ces cas de répartition "non valables".
pas difficile il y en a 4, si je compte bien. ( une ligne ou une colonne manquante )

[ansset]

Donc au final 148.
mais il faut que je vérifie mes multiples de 8.
si qcq confirme ou infirme, ce serait avec plaisir.
même s'il le fait par ordi.
Cdt

[A voir en vidéo sur Futura]

[bdom001]

Ici le O représente le cinquième jeton on remarque que les deux configurations sont identiques au final mais que les configurations dont elle sont issues sont différentes. Ainsi s'il l'on procède avec un arbre on fini par obtenir pas mal de configurations identiques qui ne doivent pas entrer dans le compte final.

Voici, j'espère avoir été assez clair dans mes explications et j'attends vos réponses avec impatience.

Bonjour,

ben en fait non, ce n'est pas très clair. Si deux configurations sont supposées identiques, il est certains quelles n'augmenteront pas le nombre total de configurations. On comprend d'emblée que la pose des jetons n'est pas ordonnée (jetons interchangeables).

Comme vous êtes impatient je vous donne le résultat de mon calcul (d'après ce que j'ai compris):



J'hésite un peu à l'expliciter car je ne suis pas encore arrivé au point de le formaliser de manière rigoureuse et générale. Je dirais simplement que je m'intéresse aux configurations des cases laissées vides

Cdlt

[ansset]

@bdom001:
ce que veux dire john c'est qu'en posant les jetons les uns après les autres , on peut se retrouver avec la même configuration finale qu'en les posant dans un autre ordre.
ce qui fait qu'on obtient beaucoup de combinaisons redondantes.
et j'ai l'impression que tu procèdes ainsi.

[ansset]

après relecture, et visionnage de sa seconde image, je ne sais plus ce qu'il entend par identique ou différente.
car dans mon calcul elle sont différentes.

[johnlanders]

Alors pour éclaircir le identique et différent. Deux positions sont considérés comme identique, lorsque que le dessin formé par les jetons est le même à la fin, les jetons ne sont pas considérés comme différents les uns des autres, le schéma sert juste à montré que deux voies de placements différents, en peuvent conduire à un schéma final qui est le même.

Imagine un automate cellulaire par exemple, ou chaque jeton décris une direction et un nombre de case dans laquelle notre cellule pourrait se déplacer, et bien les cas 3 et 4 décriraient le même mouvement pour cette automate, cependant l'ordre de placement des jetons serait différents. La notion d'ordre de placement, sert juste à débuter le dénombrement, mais seul le résultat final permet de différencier des configurations. Est-ce plus clair ?

[johnlanders]

Ou pour faire encore plus simple comme analogie :

Si tu prends un sac avec 4 boules, 2 blanches et 2 noirs. Tu as deux manières d'envisager le tirage et de dire combien de configurations tu as après avoir tiré deux boules :

Premier choix tu tiens compte de l'ordre du tirage : Ce qui donne quatre possibilités différentes :

- Blanc 1 Blanc 2
- Noir 1 Noir 2
- Blanc 1 Noir 2
- Noir 1 Blanc 2

Deuxième choix tu ne tiens pas pas compte de l'ordre du tirage : Ce qui réduit à trois configurations :

- Deux Blanches
- Deux Noires
- Un Blanche et une Noire

Dans le cas qui m’intéresse pour le dénombrement, on ne regarde que le nombre de configurations différentes obtenues sans tenir compte du chemin qui les as créer, on se situe plus face à la deuxième approche donc.

[ansset]

soyons plus clair,
les cas 1 et 2 comptent ils pour 1 ou 2 solutions ? et pourquoi
les cas 3 et 4 comptent ils pour 1 ou 2 solutions ? et pourquoi.
quand on fait une rotation de 90° qui abouti à une "image" différente, est ce 1 ou 2 solutions ?
idem pour un renversement gauche/droite ?

pour le reste , j'ai bien compris que si on place les jetons les uns derrières les autres on peut retrouver à la fin la même "image".
donc , dans ces cas , il faut supprimer les doublons.

pour ma part, ce que j'ai calculé , c'est le nb "d'images différentes" à la fin. ( sans les doublons crées par un ordre différent de placement des jetons )

[johnlanders]

Deux configurations sont considérés comme différentes si elles ne sont pas superposable strictement.

Ainsi le cas 1 et le cas 2 sont différents, ils ne sont pas superposable et compte donc comme deux configurations différentes. Certes le cas 2 est issu d'une symétrie du cas 1, mais on arrive à deux configurations non superposables après transformation.

Le cas 3 et le 4 sont deux configurations qui sont superposables, par conséquent, ils ne compte que pour une seule et unique configuration.

Par conséquent quand tu fais une rotation de 90°, si le résultat n'est pas superposable à celui avant la rotation alors tu as bien trouvé une nouvelle configuration.

Si tu fais une symétrie, tu obtiens donc l'image miroir, si cette image miroir n'est pas superposable, (si elle est chirale, je suis plus chimiste que mathématicien et c'est selon moi la meilleur propriété pour décrire le cas), alors tu as deux configurations différentes.

Donc voilà, le plus simple c'est de dire que les configurations qui ne sont pas superposable sont différentes.

Et attention il faut tenir compte de la hauteur des piles de jetons également.

Par exemple si tu prends la configuration où tu empiles deux jetons au coin supérieur droit, deux jetons sur le bord latéral gauche, et un seul jetons sur le bord inférieur.

-|-|2
2|X|-
-|1|-

(on pourrait schématiser ainsi avec un trait représentant une case vide et un chiffre le nombre de jetons sur la case et le X une case ne pouvant recevoir de jeton)

Et la configuration un jeton sur le coin supérieur droit, un jeton sur le bord latéral gauche, et trois jetons sur le bord inférieur

-|-|1
1|X|-
-|3|-

Alors on voit bien qu'il y a deux configurations différentes car non superposable, la présence au sol est la même, mais la hauteur des piles de jetons varie.

[ansset]

Le cas 3 et le 4 sont deux configurations qui sont superposables, par conséquent, ils ne compte que pour une seule et unique configuration.
.

comment ça ?
ou alors je n'ai pas compris le sens du O !!!!
si ton O est le 5ème jeton, alors je comprend et c'est dans le sens de ma résolution.
donc , je confirme mon chiffre et ma démonstration : 148 ....
je peux la ré expliquer si elle n'est pas claire pour toi.

[ansset]

je veux dire que j'ai essayé de compter le nb de figures différentes à la fin, tout simplement.
en tenant compte du fait qu'elles étaient orientées. ( ce que j'ai appelé le nb "d'images" finales possibles)

[bdom001]

Bonjour,
finalement toutes ces explications ne font qu'obscurcir davantage l'énoncé, mais la bonne nouvelle, c'est qu'il ressort de tout cela que j'avais bien compris dès le départ. Mais c'est ma faute. Lorsque je dis « ce n'est pas très clair », je veux en fait dire « Non, ce n'est pas ASSEZ clair ».

La deuxième bonne nouvelle c'est que malgré une lacune de l'énoncé qui ne précise pas que deux cases se distinguent non seulement par leur positions topographiques, mais aussi par le nombre de jetons qu'elles empilent, j'avais considéré cette règle comme implicite.

Par contre, ayant complétement zappé la contrainte suivante :

Sur chaque case on va déposer un jeton de tels sortes que chaque ligne et chaque colonne soit occupé par au moins 1 jetons

Mon premier calcul est donc faux.

Je récapitule les règles et contraintes:
1) Un carré à 9 cases ordonnées (non-interchangeables) se distinguant donc par leur position topographique mais aussi par le nombre de jetons quelles supportent (0,1 ou plus);
2) 5 Jetons indifférenciés/non-ordonnés (interchangeables) à positionner sur des cases;
3) Au moins un jetons sur chaque ligne et colonne;
4) Pas de jeton sur la case centrale.

Après une nouvelle réflexion incluant la contrainte précédemment omise, voici mon raisonnement :

a) D'abord je remarque, (comme ansset) que la règle (3) implique qu'il existe 4 configurations de base nécessitant 3 jetons;
b) Une fois les trois jetons de la configuration de base posés, il reste deux jetons à positionner
c) Avec deux jetons restant, il existe 8^2/2!=32 possibilités de les placer sur 8 cases ordonnées
d) À partir d'une des configurations de base, parmi les 32 possibilités précédentes, il existe 2 configurations permettant d'aboutir à une autre configuration de base, donc induisant une redondance, donc que je retranche à 32, se qui ramène à 30 possibilités.

Mon résultat final est donc :

Cdlt

[Médiat]

Bonjour,

Ce n'est toujours pas très clair pour moi (à cause du message #1)

Est que les cas :

1 |   | 		  | 1 | 		  | 1 | 			  |   | 1
  | X | 2		2 | X | 		  | X | 2			2 | X | 
  | 2 | 		  |   | 2		2 |   | 			  | 2 |

Sont bien différents ?

Si oui, je trouve 144 cas (à vérifier, en tout état de cause)

[ansset]

c'est l'interprétation que j'ai mais avec un résultat 148 ! que du coup je vais vérifier aussi.....

[ansset]

@Mediat :
obtiens tu 144 par programme ou par déduction ( arbre ) comme la démarche que j'ai prise ?

[Médiat]

Bonjour ansset,

Par la constitution d'un arbre

[ansset]

OK, alors l'un de nous deux a fait une erreur.
je ne vois pas encore la mienne.
je cherche.
Cdt

[Médiat]

Allons-y doucement :

Soit il y a 3 cases avec des jetons, soit 4 soit 5 et, évidemment, ces cas sont complets et exclusifs, il faut et il suffit de compter chacun de ces cas et de les ajouter.

Cas 3 cases : choisir ces 3 cases, il y a 4 solutions (à la main), puis placer les 2 pièces suivantes sur ces mêmes 3 cases : 6 possibilités soit au total pour ce cas 24 possibilités.

Etes-vous d'accord sur ce premier point ?

[ansset]

absolument.
c'est un des points de l'arbre que je détaille dans la première page.

[Médiat]

Ok

Cas 4 cases : à partir des 4 cas de départ, on ajoute un jeton sur une des places libres (et il n'y a pas de collisions, il me semble) soit 5 possibilités et le dernier jeton sur une des places occupées soit 4 possibilités, soit au total pour ce cas : 4 x 5 x 4 = 80 possibilités.

Toujours d'accord ?

[ansset]

je viens déjà de voir deux erreurs dans mon calcul avec 4 cases occupées.
sur-estimation du nb de cas avec 1 ou 2 angles ( 16 et pas 32 ) et sous-estimation du cas à 3 angles. ( j'avais écrit 0, or ça doit être 24)
mais le total n'est pas encore juste. ( 4 qui manquent )

[ansset]

Ok

Cas 4 cases : à partir des 4 cas de départ, on ajoute un jeton sur une des places libres (et il n'y a pas de collisions, il me semble) soit 5 possibilités et le dernier jeton sur une des places occupées soit 4 possibilités, soit au total pour ce cas : 4 x 5 x 4 = 80 possibilités.

Toujours d'accord ?

je ne comprend pas, quels 4 cas de départ ?

[Médiat]

Les 4 cas avec 3 cases occupées avec un seul jeton par case

[ansset]

s'il s'agit des 4 cas à 3 cases, ça ne marche pas.
par exemple une solution avec une ligne remplie + un jeton dans un angle par exemple ne correspond pas à une solution à 3 jetons + 1 ailleurs.

[Médiat]

Vous parlez de

X | X | X
  |   | 
X |   |

J'ai bien rempli une ligne + un angle, mais cela ne marche pas : pas de jeton en ligne 2

[ansset]

je viens déjà de voir deux erreurs dans mon calcul avec 4 cases occupées.
sur-estimation du nb de cas avec 1 ou 2 angles ( 16 et pas 32 ) et sous-estimation du cas à 3 angles. ( j'avais écrit 0, or ça doit être 24)
mais le total n'est pas encore juste. ( 4 qui manquent )

correction : cela doit être bien 32 et pas 16 en tenant compte des rotations et d'une seule symétrie.
mais du coup j'obtiens mon chiffre initial 148 auquel il faut que je rajoute les 24 oubliés : soit 172 !
bon, je reprendrais au calme tout à l'heure.

[Médiat]

En tout état de cause ma solution à 4 cas est incomplète ...

Il manque le cas où aucun angle n'est remplis (qui ne peut pas provenir d'une solution à 3 cases), soit 4 cas à ajouter, Total (provisoire) = 148

[ansset]

comme c'est la plus complexe (4 cases ), et que j'ai encore de gros doutes sur mes résultats, j'avais séparé ce cas de figure en 5 possibilités.
-pas d'angle concerné
-1 seul angle
-2 angles
-3 angles
-les 4 angles.....