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 - 05-06-2014 19:41:16

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

mathématiques pour les nuls 21 (chemon sûr)

Me revoici avec une énigme sans doute probabiliste, j'avoue ne pas encore avoir la réponse au deux dernières questions, et je ne sais pas si toutes les questions (en fait il n'y en a qu'une, la question ultime, mais il me semble plus cohérent d'y aller par étape pour bien comprendre ce qu'on fait) peuvent être résolues sans ordinateurs... roll


Énigme :
On considère un quadrillage fait de carrés. A chaque intersection on pourra selon les cas mettre un point, et on pourra se promener de point en point dans toutes les directions même les diagonales. On appellera chemin toute réunion de points allant du bas vers le haut ou de la gauche vers la droite et réciproquement. Un chemin ne peut donc pas commencer sur la bas de la grille et finir sur la droite par exemple.
On notera (n,m) une grille de n points de large et de m points de long.
On notera (moi je le ferai si vous avez meilleur je prends bien sûr) [latex]\alpha_{(n,m)}^k[/latex] le nombre minimum de points pour une grille de taille (n,m) avec une proba de k au moins. On pourra juste noter [latex]\alpha_{(n)}^k[/latex] si la grille est carrée.

Questions :

1) Combien de points faut-il au minimum placer sur une grille finie, de taille (n,n) donc carrée, pour être sûr d'aller d'un bout à l'autre de la grille? Plus généralement de taille (n,m) ?

2) Combien de points faut-il au minimum placer sur une grille finie carrée pour avoir au moins une chance sur deux de pouvoir traverser la grille? Et avec une grille rectangulaire?


Question ultime : Combien de points faut-il au minimum placer sur une grille finie de taille (n,m) pour être sûr de pouvoir traverser la grille dans k% des cas au moins? big_smile

Voilà j'espère que ça vous plaira je mets 100 heures pour le moment et si l'énigme plait et qu'elle est considérée comme difficile j'ajouterai du temps si vous voulez ! wink


Shadock smile

PS : Je ne prétends pas détenir la vérité absolue mais selon moi [latex]\alpha_{(4)}^1= 13[/latex]


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
  • |
  • Répondre

#0 Pub

 #2 - 05-06-2014 20:58:31

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3073
Lieu: Au sud du Nord

Mathéatiques pour les nuls 21 (Chemin sûr)

Question ultime

42


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)

 #3 - 05-06-2014 21:48:51

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Maathématiques pour les nuls 21 (Chemin sûr)

@emmaenne remplace Kosmo on dirai tongue


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #4 - 06-06-2014 22:18:12

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

Mathématiques poour les nuls 21 (Chemin sûr)

Merci pour cette énigme. Si j'ai bien compris:

- Il faut partir d'une extrémité du damier et parvenir exactement à celle d'en face ?
- On ne peut avancer que d'une case à la fois (autrement dit, si il n'y a pas de point présent en diagonale ou tout droit, on a perdu) ?
- La portion de chemin entreprise entre deux points consécutifs doit toujours rapprocher de l'extrémité à atteindre ?

Comment choisit-on l'emplacement de départ ? Je suppose qu'on le choisit après placement des points ? Peut-on démarrer à partir d'un emplacement où on n'a pas mis de point ?

 #5 - 07-06-2014 12:39:26

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

mathématiques oour les nuls 21 (chemin sûr)

Oui c'est ça, je ferai un dessin ce soir si je suis chez moi sinon j'enverrai une photo smile

En fait on ne choisit pas un point de départ et un point d'arrivée admettons que tu es une grille de taille (10,10) et qu'il y ait 99 points sur ta grille, tu pars du point que tu veux, tu fais le chemin que tu veux qui va toujours dans le même sens ou juste "a plat" et tu finiras bien par trouver un chemin qui t'amène de l'autre côté de la grille smile

Ce qui est important ce n'est pas le point de départ ou d'arrivée c'est le chemin, si il y a un chemin qui va d'un bout à l'autre de la grille alors tout va bien smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #6 - 07-06-2014 15:16:45

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

Mathématiques pour le nuls 21 (Chemin sûr)

Qu'est-ce que c'est, le "bout" d'une grille ?

Doit-on comprendre qu'il faut aller du coin en bas à gauche vers le coin en haut à droite sans jamais redescendre ni retourner vers la gauche ?

 #7 - 07-06-2014 16:26:14

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

Mathématiques pour les nuls 21 (Cheminn sûr)

Je n'ai toujours rien compris à la question. On cherche quoi ? Tu n'as pas un exemple en image ?

 #8 - 07-06-2014 19:13:01

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

mathématiques pour kes nuls 21 (chemin sûr)

Pour qu'il y ait calcul de probabilité, il faut bien qu'il y ait un tirage aléatoire à un moment donné. Quel est ce tirage aléatoire ? A mon avis, c'est l'emplacement de départ, mais j'aimerais être sur.

 #9 - 07-06-2014 20:48:07

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Mathméatiques pour les nuls 21 (Chemin sûr)

