Archive for tournament

Le Monde puzzle [#1154]

Posted in Statistics with tags , , , , , , on August 25, 2020 by xi'an

The weekly puzzle from Le Monde is another Sudoku challenge:

An n by n grid contains all numbers from 1 till n². Is it possible for fill the grid so that every row and every column has an integer average, for n=5, 7 9?

By sheer random search

`?`=rowSums; `+`=sample 
o=function(n){
x=matrix(+(n^2),n) 
while(any(c(?x,?t(x))%%n))x=x/x*+x 
x}

I found solutions for n=3,4,5, quite easily,

     [,1] [,2] [,3] [,4] [,5]
[1,]   20   15   14   13    3
[2,]   21    4   25    6    9
[3,]    2    1   23   18   11
[4,]   17   12   22   24    5
[5,]   10    8   16   19    7

correction, for n=6 as well

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    4   12   11   23    8   32
[2,]   17   15   14   33    5   30
[3,]   35   28   27    7   13   22
[4,]   31    1    6    2   21   29
[5,]   25   36   20   34   16   19
[6,]   26   10   24    3    9   18

but larger values of n require a less frontal attack… Simulated annealing maybe.

Le Monde puzzle [#1152]

Posted in Kids, R with tags , , , , , , on July 20, 2020 by xi'an

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).