Le Monde puzzle [43]

November 7, 2010
By

(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
 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

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.

Sponsors

Mango solutions



RStudio homepage



Zero Inflated Models and Generalized Linear Mixed Models with R

Quantide: statistical consulting and training



http://www.eoda.de







ODSC

ODSC

CRC R books series











Contact us if you wish to help support R-bloggers, and place your banner here.

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)