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


É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?

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 !


Shadock

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