Archive for competition

in the street for a year

Posted in Mountains, pictures, Travel, University life with tags , , , , , , , , , , on April 13, 2018 by xi'an

Just like about every year, I sent two of my pictures to the photography competition of Paris Dauphine, with not much consideration for the theme “green the future”, and was hence quite surprised to get selected this time! (Almost as much surprised as last year when an almost perfect copy of my picture of the Alcazar Baths of Lady María de Padilla got selected!) As I could travel back from Oxford to attend the opening ceremony, I went there last night, wondering at which of my pictures had been selected (Lac Pavin, Auvergne versus the Quinrang, Skye)…


And so this picture will remain exposed in the street, boulevard Lannes, for the incoming year, meaning I will cross it each time I bike to the university! The 22 other pictures were more in tune with the theme of a green future, like the winning one of a fast moving métro carriage at the station Chemin Vert. Or this simple blade of grass growing from ashes…

 
And thus the winner is… Continue reading

Le Monde puzzle [#1044]

Posted in Books, Kids with tags , , , , , , on March 12, 2018 by xi'an

A dynamic programming Le Monde mathematical puzzle:

Bob and Alice are playing a game where Alice fills a one-litre bottle from a water fountain, and empties it between four buckets. Bob then empties two of the four buckets. Alice then fills again her bottle and empties it again in the buckets. Alice wins if she manages to fill one bucket after a finite number of steps. What is the maximum capacity of a bucket for Alice to find a winning strategy?

The question sounded too complex to solve by an R code so I somewhat simplified it by deciding that Alice could not allocate any portion of the litre to a bucket but instead only 0,¼,⅓,½,⅔,¾,1. And then looked at a finite horizon to see how much she could fill a bucket when Bob was trying to minimise this amount: a crude R code just took too long for an horizon of 6 steps and hence I tried to reduce the number of calls to my recursive function

solfrak=c(0,.25,.333,.5,.667,.75,1)
petifil=function(buck=rep(0,4),hor=3){
#eliminate duplicates
 albukz=NULL
 for (a in solfrak)
 for (b in solfrak[!(solfrak+a>1)])
 for (c in solfrak[!(solfrak+a+b>1)]){
   if (a+b+c<=1){ albukz=rbind(albukz,
      c(a,b,c,1-a-b-c))}} 
   albukz=t(apply(buck+albukz,1,sort)) 
   albukz=albukz[!duplicated(albukz),] 
   if (is.matrix(albukz)){ 
    bezt=max(apply(albukz,1,petimpty,hor=hor-1)) 
    }else{ 
      bezt=petimpty(albukz,hor-1)} 
    return(bezt)} 

petimpty=function(buck,hor){ 
  if (hor>1){
    albukz=NULL
     for (i in 1:3)
     for (j in (i+1):4)
      albukz=rbind(albukz,c(buck[-c(i,j)],0,0))
     albukz=t(apply(albukz,1,sort))
     albukz=albukz[!duplicated(albukz),]
     if (is.matrix(albukz)){
       bezt=min(apply(albukz,1,petifil,hor))}else{
        bezt=petifil(albukz,hor)}
     }else{
      bezt=sort(buck)[2]+1}
   return(bezt)}

which led to a most surprising outcome:

> petifil(hor=2)
[1] 1.333
> petifil(hor=3)
[1] 1.5
> petifil(hor=4)
[1] 1.5
> petifil(hor=5)
[1] 1.5

that is no feasible strategy to beat the value 1.5 liters. Which actually stands way below two liters, the maximum content of the bucket produced in the solution!

The Norse Farce [design #2]

Posted in Statistics with tags , , , on December 7, 2017 by xi'an

In reply to my call for designs along the Norse farce pun, here is a nice proposal from Thomas, which stands so far as a strong competitor for the best design! I welcome more submissions: remember, a free mug to the winner!!!

Le Monde [last] puzzle [#1026]

Posted in Books, Kids, R with tags , , , , , on November 2, 2017 by xi'an

The last and final Le Monde puzzle is a bit of a disappointment, to wit:

A 4×4 table is filled with positive and different integers. A 3×3 table is then deduced by adding four adjacent [i.e. sharing a common corner] entries of the original table. Similarly with a 2×2 table, summing up to a unique integer. What is the minimal value of this integer? And by how much does it increase if all 29 integers in the tables are different?

For the first question, the resulting integer writes down as the sum of the corner values, plus 3 times the sum of the side values, plus 9 times the sum of the 4 inner values [of the 4×4 table]. Hence, minimising the overall sum means taking the inner values as 1,2,3,4, the side values as 5,…,12, and the corner values as 13,…,16. Resulting in a total sum of 352. As checked in this computer code in APL by Jean-Louis:

This configuration does not produce 29 distinct values, but moving one value higher in one corner does: I experimented with different upper bounds on the numbers and 17 always provided with the smallest overall sum, 365.

firz=matrix(0,3,3)#second level
thirz=matrix(0,2,2)#third level
for (t in 1:1e8){
flor=matrix(sample(1:17,16),4,4)
for (i in 1:3) for (j in 1:3)
firz[i,j]=sum(flor[i:(i+1),j:(j+1)])
for (i in 1:2) for (j in 1:2)
thirz[i,j]=sum(firz[i:(i+1),j:(j+1)])
#last
if (length(unique(c(flor,firz,thirz)))==29)
solz=min(solz,sum(thirz))}

and a further simulated annealing attempt did not get me anywhere close to this solution.

Le Monde puzzle [poll]

Posted in Books, Kids with tags , , on November 1, 2017 by xi'an

As the 25 Le Monde mathematical puzzles have now been delivered (plus the extraneous #1021), the journal is asking the players for their favourites, in order to separate ex-aequos. For readers who followed the entire sequence since puzzle #1001, what are your favourite four puzzles? (No more than four votes!)

Le Monde puzzle [open problem]

Posted in Books, Kids with tags , , , , , on October 23, 2017 by xi'an

What should have been the last puzzle in Le Monde competition turned out to be an anticlimactic fizzle on how many yes-no questions are needed to identify an integer between 1 and 1025=2¹⁰+1 and an extension to replies possibly being lies

What is much more exciting is that voting puzzle #1021 got cancelled because the authors of this puzzle thought the cascading majority rule would produce the optimal solution and it does not! (As exhibited by my R code.) So here is an open problem to ponder about! (And another puzzle in the pipeline to complete the competition.)

Le Monde puzzle [#1024]

Posted in Books, Kids with tags , , , , , , , on October 10, 2017 by xi'an

The penultimate and appropriately somewhat Monty Hallesque Le Monde mathematical puzzle of the competition!

A dresser with 5×5 drawers contains a single object in one of the 25 drawers. A player opens a drawer at random and, after each choice, the object moves at random to a drawer adjacent to its current location and the drawer chosen by the player remains open. What is the maximum number of drawers one need to open to find the object?

In a dresser with 9 drawers in a line, containing again a single object, the player opens drawers one at a time, after which the open drawer is closed and the object moves to one of the drawers adjacent to its current location. What is the maximum number of drawers one need to open to find the object?

For the first question, setting a pattern of exploration and, given this pattern, simulating a random walk trying to avoid the said pattern as long as possible is feasible, returning a maximum number of steps over many random walks [and hence a lower bound on the true maximum]. As in the following code

sefavyd=function(pater=seq(1,49,2)%%25+1){
  fild=matrix(0,5,5)
  m=pater[1];i=fild[m]=1
  t=sample((1:25)[-m],1)
  nomove=FALSE
  while (!nomove){
   i=i+1
   m=pater[i];fild[m]=1
   if (t==m){ nomove=TRUE}else{
   muv=NULL
   if ((t-1)%%5>0) muv=c(muv,t-1)
   if (t%%5>0) muv=c(muv,t+1)
   if ((t-1)%/%5>0) muv=c(muv,t-5)
   if (t%/%5<4) muv=c(muv,t+5)
   muv=muv[fild[muv]==0]
   nomove=(length(muv)==0)
   if (!nomove) t=sample(rep(muv,2),1)}
  }
  return(i)}

But a direct reasoning starts from the observation that, while two adjacent drawers are not opened, a random walk can, with non-zero probability, switch indefinitely between both drawers. Hence, a sure recovery of the object requires opening one drawer out of two. The minimal number of drawers to open on a 5×5 dresser is 2+3+2+3+2=12. Since in 12 steps, those drawers are all open, spotting the object may require up to 13 steps.

For the second case, unless I [again!] misread the question, whatever pattern one picks for the exploration, there is always a non-zero probability to avoid discovery after an arbitrary number of steps. The [wrong!] answer is thus infinity. To cross-check this reasoning, I wrote the following R code that mimics a random pattern of exploration, associated by an opportunistic random walk that avoids discovery whenever possible (even with very low probability) bu pushing the object towards the centre,

drawl=function(){
  i=1;t=5;nomove=FALSE
  m=sample((1:9)[-t],1)
  while (!nomove){
    nextm=sample((1:9),1)
    muv=c(t-1,t+1)
    muv=muv[(muv>0)&(muv<10)&(muv!=nextm)] 
    nomove=(length(muv)==0)||(i>1e6)
    if (!nomove) t=sample(rep(muv,2),1,
              prob=1/(5.5-rep(muv,2))^4)
    i=i+1}
  return(i)}

which returns unlimited values on repeated runs. However, I was wrong and the R code unable to dismiss my a priori!, as later discussions with Robin and Julien at Paris-Dauphine exhibited ways of terminating the random walk in 18, then 15, then 14 steps! The idea was to push the target to one of the endpoints because it would then have no option but turning back: an opening pattern like 2, 3, 4, 5, 6, 7, 8, 8 would take care of a hidden object starting in an even drawer, while the following 7, 6, 5, 4, 3, 2 openings would terminate any random path starting from an odd drawer. To double check:

grawl=function(){
  len=0;muvz=c(3:8,8:1)
  for (t in 1:9){
    i=1;m=muvz[i];nomove=(t==m)
    while (!nomove){
     i=i+1;m=muvz[i];muv=c(t-1,t+1)
     muv=muv[(muv>0)&(muv<10)&(muv!=m)]
     nomove=(length(muv)==0)
     if (!nomove)
      t=sample(rep(muv,2),1)}
    len=max(len,i)}
  return(len)}

produces the value 14.