Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 21-01-2018 20:10:51

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Déénombrement pâtissier

Bonjour à tous,

n'ayant pas abandonné le gâteau 149, je suis tombé sur un problème intéressant de dénombrement.

On dispose 12 pépites de chocolat sur un gâteau en forme de grille de 6x6 cases, de sorte que chaque ligne et chaque colonne contienne exactement 2 pépites.

http://www.prise2tete.fr/upload/Ebichu-pepites.png

Combien y a-t-il de façons de procéder, si l'on considère que deux gâteaux symétriques sont différents ?

Je précise pour les allergiques qu'il est possible de résoudre ce problème sans ordinateur smile


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 22-01-2018 17:38:21

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

dénombrement pâtiqsier

67950 tombe bien !

Bon, je n'ai pas cherché à finasser, enfin si un peu au début, mais je me suis perdu.
Alors j'ai défini un nombre en commençant par le plus petit :

12 12 34 34 56 56

et en échangeant les chiffres, et en y allant toujours dans le sens croissant, avec bien entendu jamais 2 chiffres dans la même paire. En remarquant les redondances, il ne m'a fallu qu'une seule page A3 pour en venir à bout.

Mais bon, j'ai eu du bol de ne pas faire d'erreurs de calcul, ni d'en oublier !

 #3 - 22-01-2018 18:43:48

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Dénombrement pâtissierr

@nodgim : bravo ! Il y avait moyen de finasser, la preuve dont je dispose est nettement plus compacte, mais l'essentiel c'est d'aboutir.

 #4 - 24-01-2018 17:26:47

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Dénombremnt pâtissier

Bonjour,

Si on part d'une pépite, et qu'on se déplace jusqu'à la suivante alternativement horizontalement et verticalement, on finit par revenir au point de départ.
Les seuls cycles possibles ont pour longueur 4, 6, 8 ou 12.

Avec 12 pépites, on peut avoir un des 4 cas suivants :
1) 3 cycles de 4
2) 1 cycle de 4 + 1 cycle de 8
3) 2 cycles de 6
4) 1 cycle de 12

Si on appelle A(n,p) le nombre  d'arrangements de n éléments pris p à p, le nombre de possibilités dans chaque configuration est :

Code:

1)  1350 = ( A(6,2)*A(4,2)*A(2,2) )**2 / (4*4*4) / 6
2) 16200 = ( A(6,2)*A(4,4) )**2 / (4*8)
3)  7200 = ( A(6,3)*A(3,3) )**2 / (6*6) / 2
4) 43200 = ( A(6,6) )**2 / (12)

soit un total de 67950 possibilités.

J'ai vérifié le résultat avec un script en python3 qui place les pépites dans toutes les positions possibles.

 #5 - 24-01-2018 19:24:18

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

DDénombrement pâtissier

Félicitations ! Très jolie méthode de dénombrement, et très efficace smile

enigmatus a présenté une solution qui ne nécessite que 4 calculs pas trop compliqués.

 #6 - 25-01-2018 17:41:57

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Dénombrement ppâtissier

Bonsoir Ebichu

Je n'ai pas eu beaucoup de temps libre cette semaine , si tu pouvais laisser caché jusqu'à samedi smile

Vasimolo

 #7 - 25-01-2018 17:52:50

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

dénombrzment pâtissier

Bien sûr, je rajoute du temps.

 #8 - 26-01-2018 08:35:54

nobodydy
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1677

dénombrement pâtissiee

Salut

Je ne suis pas très fier de moi sad
mais bon !

pour une grille de :
2x2 : 1 possibilité (pas trop dur de tête)
3x3 : 6 (facile avec un crayon)
4x4 : 90 (facile mais excel est plus rapide)

ensuite un coup d'OEIS à tout hasard et bingo !
A001499    Number of n X n matrices with exactly 2 1's in each row and column,
1, 0, 1, 6, 90, 2040, 67950

Voila , tu connais mon niveau en math lollol

Bonne journée

 #9 - 26-01-2018 19:15:45

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

dénombrement pâtissizr

