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 - 29-03-2017 08:53:03

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

On traverse beuacoup ?

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



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 29-03-2017 12:00:55

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 382

on traverse braucoup ?

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 453

On traverse beaucup ?

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 : 189

on tracerse 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 : 3137

On trvaerse beaucoup ?

@ 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 453

on traverse bzaucoup ?

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 travverse 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 : 189

On travrese beaucoup ?

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 : 3137

on traverse beaucoip ?

@ 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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

On traverse beaucooup ?

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.

Code:

    0    1    8   36  120  330  792 1716
    0    1    7   28   84  210  462  924
    0    1    6   21   56  126  252  462
    0    1    5   15   35   70  126  210
    0    1    4   10   20   35   56   84
    0    1    3    6   10   15   21   28
    0    1    2    3    4    5    6    7
    1    1    1    1    1    1    1    1

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.

Code:

   0   0   0   0   0   0   0 429
   0   0   0   0   0   0 132 429
   0   0   0   0   0  42 132 297
   0   0   0   0  14  42  90 165
   0   0   0   5  14  28  48  75
   0   0   2   5   9  14  20  27
   0   1   2   3   4   5   6   7
   1   1   1   1   1   1   1   1

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 : 3137

On traverse bbeaucoup ?

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,661E+3

On travers 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.
http://www.prise2tete.fr/upload/gwen27-ontraverse.PNG
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 : 3137

On traerse 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,661E+3

on traverse beaucoip ?

Je ne connais pas du tout lol

 #15 - 02-04-2017 17:06:04

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,661E+3

On traverse eaucoup ?

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 : 3137

on travzrse beaucoup ?

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 : 3137

On trvaerse 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.

 

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 : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
15-02-2011 Enigmes Mathématiques
P2T
17-02-2016 Enigmes Mathématiques
18-08-2015 Enigmes Mathématiques
02-10-2012 Enigmes Mathématiques
P2T
Balade de tour par MthS-MlndN
24-10-2009 Enigmes Mathématiques
P2T
01-01-2017 Enigmes Mathématiques
P2T
La Machine v2.0 par SabanSuresh
28-10-2014 Enigmes Mathématiques
P2T
Equation Differentielle par salehseghiri
30-11-2011 Enigmes Mathématiques
P2T
14 = 16 par fred101274
22-12-2010 Enigmes Mathématiques

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