|
#1 - 11-01-2018 08:55:24
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Traajets sur un rectangle découpé
Bonjour @ tous.
On découpe dans du papier quadrillé un rectangle 14*6. On repère le pt A en (0,0) en bas à gauche et le pt B en haut à droite en (14,6). On découpe dans le rectangle 2 fenêtres carrées 2*2 centrées en (2,2 ) et (12,4).
On compte le nombre de chemins possibles (cheminement par les contours autorisé) pour aller de A à B en progressant sur le quadrillage uniquement soit vers le haut soit vers la droite. On m'a dit qu'avec les fenêtres le nombre de chemins possibles était moins de la moitié de celui sans les fenêtres.
Qu'en pensez vous ?
#2 - 11-01-2018 10:23:46
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Trajets sur un rctangle découpé
Salut nodgim,
j'en pense que c'est vrai : 19296 < 38760/2
#3 - 11-01-2018 12:09:20
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
trajets sur un revtangle découpé
C'est bon Ebichu, et vite fait s'il vous plait !
Et sans tableur ?
#4 - 11-01-2018 14:14:38
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
trajets sur in rectangle découpé
Bonjour,
nodgim a écrit:On m'a dit qu'avec les fenêtres le nombre de chemins possibles était moins de la moitié de celui sans les fenêtres.
"On" t'a bien renseigné. Je trouve respectivement 19296 et 38760 chemins, soit moins de 49,8%.
Ce calcul peut se faire à la main, de proche en proche : pour chaque point du quadrillage, le nombre de chemins est la somme des nombres de chemins arrivant au point de gauche et à celui du dessous. C'est fastidieux, et j'ai fait un scrpt en python3.
En voici le résultat :
#5 - 11-01-2018 15:32:40
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Trajets sur un rectangl découpé
Sans tableur je dirais : [latex]\binom{20}{6}=38760[/latex] et [latex]\binom{20}{6}-\binom{4}{2}\binom{16}{4}-\left(\binom{16}{4}-\binom{4}{2}\binom{12}{2}\right)\binom{4}{2}=19296[/latex].
#6 - 11-01-2018 16:20:03
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
ttajets sur un rectangle découpé
Salut !
A moins que je ne me sois trompé, je trouve que c'est faux (mais proche) :
38760 chemins sans fenêtre et 19296 avec...
#7 - 11-01-2018 18:07:04
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Trajets sur n rectangle découpé
@ Ebichu: c'est bien en effet la formule à utiliser. Tu as fait le tour complet du problème. Bravo à toi !
@ Enigmatus et Golgot :
Ce sont les bons résultats, bravo à vous deux ! Et beau dessin pour Golgot pour qui le résultat est toujours à emballer dans un beau papier. Salut l'artiste !
Reste à tenter de trouver une justification à ces résultats.
#8 - 11-01-2018 20:54:22
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Tajets sur un rectangle découpé
Dans le cas sans fenêtres, le nombre de chemins pour arriver au point de coordonnées (i,j) est C(i+j,i) (nb de combinaisons de i valeurs choisies parmi i+j).
#9 - 12-01-2018 07:36:07
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Trajets sur un rectanglee découpé
Oui Enigmatus. C'est à partir de cette idée qu'on arrive à trouver la solution avec les fenêtres.
Indice: soit en calculant avec des points intermédiaires, soit par soustraction.
#10 - 12-01-2018 14:45:01
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
trajets sur un rectangle dévoupé
Je ne sais pas si c'est l'explication que tu voulais, mais le résultat du décompte avec fenêtres s'obtient par le calcul :
On enlève d'abord la valeur de la case en bas à gauche (2 parmis 4) qui fait 6 et qui se répèterai si elle était là 4 parmi 16 fois, puis on enlève l'autre fenêtre qui donne la soustraction un peu plus compliqué...
#11 - 12-01-2018 17:03:07
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
trajets sur un rectangle déciupé
C'est bien Golgot, bravo à toi !
C'est toujours la même chose, ce n'est pas compliqué une fois qu'on a compris le truc.
#12 - 12-01-2018 18:54:37
Trajets sur un rectanggle découpé
J'ai trouvé 37100 pour le nombre de chemins sans fenêtre et j'ai trouvé 1056 avec les fenêtres. Donc avec les fenêtres s'est bien moins de la moitié.
#13 - 12-01-2018 19:19:09
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,996E+3
trajets sur yn rectangle découpé
Je me trompe peut-être, mais la solution a l'air relativement simple.
Sans fenêtre le nombre de chemins possibles est le nombre de manières de placer les 6 déplacements verticaux parmi les 20 nécessaires , soit C(6,20)
C(6,20) = 20 ! / ( 6! 14! ) = 38760.
En rajoutant une fenêtre en (2,2), il faut , de la même façon, retirer tous les chemins y menant soit C(2,4) multiplié par le nombre de chemins en partant.
A retirer : C(2,4) C(4,16) => C(6,20) - C(2,4) C(4,16)
On retire aussi le nombre de chemins passant par la seconde fenêtre (identique par symétrie).
A retirer : C(2,4) C(4,16) => C(6,20) - 2 C(2,4) C(4,16)
Seulement, on a retiré deux fois les chemins passant par les deux fenêtres...
A rajouter : C(2,4) C(2,4) C(2,12)
C(6,20) - 2 C(2,4) C(4,16) + C(2,4) C(2,4) C(2,12)
= 38760 - ( 2 * 6 * 1820 ) + ( 6 * 6 * 66 ) = 19296
On retire donc bien un peu plus de la moitié des chemins ( 19380 )
#14 - 13-01-2018 07:48:16
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
trajets sur un rrctangle découpé
@ Juju : Non. Ton nombre de chemins sans les fenêtres est proche de la vérité, mais pas ton nombre avec les fenêtres.
@ Gwen : Parfait ! Tu as écrit exactement ce que j'avais envie de dire en conclusion. Tu es télépathe ou médium ?
#15 - 13-01-2018 12:27:05
Trajets sur un rectagle découpé
Rebonjour, J'avais une erreur de calcul, avec les fenetres je trouve 38760. Et sans les fenêtres, j'avais mal dimensionné les fenêtres, je trouve 19296. Donc oui avec les fenêtres le nombres de chemin est moins de la moitié (38760/2=19380)
#16 - 14-01-2018 07:47:45
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
trajets sur un recrangle découpé
OK Juju, c'est bon maintenant, bravo à toi !
Il y a un raccourci théorique pour ce problème, qui évite le recours à du calcul algorithmique.
#17 - 14-01-2018 19:21:34
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Trajets sur un rectnagle découpé
Question subsidiaire : on découpe dans du papier quadrillé un rectangle 7*7. On repère le point A en bas à gauche par (0;0) et le point B en haut à droite par (7;7).
Quel est le nombre minimal de points du quadrillage qu'il faut supprimer (par exemple, dans son énoncé, nodgim avait supprimé deux points) pour que le nombre de chemins possibles pour aller de A à B soit 2018 ?
#18 - 14-01-2018 20:15:57
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Trajets sur un rectangl edécoupé
Spoiler : [Afficher le message] Il suffit d'enlever les mailles (2;1) et (6;1)
#19 - 14-01-2018 21:18:02
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Trajets sur un rectangle découpéé
@golgot59 : bien vu À symétrie près, c'est la seule solution.
#20 - 14-01-2018 21:32:56
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Tarjets sur un rectangle découpé
J'ai une autre solution : (0,5) (1,2)
#21 - 14-01-2018 21:39:43
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Trajets sur un recttangle découpé
@enigmatus : je ne pense pas, ça fait 2010. Je pense que tu as mis un 1 au lieu d'un 0 en (0,6).
#22 - 14-01-2018 22:10:40
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
trajzts sur un rectangle découpé
#23 - 15-01-2018 16:29:40
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
trajets sur un rectangle fécoupé
Bon, je n'ai pas pu examiner la relance d'Ebichu, mais si ça vous intéresse, j'avais gardé par devers moi cette configuration là :
Rectangle toujours de (6,14) et fenêtre centrée au milieu de 4*2 (longueur de la fenêtre parallèle à la longueur du rectangle).
Nombre de chemins ?
#24 - 15-01-2018 16:50:20
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Trajets sur un rectangle déccoupé
Spoiler : [Afficher le message] [latex]\binom{20}{6}-\binom{10}{3}^2-2\binom{10}{2}\binom{9}{3}=16800[/latex]
#25 - 15-01-2018 17:12:23
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
trajets sur un rectangme découpé
Spoiler : [Afficher le message] avec le tableur 16800
|
|