Le Monde puzzle [#1152]

[This article was first published on R – Xi’an’s Og, 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.

The weekly puzzle from Le Monde is a tournament classic:

An even number of teams play one another once a week with no tie allowed and have played all other teams. Four weeks into the tournament, A has won all its games, B,C, and D have won three games, the other teams have won at least one games. What is the minimum number of teams? Show an instance.

By sheer random search

tnmt=function(K=10,gamz=4){ t1=t0=matrix(1,K,K)
tnmt=function(K=10,gamz=4){ tnmt=t0=matrix(0,K,K) while (!prod(apply(tnmt^2,1,sum)==4)){ tnmt=t0 for (i in 1:(K-2)){ if((a<-gamz-sum(tnmt[i,]^2))> K-i-1) break() if(a>0){ j=sample((i+1):K,a) tnmt[i,j]=sample(c(-1,1),a,rep=TRUE) tnmt[j,i]=-tnmt[i,j]}}} tnmt}
chck=function(1,gamz=4){ sumz=apply(tnmt,1,sum) max(sumz)==gamz& sum(sumz==2)>2& min(sumz)>-gamz}

I found that 8 teams were not producing an acceptable game out of 10⁶ tries. Here is a solution for 9 teams:

 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [1,] -1 -1 1 -1 [2,] -1 1 -1 -1 [3,] 1 1 1 -1 [4,] 1 1 1 -1 [5,] -1 -1 1 -1 [6,] -1 -1 -1 1 [7,] 1 -1 1 1 [8,] 1 -1 -1 -1 [9,] 1 1 1 1

where team 9 wins all four games, 7,4 and 3, win three games, and the other 4 teams win one game. Which makes sense since this is a zero sum game, with a value of 10 over the four top teams and 2(N-4)=10 if no team has two wins (adding an even number of such teams does not change the value of the game).

Favorite

Leave a Comment