@nobodydy : je n'y avais même pas pensé, bravo smile

 #10 - 27-01-2018 16:19:58

Flight
Visiteur

Dénombrement pââtissier

Salut
Je dirais (C(6,2).C(4,2).C(2,2))^2=8100

 #11 - 28-01-2018 10:00:13

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

dénombrement pâtissirr

J'ai quand même fini par en venir à bout smile

Je n'ai pas trouvé d'astuce combinatoire , je me suis rabattu sur les probabilités en choisissant au hasard une paire sur chaque ligne :

http://www.prise2tete.fr/upload/Vasimolo-deuxparligne.png

C'est "un peu" lourd , on doit pouvoir faire plus simple .

Vasimolo

 #12 - 28-01-2018 11:54:43

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

dénombrement pâtissiee

@Flight : salut, non, ce n'est pas ça. C'est un peu plus compliqué.

@Vasimolo : très bien ! La méthode dont je dispose est du même niveau de complexité, j'ai l'impression que c'est la méthode "duale" de la tienne. Je doute que l'on puisse faire beaucoup plus simple.

 #13 - 30-01-2018 09:21:40

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

dénombrement pâtissuer

C'est terminé, merci à tous les participants.

Voici ma façon de voir les choses. On remplit les colonnes une par une, de gauche à droite, de toutes les façons possibles.

Pour la première colonne, il y a [latex]\binom{6}{2}=15[/latex] façons de procéder. Puis il faut maintenant remplir 5 colonnes, de sorte que 2 des lignes contiennent 1 pépite, et 4 des lignes contiennent 2 pépites. Pour remplir la 2e colonne, il faut donc distinguer 3 cas :
* les 2 pépites de la colonne tombent chacune sur une des 2 lignes où 1 pépite manque (1 façon de procéder).
* les 2 pépites de la colonne tombent l'une sur une des 2 lignes où 1 pépite manque, l'autre sur une des 4 lignes où 2 pépites manque (2*4=8 façons de procéder).
* les 2 pépites de la colonne tombent chacune sur une des 4 lignes où 2 pépites manque ([latex]\binom{4}{2}=6[/latex] façons de procéder).

Il faut ensuite continuer récursivement le procéder. Pour généraliser, appelons [a,b] le nombre de façons de remplir un rectangle où a représente le nombre de lignes où 1 pépite manque, et b le nombre de lignes où 2 pépites manquent.
Le nombre de lignes du rectangles est alors (a+b), tandis qu'il comporte (a+2b)/2 colonnes.

Le raisonnement ci-dessus se généralise par la relation [latex][a,b]=\binom{a}{2}[a-2,b]+\binom{a}{1}\binom{b}{1}[a,b-1]+\binom{b}{2}[a+2,b-2][/latex], soit [latex][a,b]=a(a-1)/2[a-2,b]+ab[a,b-1]+b(b-1)/2[a+2,b-2][/latex].

On recherche dans ce problème la valeur de [0,6], et on peut l'obtenir à l'aide du tableau suivant.

http://www.prise2tete.fr/upload/Ebichu-denombrement.png

On initialise [0,0] à 1, puis on remplit le tableau de haut en bas, puis de gauche à droite. En bas à droite, j'ai indiqué comment remplir une case à partir de 3 cases précédentes (ou moins si on est près du bord du tableau). Par exemple, pour la case [2,4], on fait 2(2-1)/2[0,4]+2*4[2,3]+4(4-1)/2[4,2]=1*90+8*204+6*468=4530.

La solution était donc 67950, bravo à ceux qui ont trouvé. Comme observé par nobodydy, OEIS connaissait...

En question bonus, en généralisant ce raisonnement, j'arrive à calculer le nombre de façons de remplir une grille 9x9 de sorte que chaque ligne et chaque colonne contienne exactement 3 pépites, mais comme cela représente plusieurs dizaines de calculs, j'ai eu recours à un programme. On doit trouver un nombre à 14 chiffres ne comportant ni 3 ni 4, et OEIS le connaît.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete