# Le Monde puzzle [43]

**Xi'an's Og » R**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

**H**ere is the puzzle in * Le Monde* I missed last week:

Given a country with 6 airports and a local company with three destinations from each of the six airports, is it possible to find a circular trip with three intermediate stops from one of the airports? From all of the airports?

One more airport is opened with the same rules about the three destinations. Is it still possible? And with yet another airport?

An R resolution is to run random links between airports and to check whether a trip is possible. Here is my solution

A=8 #number of airports L=3 #number of flights between airports orgn=rep(0,A) #occurrences of round trip allorg=1 #round trip from all airports T=10^4 #maximum number of tries for (t in 1:T){ con=matrix(0,A,A) #flight connections i=1 while ((sum(con[i,])<4)&&({3-sum(con[i,])}<{A-i})&&(i<A)){ #checking for the constraint to hold #random flights to remaining targets con[i,sample(((i+1):A),3-sum(con[i,]))]=1 con[con[i,]==1,i]=1 #symmetry i=i+1 } if ((i==A)&&(sum(con[A,])==3)){ tour=(con%*%con>0)*1 for (i in 2:4) #3 intermediate stops tour=(tour%*%con>0)*1 for (u in 1:A) #starting airport orgn[u]=max(orgn[u],(tour[u,u]>0)) if (max(diag(tour))>0) #one or all? allorg=min(allorg,min(diag(tour))) } if (max(orgn)>0) break() #end of the random search }

The only trick is the matrix product that simplifies the computation of the connectivity graph for the airports linked in four trips. Running the above R code shows that for six and eight airports there are always circuits with 3 stops, but that for seven airports, it is impossible to ensure three destinations (the loop never breaks and tour is never created). This is true for any odd number of airports.

Filed under: R Tagged: Le Monde, mathematical puzzle, simulation

**leave a comment**for the author, please follow the link and comment on their blog:

**Xi'an's Og » R**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.