|
#1 - 29-03-2017 08:53:03
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
On traverse eaucoup ?
Bonjour à tous.
Un jeton, pour aller du bas / gauche au haut / droit d'un échiquier ( 8*8 cases ) se déplace soit d'une case vers le haut, soit d'une case vers la droite. Quelle est la proportion de chemins qui franchit la diagonale Départ / Arrivée ? (se trouver sur une case de la diagonale n'est pas un franchissement ).
Généralisation pour un échiquier de n*n cases.
Bonne recherche
#2 - 29-03-2017 12:00:55
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
On trverse beaucoup ?
Je tente : On peut remarquer que si on note N(n,m) le nombre de façon d'arriver à la case (n,m) en restant "sous la diagonale' on a :
N(1,1)=1 N(n,n+1)=0 pour tout n (vu que l'on ne traverse pas) N(n+1,m+1)=N(n,m+1) + N(n+1,m)
A défaut de se compliquer la vie, on peut remplir de proche en proche un tableau excel ainsi programmé qui donne N(8,8)=429
Donc Proba = 2*429 / C(16,8) = 2/30
#3 - 29-03-2017 14:10:10
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
On traverse beaucoup ??
Il y a [latex]\binom{2n-2}{n-1}[/latex] chemins dans l'échiquier de taille n.
Parmi eux, il y en a [latex]\frac{1}{n}\binom{2n-2}{n-1}[/latex] qui restent au-dessus de la diagonale (nombre de Catalan), et le même nombre en-dessous.
Le nombre recherché est donc [latex]\binom{2n-2}{n-1}(1-\frac{2}{n})[/latex].
Application numérique : pour l'échiquier classique, cela fait [latex]\binom{14}{7}(1-\frac{2}{8})=2574[/latex].
#4 - 29-03-2017 16:11:13
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
On traerse beaucoup ?
Bonjour, soit Cn le n-ième nombre de Catalan. Soit ((k n))= k parmi n Il existe ((n-1 2(n-1) )) chemins possibles. En effet, on peut représenter tout chemin par un nombre binaire de longueur 2(n-1), où 0 signifie un déplacement à droite et 1 un déplacement en haut.
Ill y a C(n-1) chemins sous-diagonaux, C(n-1) sur-diagonaux, donc ((n-1 2(n-1) )) - 2C(n-1) = (n-2)/nx((n-1 2(n-1)))chemins qui traversent
Edit: J'ai corrigé des erreurs entre n et n-1... Je n'ai pas parlé de la proportion. On trouve bien evidemment un rapport de (n-2)/n qui tend vers 1 quand augmente. On traverse donc beaucoup...
#5 - 29-03-2017 19:02:18
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
On traverse beaucop ?
@ Portugal: non, pas vraiment, revois tout ça.
@ Ebichu et Caduck: c'est si connu que ça ? Réponses qui n'ont même pas fait appel à la réflexion, semble t'il... Bravo pour votre mémoire en tout cas.
#6 - 29-03-2017 19:43:09
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
On traverse bbeaucoup ?
Le nombre de chemins dans l'échiquier, ou au-dessus de la diagonale, oui, c'est très classique. Après, il faut encore penser à les utiliser et les assembler de la sorte, ce qui n'est pas totalement évident tout de même.
#7 - 29-03-2017 21:19:12
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
on teaverse beaucoup ?
Houps Je m’étais trompé sur le dénominateur. En regardant "bêtement" sur ma table sans bloquer la diagonale j'obtiens 3432 combinaison donc 25% de proba de ne pas croiser.
#8 - 29-03-2017 23:06:28
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
On travers ebeaucoup ?
La dernière énigme sur les nombres de Catalan n'était vraiment pas vieille, et les chemins qui coupent la diagonale sont vraiment intimement liés aux nombres de Catalan, ce n'était donc pas difficile. J'ai retenu ces nombres car ils ont finalement des applications très importantes en dénombrement.
#9 - 30-03-2017 08:23:35
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
On traverse beauoup ?
@ Portugal: oui, c'est ça, bravo. Il ne te reste plus qu'à regarder la généralisation....
#10 - 31-03-2017 09:59:18
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
On travesre beaucoup ?
Bonjour, On peut convenir de faire le premier déplacement vers la droite, et donc de ne traiter que la moitié des chemins.
Avec franchissement de la diagonale On remplit la ligne du bas avec des 1, et on complète la colonne de gauche avec des 0. On remplit chaque case de proche en proche en faisant la somme de sa case de gauche et de sa case du dessous. Le nombre de chemins pour chaque valeur de n est sur la diagonale.
On reconnaît le triangle de Pascal, et le nombre de chemins pour n est C(2*n-3,n-2).
Sans franchissement de la diagonale Même principe, mais on remplit la ligne du bas avec des 1, et le triangle au-dessus de la diagonale avec des 0. Je n'ai pas trouvé de formule pour les valeurs.
Le rapport cherché pour n=8 est 3/4.
Je trouve un rapport de (n-2)/n dans le cas général, vérifié jusqu'à n=50, mais je ne sais pas le justifier.
#11 - 31-03-2017 19:48:38
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
on trzverse beaucoup ?
Bon travail, Enigmatus, et résultat correct. Bravo ! Ta conjecture est la bonne, mais il te faut abandonner l'informatique pour la preuve.
#12 - 02-04-2017 14:32:04
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,992E+3
on trzverse beaucoup ?
Pour moi, la somme des déplacements possibles est un genre de Pyramide carrée.
Le termes valent (2*n)!/(n!)^2 pour une grille de taille n+1. Les déplacements traversant la diagonale sont équivalents à la moitié des termes sur la diagonale (coins non-compris ) car un trajet sur 2 la franchit ou "rebondit", chaque trajet entrant ayant 2 trajets sortants.
Soit : (2+6+20+70+252+924) dans l'exemple...
Soit pour 8 cases : 3432/(4700/2) = 1175/1716 en pas clair : f(n) / ( f(n-1)-1)
Autrement dit : https://oeis.org/A000984 Sur https://oeis.org/A066796
On a un truc du genre : 0,3333333333 0,4 0,4 0,3888888889 0,3787878788 0,3712121212 0,3656565657 0,3614973262 0,3582887701 0,3557422969 0,3536719035 0,3519546949 0,3505067728 0,349268993 0,3481984498 0,3472632371 0,3464391181 0,3457073411 0,3450531644 0,3444648348 0,3439328647 0,3434495099 0,3430083855 0,34260418 0,342232438 0,3418893946 0,3415718459 0,3412770485 0,3410026395
qui semble évoluer vers 1/3 et on retrouve les valeurs du triangle de Pascal.
#13 - 02-04-2017 16:06:29
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
On travese beaucoup ?
Non, ce n'est pas ça, Gwen. Cela dit, si tu ne connais pas bien les combinatoires, ça risque d'être difficile.
#14 - 02-04-2017 16:34:36
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,992E+3
On travers ebeaucoup ?
Je ne connais pas du tout
#15 - 02-04-2017 17:06:04
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,992E+3
On traverse beaucou p?
Ceci dit, aux erreurs de calcul près, 637/1621 me semble logique à défaut d'être rigoureux...
ça fait 0,37121212.... Bizarre ! ce n'est pas ce que j'ai écrit, mais c'est ce que j'ai dit.
En recalculant : 0,3333333333 0,4 0,4 0,3888888889 0,3787878788 0,3712121212 0,3656565657 0,3614973262 0,3582887701 0,3557422969 0,3536719035 0,3519546949 0,3505067728 0,349268993 0,3481984498 0,3472632371 0,3464391181 0,3457073411 0,3450531644 0,3444648348 0,3439328647 0,3434495099 0,3430083855 0,34260418 0,342232438 0,3418893946 0,3415718459 0,3412770485 0,3410026395 0,3407465723 0,340507066 0,3402825629 0,3400716951
#16 - 02-04-2017 19:15:58
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
On traverse beaucoupp ?
Non, ce n'est pas ça non plus. Désolé. Je crois que sans un minimum de connaissances sur les dénombrements, ça risque d'être compliqué.
#17 - 04-04-2017 16:13:08
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
On travrse beaucoup ?
Le temps est écoulé. Certains d'entre vous ont vite trouvé la relation avec les nombres de Catalan, et le problème leur a semblé somme toute assez classique.
Pour ceux qui ont cherché et n'ont trouvé qu'une solution partielle, voici une explication :
Généralisation pour un échiquier de n*n cases.
C'est équivalent de partir du (0,0) d'un repère orthonormé pour arriver au point (n-1,n-1)= (n',n')
Le nombre de déplacements est constant et égal à 2n'. De plus, si on désigne par 1 un déplacement vers le haut et 0 un déplacement vers la droite, alors il y a autant de 1 que de 0.
Un chemin est donc modélisable par un nombre binaire de 2n' chiffres comportant n' " 1 " et n' " 0 ".
Le nombre de chemins possibles est donc C( 2n', n') qui compte le nombre de placements de n' " 1 " dans 2n' emplacements possibles.
Examinons les déplacements qui démarrent par le haut et qui passent sous la diagonale Départ / Arrrivée. Cette traversée si lit dans le nombre qui modélise le chemin: Elle se produit lorsque le nombre de " 0 " dépasse d'une unité le nombre de " 1 " . Dans ce cas, le nombre de 1 restants dépasse d'une unité le nombre de zéros restants. En termes de comptage, ça ne change rien si on remplace dans les restants un "1" par un "0". Et donc le nombre de combinaisons qui traversent depuis le haut est, si on compte bien, C (2n'-1, n'-2). Et Idem pour le nombre de combinaisons qui traversent depuis le bas. Si on fait le ratio, on arrive à (n'-1) / (n'+1) ou n / (n+2).
Merci aux participants.
|
|