http://www.hostingpics.net/viewer.php?id=126646pdt.jpg

Voilà donc on part du point qu'on veut et on arrive au point où on veut pourvu que l'on passe sur un chemin définie susdit smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #10 - 07-06-2014 21:19:45

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

mathématiqyes pour les nuls 21 (chemin sûr)

Je ne comprends vraiment rien à ton problème.  C'est quoi ces trucs de gauche droite haut bad ?  hmm

 #11 - 07-06-2014 22:01:07

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Mathématiques pour les nuls 12 (Chemin sûr)

Bonjour,
Pour la 1ère question, il me semble évident que le moyen le plus économe pour bloquer tout chemin, c'est d'en tracer un qui va d'un coin au coin opposé (sans diagonale). Tout autre choix ouvrirait des chemins, dont le blocage coûterait en définitive autant ou davantage. D'où :
[TeX]\alpha(n)=n^2-2n+2[/latex] (ouh là, je ne trouve déjà pas comme toi...)
dans le cas général :
[latex]\alpha(n,m)=n*m-n-m+2[/TeX]
Avant d'attaquer la proba, voyons pourquoi nous ne sommes pas d'accord...


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #12 - 08-06-2014 00:32:06

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Maathématiques pour les nuls 21 (Chemin sûr)

@gwen : Le dessin ne peut être plus explicite le but est d'aller d'un segment voilà ce sera peut-être plus clair comme ça, d'un segment de la grille au segment opposé le plus loin ^^ je sais je ne comprends pas pourquoi vous ne comprenez pas je crois que je vais finir par faire une vidéo pour vous expliquer mon énigme, une première dans l'histoire de P2T big_smile
Si la grille est carrée, tu pars d'un bord du carré, tu te mets sur le point que tu veux après avoir fait ton tirage aléatoire par exemple dans le cas d'une grille (3,3) il y a au total 9 points au max que tu peux placer sur la grille, si tu décides de tirer aléatoirement 5 points sur la grille tu regardes si tu as au moins un point sur le bord inférieur du carré que forme la grille tu regardes si tu as au moins un point sur le bord du haut du carré et que tu as un chemin entre deux de ces points alors tu pourras traverser d'un bout à l'autre... smile

@Fix où tu as vu dans l'énigme que le but était de bloquer les chemins? On considère tous les chemins possibles smile Sur la grille (3,3) si tu places 3 points aux intersections des lignes du bas et du milieu alors il te reste plus qu'un point à placer sur la ligne du haut pour être sûr à 100% de pouvoir traverser d'un bout à l'autre donc [latex]\alpha_{(3)}^1=7[/latex] voilà c'est tout smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #13 - 08-06-2014 01:06:21

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 236

Mathématiques pour les nuls 21 (hemin sûr)

Le cas de la probabilité [latex]1[/latex] est assez intuitif :
[TeX]\alpha^1_{(n,m)}=(n-1) \cdot (m-1)+1[/TeX]
La généralisation pour une probabilité [latex]k[/latex] semble par contre beaucoup plus complexe...

Tout le problème est en fait de pouvoir dénombrer, pour un nombre de points donné, les configurations qui forment au moins un chemin neutral

 #14 - 08-06-2014 01:16:50

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Mathématiques pour less nuls 21 (Chemin sûr)

Euh, mais :
- il s'agit du nombre de points minimum pour pouvoir tracer un chemin ("horizontal" et "vertical") ou ("horizontal" ou "vertical") ? Dans ton énoncé, je comprends la 2nde possibilité. Et à partir du moment où j'aurais tous les points sur la ligne du bas ou celle du milieu, dans ton exemple, je n'ai pas besoin de chercher d'autres points puisque j'ai plusieurs chemins horizontaux...
- Est-ce qu'un chemin "vertical" peut passer par des points latéraux (bords gauches ou droites) ? Je suis parti du principe que c'était possible...

Mon raisonnement dans mon post précédent visait juste à calculer le nombre minimal de points qu'il suffit de confisquer au joueur pour empêcher tout chemin vertical et horizontal. A partir de là, on en déduit le nombre minimal qu'il suffit d'avoir pour tracer ces fameux chemins !


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #15 - 08-06-2014 19:30:33

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

Mathématiques por les nuls 21 (Chemin sûr)

