{"word_count": 781, "character_count": 5574}
Pendant les "vacances", j'étais avec les enfants (le plus grand et la plus petite) au palais de la découverte, à Paris, à l'exposition temporaire "faîtes vos jeux". Comme toujours, je suis surpris quand je compare les musées de sciences, et les musées d'art (j'avais fait un billet voilà quelques années en comparant le MoMaths et le Gugenheim, à New York City). Autant ma grande fille est autant intéressée par les tableaux que par les sciences, autant les deux autres préfèrent mille fois les seconds au premier. On a d'ailleurs passé plus de 4 heures au musée (dont une à faire toutes les animations de "faîtes vos jeux"), il a fallu y aller parce que j'avais une réunion de boulot (oui, les parisiens n'étaient pas en vacances, et j'avais une réunion impossible à déplacer). D'où les guillemets à "vacances" (le second jour de notre excursion, c'était une intervention de deux heures en fin d'après midi).Mais je m'égare... A un des stands de l'animation, il avait le défi des abeilles,Sur notre "damier" 8x8 (ici), on a 32 cases bleues et 32 rouges (ou oranges), et on cherche la probabilité qu'un chemin permette de passer d'un côté à l'autre. Sur le moment, le problème m'a pas mal pris la tête, et je me disais que la réponse devait être compliquée... en tout cas, que ça n'était pas aussi simple que ça...En ligne, on peut trouver le guide de l'enseignant qui apporte des compléments aux divers ateliers, et qui propose, en l'occurrence, une solutionLa réponse serait-ici 1/2. Mais la réponse ne me satisfait pas, en particulier la phrase "son absence à l'inverse impose un chemin orange" qui suppose qu'il existe forcément un chemin, soit rouge, soit bleu, pour passer d'un côté à l'autre, ce qui ne me semble pas trivial ! QuantPar exemple sur le damier 4x4 ci-dessous,il n'existe aucun chemin rouge allant  du bas vers le haut, et aucun chemin bleu non plus ! Et si on regarde, il existe (au moins) un chemin rouge allant de la gauche vers la droite, et un chemin bleu. Bref, la réponse 1/2 me semble douteuse....  Pour ceux qui veulent de vrai hasard (mais qui a autant de chance d'apparaître que celui au dessus), on a le graph ci-dessousMais maintenant essayons de la calculer cette probabilité. Par simulations au moins. Regardons un damier,on peut le visualiser sous forme d'une matriceou en décalant un peu d'une matrice carrée 4x4 (ici)Si on regarde ce que sont les voisins (afin de faire un chemin), sur le schéma initial, on cherchait les configuration suivantesce qui, dans notre matrice, correspond aux éléments ci-dessous,Bref, on va pouvoir connecter des points d'un graph, et regarder si les 4 premiers éléments du graphs sont connectés aux 4 derniers(le but est désormais de savoir si le nord et le sud connectent, peu importe la couleur). On peut commencer par créer le graphd=4set.seed(1)C=sample(c(rep(1,d^2/2),rep(2,d^2/2)),size=d^2)M=matrix(C,d,d)&#62; M[,1] [,2] [,3] [,4][1,] 1 1 2 2[2,] 1 2 1 1[3,] 2 2 1 1[4,] 2 2 1 2ce qui correspond bien à notre matrice ci-dessousOn va alors créer le graph, c'est à dire chercher les noeuds qui communiquentlibrary(igraph)B=NULLfor(i in 1:(d^2)){x=rep(i,6)y=c(i-d,i-d+1,i-1,i+1,i+d-1,i+d)if(i%%d==1) y=c(i-d,i-d+1,NA,i+1,NA,i+d)if(i%%d==0) y=c(i-d,NA,i-1,NA,i+d-1,i+d)D=data.frame(x,y)D=D[(D$y&#62;=1)&#38;(D$y&#60;=d^2),] B=rbind(B,D[which(C[D$y]==C[D$x]),]) } B=B[(B[,2]&#62;=1)&#38;(B[,2]&#60;=d^2),]G=as.vector(t(B))m=make_graph(G)On peut ainsi voir ici que 1 communique avec 2, et 5&#62; B[B$x==1,]x y4 1 26 1 5On peut d'ailleurs visualiser le graph, et voir qu'il est constitué de 4 graphs disjoints,&#62; plot(m)(le coin 16 étant isolé, sans connection avec le reste - étrangement - il n'apparait pas sur le graph)Pour trouver tous les points qui communiquent entre eux, on peut itérer un peu (voire beaucoup, peu importe)G_iter=connect(make_graph(G), d^2)connectpt=function(x) as.numeric(adjacent_vertices(G_iter,x)[[1]])Ici, le nord et le sud communiquent s'il y a au moins un chemin (peu importe la longueur)sum(unlist(Vectorize(connectpt)(1:d))%in%(d^2+1-(1:d)))&#62;0On peut alors une petite fonction, qui va générer une répartition des couleurs sur un damier carré (de longueur paire)simu=function(d){C=sample(c(rep(1,d^2/2),rep(2,d^2/2)),size=d^2)B=NULLfor(i in 1:(d^2)){x=rep(i,6)y=c(i-d,i-d+1,i-1,i+1,i+d-1,i+d)if(i%%d==1) y=c(i-d,i-d+1,NA,i+1,NA,i+d)if(i%%d==0) y=c(i-d,NA,i-1,NA,i+d-1,i+d)D=data.frame(x,y)D=D[(D$y&#62;=1)&#38;(D$y&#60;=d^2),] B=rbind(B,D[which(C[D$y]==C[D$x]),]) } B=B[(B[,2]&#62;=1)&#38;(B[,2]&#60;=d^2),] G=as.vector(t(B)) G_iter=connect(make_graph(G), d^2) connectpt=function(x) as.numeric(adjacent_vertices(G_iter,x)[[1]]) sum(unlist(Vectorize(connectpt)(1:d))%in%(d^2+1-(1:d)))&#62;0}On peut alors construire la fonction suivante, pour faire un peu de monte carloappr=function(d,nsimu) mean(Vectorize(simu)(rep(d,nsimu)))Par exemple sur notre damier 4x4, on a environ 3 chances sur 4 d'avoir un chemin (peu importe sa couleur) qui permette de rejoindre le sud depuis le nord&#62; appr(4,10000)[1] 0.7446alors que sur le 8x8 du palais de la découverte, on a&#62; appr(8,10000)[1] 0.780578% de chances (un peu plus). Ce qui semble confirmer qu'il n'y a pas forcément un chemin permettant d'aller du nord au sud.On peut d'ailleurs faire un petit dessin pour noter que quand la dimension du damier augmente (je n'ai pas tenté ici le cas impair - avec une case de plus d'une certaine couleur), la probabilité de trouver au moins un chemin semblerait augmenter (même si ça reste à prouver, et en particulier, je serais curieux de voire vers quoi ça converge...)&#160;