Le retour des abeilles

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


2 thoughts on “Le retour des abeilles”

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

Leave a Reply

Your email address will not be published. Required fields are marked *