Shadock, sur une grille de n cases pas n cases, combien de points au maximum peut-on tirer de manière aléatoire (tu avais oublié de préciser qu'on tirait ces points au hasard et de façon équiprobable) ? Est-ce que c'est (n-1)² ?

 #16 - 08-06-2014 23:09:29

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

mathémztiques pour les nuls 21 (chemin sûr)

Les points sont tirés chacun de manière équiprobable.

Et je ne vois pas pas pourquoi vous désespérez tous avec ces histoires de chemin, il suffit de prendre la définition au pied de la lettre... sad

Admettons notre grille est formée par un carré ABCD le but est d'aller de [AB] vers [CD] vous tracer votre grille à l'intérieur du carré et bien évidemment les bords du carré en font parti...si le dessin n'est pas clair avec ça je peux plus rien pour vous moi hmm et ensuite vous tracez vos chemins en reliant les points de proche en proche dans toutes les directions ! smile

Sydre oui c'est exactement ça big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #17 - 09-06-2014 23:35:41

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Mathématiques pour les nuls 12 (Chemin sûr)

Je suis peut-être non-comprenant, mais avec des réponses à mes questions, j'aurais pu changer ! roll


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #18 - 10-06-2014 12:49:09

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

mathématiques pour les nuls 21 (chemun sûr)

Bonjour,

pour le cas où la probabilité est 1 je ne suis pas d'accord avec la formule de Sydre.
Je dirais plutôt :
[TeX]\alpha^1_{(m,n)}=\max(m(n-1),n(m-1))+1[/TeX]
Enfin si j'ai bien compris l'énoncé hmm


Il y a sûrement plus simple.

 #19 - 10-06-2014 13:44:02

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

Mathématiques pour les unls 21 (Chemin sûr)

Ce qui se conçoit bien s'exprime clairement
Et les mots pour le dire arrivent aisément.
                                             (Boileau)

Un énoncé qui ne précise pas sans ambiguïté
1 ce que l'on cherche
2 les conditions/contraintes

ne peut donner lieu à  solution.

 #20 - 10-06-2014 15:06:54

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

mathématiques poyr les nuls 21 (chemin sûr)

Voilà comment j'ai compris l'énoncé.

On a une grille comme ci-dessous (ici 4x4) :

http://www.prise2tete.fr/upload/cogito-mpn21.png

On tire aléatoirement des points parmi les intersections.
Ici on a eu un tirage de cinq points qui sont numérotés dans l'ordre dans lequel ils ont été tirés. Ils se trouvent que ces 5 points (en fait seulement quatre d'entre eux même) forment un chemin car je peux en reliant les points, relier les deux côtés rouges (un exemple de chemin est tracé en vert sur le dessin). Dans l'exemple cité ici, il n'existait pas de chemin avant le tirage du cinquième point.
Si j'avais pu relié les deux côtés bleus, j'aurais eu également un chemin.

J'interprète [latex]\alpha^1_{(m,n)}[/latex] comme étant le plus petit nombre de points qu'il faut tiré dans une grille m x n pour être sûre d'avoir un chemin, c'est-à-dire pour être sur de pouvoir reliés soit les deux côtés bleus, soit les deux côtés rouges en reliant les points comme indiquer dans l'énoncer.

Maintenant, je ne sais pas si cette interprétation est la bonne ou pas.

EDIT : Du coup, je rectifie, je suis effectivement d'accord avec la formule de Sydre smile.
Pardon.

Mais dans ce cas on aurait [latex]\alpha^1_{4}=10[/latex] et [latex]\alpha^1_{3}=5[/latex] qui sont différents des nombres données par shadock, donc je ne sais pas si c'est la bonne interprétation hmm.


Il y a sûrement plus simple.

 #21 - 10-06-2014 16:44:22

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

mathématiques poyr les nuls 21 (chemin sûr)

Si c'est ça, je ne comprends toujours pas les exemples donnés en dessin... hmm

 #22 - 10-06-2014 18:36:51

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

Mathématiques pour les nuls 21 (Chhemin sûr)

fix33 a écrit:

Je suis peut-être non-comprenant, mais avec des réponses à mes questions, j'aurais pu changer ! roll

Mais pourquoi veux-tu changer ?
Tu as la même réponse que Sydre et Shadock a dit à Sydre qu'il avait bon ! roll

Gwen27 a écrit:

Si c'est ça, je ne comprends toujours pas les exemples donnés en dessin... hmm

Ben moi, je ne vois pas d'exemple de dessin donné par Shadock... roll

Je ne comprends rien à ce sujet....


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #23 - 10-06-2014 19:27:56

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

Mathématiques pour les nuls 21 (Chemin sûrr)

C'est dans le message #9 mais on ne voit pas l'image. Il faut copier son URL et l'ouvrir dans un nouvel onglet.

 #24 - 10-06-2014 20:31:32

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

Mathématiques pour les nuuls 21 (Chemin sûr)

Bah vous dites que alpha exposant 1 et indice 3 = 5 (désolé je maîtrise pas le latex).

Bah vous prenez la grille on met 5 points, un au centre, et un à chaque coin et voilà on peut passer à coup sûr de haut en bas et il y a 5 points. Sur la figure, il y'en a plus mais on demande le minimum. Je suis bon ?

 #25 - 10-06-2014 23:42:20

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

Mathématiques pour les nuls 12 (Chemin sûr)

On demande le nombre minimum de points pour que même avec ces points placés au hasard sur les intersections, il existe toujours avec certitude au moins un chemin qui aille de l'extrémité gauche à l'extrémité droite ou de l'extrémité basse vers l'extrémité haute du quadrilatère. Autrement dit, on demande à connaître le nombre de points dans le pire des cas de positionnement.
Enfin je crois que c'est ça lol

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