Le Monde puzzle [43]

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 such that returns are always possible, 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=0 #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=max(allorg,min(diag(tour)))
 }

 if (min(orgn)>0) break() #end of the random search
}

The only trick is the matricial 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. The reason is that having an odd number of airports clashes with the constraint on return flights (expressed by the symmetric matrix con.)