Le Monde puzzle [43]

November 7, 2010

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

Here 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
 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[con[i,]==1,i]=1             #symmetry

 if ((i==A)&&(sum(con[A,])==3)){

 for (i in 2:4) #3 intermediate stops

 for (u in 1:A) #starting airport

 if (max(diag(tour))>0) #one or all?

 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

To 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 on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , ,

Comments are closed.


Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)