Suite à mon précédant billet, “Maudites Abeilles“, j’ai eu des commentaires sur le blog, mais aussi sur Twitter pour me dire que malgré tout, il y avait bien une chance sur deux pour avoir un chemin bleu permettant de connecter les deux régions bleues, celle au nord et celle au sud.
En effet, dans le problème de base, les régions sont colorées, et le problème n’est pas l’existence d’un chemin, mais l’existence d’un chemin de la bonne couleur. Il faut juste rajouter une petite ligne pour spécifier la couleur du chemin
> simu2=function(d){
+ C=sample(c(rep(1,d^2/2),rep(2,d^2/2)),size=d^2)
+ B=NULL
+ for(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>=1)&(D$y<=d^2),] + B=rbind(B,D[which((C[D$y]==C[D$x])&(C[D$x]==1)),]) + } + B=B[(B[,2]>=1)&(B[,2]<=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)))>0}
> appr=function(d,nsimu) mean(Vectorize(simu2)(rep(d,nsimu)))
> appr(4,10000)
[1] 0.4993
et en effet, il y a une chance sur deux de trouver un chemin bleu permettant de connecter les deux régions bleues. Mais comme je le disais hier, j’ai du mal avec l’argument de symétrie évoqué dans la “correction”.
OpenEdition suggests that you cite this post as follows:
Arthur Charpentier (April 27, 2017). Le retour des abeilles. Freakonometrics. Retrieved December 3, 2024 from https://doi.org/10.58079/ov7i
En détaillant beaucoup, le raisonnement est en fait le suivant.
Dans toute la suite, j’écris ∃bleu pour « ∃ chemin bleu d’est en ouest », et ∃orange pour « ∃ chemin orange du nord au sud ».
Tout le problème reste évidemment le même par la symétrie (bleu & est-ouest) ↔ (orange & nord-sud).
C’est parfois plus simple d’imaginer que le bleu représente des fils électriques, et l’orange des isolants.
Il est facile de se convaincre que ∃bleu ⇒ ∄orange, et ∄bleu ⇒ ∃orange :
Si le courant passe d’est en ouest, c’est que j’ai un chemin continu de fils bleus, et que donc les parties isolantes nord et sud sont séparées ;
Si le courant ne passe pas d’est en ouest, c’est donc que j’ai une couche isolante orange continue du nord au sud qui sépare les zones est et ouest (sinon, le courant passerait).
Autrement dit, en fait ∃bleu ⇔ ∄orange. Donc ℙ(∃bleu) = ℙ(∄orange).
Or, par symétrie (que j’utilise seulement ici), ℙ(∄orange)=ℙ(∄bleu).
Au final, ℙ(∃bleu) = ℙ(∄bleu) = ½ = ℙ(∃orange) = ℙ(∄orange).
Ne pourrait-on pas le relier au problème de percolation avec un voisinage lié au pavage avec des haxagones ?