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

## Le Monde puzzle [#1149]

Posted in Books, Kids, pictures, R with tags , , , , , , on July 1, 2020 by xi'an The weekly puzzle from Le Monde is a leaking variant on an old puzzle:

Three buckets have capacities of 8, 5 and 3 litres, respectively. At the start of the game, the 8 litre bucket is full and both others are empty. Aiming at reaching exactly 4 litres in one bucket, water is transferred between buckets. However, a fraction 1/k is lost with each transfer. If k=9, it is possible to reach 4 litres in three operations? If k=7, is it at all possible to reach 4 litres?

By sheer random search

```k=1/5
z=c(8,5,3)
m<-function(s){
i=sample(1:3,2)
s[i]=s[i]+ifelse(
rep((a<-z[i]-s[i])<(b<-s[i])*(1-k),2),
a*c(1,-1-k),b*c(1-k,-1))
s}```

I found that most fractions allow to reach 4 litres starting with k=2. (And am unsure the missing ones, like 18 or 21 are not due to a lack of luck… In particular, for k=9, the shortest path is

``` 8.000    0 0
2.375    5 0
0.000    5 2.11
0.000    4 3
```

## Le Monde puzzle [#1147]

Posted in Books, Kids, R with tags , , , , , , on June 10, 2020 by xi'an The weekly puzzle from Le Monde is not much, again:

A number A is such that (1) the difference between two digits is never 1 (2) two digits are equal to 2 (3) it only involves 3 different digits (4) it is a multiple of 4 (5)  the sum of two of the digits is 5 (6) the product of the digits is not a multiple of 6 (7) the digits are between 0 and 6. What are the values of A with no digit equal to 0? What is the smallest A containing a zero?

as brute force produced 2052 as the smallest number with a zero. But I could not find numbers without a zero which seems indeed impossible since (1) plus (2) excludes 1 and 3, then (5) implies 0 and 5 are the other digits. Did I misunderstood the wording?!

A digit 1<x<7 is part of the digits of A if and only if (x) is true.

Which of course reduces the number of constraints. Using the checking function (and possibly calling xor for the first time ever!)

```rule<-function(A){
xor(!1%in%outer(A,A,'-'),!1%in%A)&
xor(sum(A==2)==2,!2%in%A)&
xor(length(unique(A))==3,!3%in%A)&
xor(!dig2num(A)%%4,!4%in%A)&
xor(5%in%outer(A,A,'+'),!5%in%A)&
xor(!!prod(A)%%6,!6%in%A)}
```

the first realisations of A are

```     304   340   344  2452  2524  3004  3040  3044  3304  3340  3344
  3400  3404  3440  3444  4252  4300  4304  4340  4344  5224 20452
 20524 22335 22353 22355 22504 22533 22535 22540 22553 23235 23253
 23255 23325 23523 23525 24052 24520 25024 25204 25233 25235 25240
 25253 25323 25325 25420 25523 30004 30040 30044 30304 30340 30344
 30400 30404 30440 30444 32235 32253 32255 32325 32523 32525 33004
 33040 33044 33225 33304 33340 33400 33404 33440 33522 34000 34004
 34040 34044 34300 34304 34340 34400 34404 34440 35223 35225 35322
 35522 40252 40300 40304 40340 40344 42052 42520 43000 43004 43040
 43044 43300 43304 43340 43400 43404 43440 44300 44304 44340 45220
 50224 52024 52204 52233 52235 52240 52253 52323 52325 52420 52523
 53223 53225 53322 53522 54220 55223 55322```

with the first value containing 0 being 304. And no 6 ever appearing in the numbers!

## Le Monde puzzle [#1146]

Posted in Books, Kids, R with tags , , , , , , , , on June 5, 2020 by xi'an The weekly puzzle from Le Monde is once more disappointing.

Everyday of the month, take 0, 1 or 2 units. If one unit taken past day, next day none can be taken. If two units taken two day ago, none can be taken the current day. What is the strategy maximising the number of units  for February? March? April? Generalise to 0,..,3 units taken each day with 0 compulsory three days after taking 3 units.

as taking 2-1-0 (or 3-2-1-0) sounds like the optimal strategy. Except at the final step when 2, 2-2, 2-2-0, and 1-0-2-2 are best. But then why would one distinguish between the three months..?! Because the outcome differ, as 30, 32, and 33, resp. (or 45, 48 and 51). With an average increase of 1 in the first case and 1.5 in the second.

Another puzzle took too much of my time, namely a code golf challenge to devise a code taking as input a matrix of moves over an n x x grid and returning as input the number of nodes and transient tributaries for each loop (or irreducible set) of the moves. Which I solved by running Markov chains from each starting point long enough to reach stationarity. Entering the moves as

```n=3;M=matrix(sample(1:4,n^2,rep=T),n)
```

and returning the result via 390 bytes

```j=cbind;l=sum;a=apply
m=l(!!M);n=m^.5
g=function(A,r=M[A])A+c((r<2)*(1-n*(A[,1]==n))-(r==2)*(1-n*(A[,1]<2)),
(r==3)*(1-n*(A[,2]==n))-(r>3)*(1-n*(A[,2]<2)))
I=c()
for(i in d<-1:n)I=rbind(I,j(i*d/d,d))
for(t in b<-1:m)I=g(I)
p=function(i)i[,1]+n*i[,2]-n-1
K=matrix(0,m,m)
for(t in b)K[b+m*p(I<-g(I))]=1
s=o=a(u<-unique(K),1,l)
for(k in 1:l(!!s))s[k]=l(!a(!!sweep(K,2,u[k,],'-'),1,l))
j(o,s-o)
```

which could be much shorter if only matrices could be indexed from 0 as in C.

## Le Monde puzzle [#1144]

Posted in Books, Kids with tags , , , , , , on May 19, 2020 by xi'an The weekly puzzle from Le Monde is again using 2020 but not R!

Two teams involve a prime total number m of participants, with each player getting between 0 and 100 points. The total score for both teams is 2020, with team B less than team A on average. A single transfer from A to B increases the average scores for both A and B by 1/2. What is the difference of the averages? The transfer(ed) player, Camélia, had 5 points less  than the average score for A. What was the score of Camélia?

but I could not find a brute force solution and ended up finding that 2×2020=2x2x5x101 is a multiple of m, which leaves only

m=101

as the possible number of players. Which almost immediately leads to a difference of m/2 between the average scores. And then almost as immediately to Camélia’s score being 60. If one really needed an R function

```k=function(a){((C<-71-a)>0)&(C+(a-1)/2<102)
&(C-((102-a)/2)>0)&(C+5==(C+(a-1)/2))}```

does return a=11 but this is 100% useless!