Archive for Gare d’Austerlitz

Le Monde puzzle [#1159]

Posted in Books, Kids, R with tags , , , , , , on October 6, 2020 by xi'an

The weekly puzzle from Le Monde is quite similar to #1157:

Is it possible to break the ten first integers, 1,…,10, into two groups such that the sum over the first group is equal to the product over the second? Is it possible that the second group is of cardinal 4? of cardinal 3?

An exhaustive R search returns 3 solutions by

library(R.utils)
bitz<-function(i)
  c(rev(as.binary(i)),rep(0,10))[d<-1:10]
for (i in 1:2^10)
  if (sum(d[!!bitz(i)])==prod(b<-d[!bitz(i)])) print(b)
[1]  1  4 10 #40
[1] 6 7 #42
[1] 1 2 3 7 #42

which brings a positive reply to the question. Moving from N=10 to N=19 produces similar results

[1]  1  9 18 #162
[1]  2  6 14 #168
[1]  1  3  4 14 #168
[1]  1  2  7 12 #168

with this interesting pattern of only two acceptable products, but I am obviously unable to run the same code for N=49, which is the subsidiary question to the puzzle. Turning to a more conceptual (!) approach, over a long insomnia bout (!!) and a subsequent run, I realised that if there are three terms, x¹,x² and x³, in the second group, they need satisfy

x¹x²x³+x¹+x²+x³=½N(N+1)

and if in addition one of them is equal to 1, x¹ say, this equation simplifies into

(x²+1)(x³+1)=½N(N+1)

which always leads to a solution, as e.g. for N=49,

x¹=1, x²=24 and x³=48.

A brute-force search also led to a four term solution in that case

x¹=1, x²=7, x³=10 and x⁴=17.

Le Monde puzzle [#1157]

Posted in Books, Kids, R with tags , , , , , , on October 1, 2020 by xi'an

The weekly puzzle from Le Monde is an empty (?) challenge:

Kimmernaq and Aputsiaq play a game where Kimmernaq picks ten different integers between 1 and 100, and Aputsiaq must find a partition of these integers into two groups with identical sums. Who is winning?

Indeed, if the sums are equal, then the sum of their sums is even, meaning the sum of the ten integers is even. Any choice of these integers such that the sum is odd is a sure win for Kimmernaq. End of the lame game (if I understood its wording correctly!). If some integers can be left out of the groups, then both solutions seem possible: calling the R code

P=1;M=1e3
while (P<M){
a=sample(1:M,10);P=Q=0
while((P<M)&(!Q)){
t=sample(1:7,1)     #size of subset
o=1         #total sum must be even
while(!!(s<-sum(o))%%2)o=sample(a,10-t)
Q=max(2*cumsum(b<-sample(o))==s)
P=P+1}}

I found no solution (i.e. exiting the outer while loop) for M not too large…  So Aputsiaq is apparently winning. Le Monde solution considers the 2¹⁰-1=1023 possible sums made out of 10 integers, which cannot exceed 955, hence some of these sums must be equal (and the same applies when removing the common terms from both sums!). When considering the second half of the question

What if Kimmernaq picks 6 distinct integers between 1 and 40, and Aputsiaq must find a partition of these integers into two groups with identical sums. Who is winning?

recycling the above R code produced subsets systematically hitting the upper bound M, for much larger values. So Kimmernaq should have a mean to pick 6 integers such that any subgroup cannot be broken into two parts with identical sums. One of the outcomes being

 
> a
[1] 36 38 30 18  1 22

one can check that all the possible sums differ:

aa=a
for(i in 2:5){
 bb=NULL
 while(length(bb)<choose(6,i))bb=unique(c(bb,sum(sample(a,i))))
 aa=c(aa,bb)}
unique(aa)

and the outcome is indeed of length 2⁶-2=62!

As an aside, a strange [to me at least] R “mistake” was that when recycling the variable F in a code-golfing spirit, since it is equal to zero by default, rather than defining a new Q:

while((P<M)&(!F)){
...
F=max(2*cumsum(b<-sample(o))==s)
P=P+1}

the counter P was not getting updated!

Le Monde puzzle [#1155]

Posted in Books, Kids, R with tags , , , , , , , on September 26, 2020 by xi'an

The weekly puzzle from Le Monde is another Sudoku challenge:

Anahera and Wiremu play a game for T rounds. They successively pick a digit between 1 and 3, never repeating the previous one, and sum these digits. The last to play wins if the sum is a multiple of 3. Who is the winner for an optimal strategy?

By a simple dynamic programming of the optimal strategy at each step

N=3
A=matrix(-1,20,N)
A[1,1:N]=1:N
for (T in 2:20)
for (i in 1:N) A[T,i]=i+ifelse(!T%%2, #parity check
max((i+A[T-1,-i])%%3), #avoid zero
min((i+A[T-1,-i])%%3)) #seek zero

the first to play can always win the game. Not fun!

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