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

## splitting a field by annealing

Posted in Kids, pictures, R, Statistics with tags , , , , , , , , on October 18, 2017 by xi'an

A recent riddle [from The Riddle] that I pondered about during a [long!] drive to Luxembourg last weekend was about splitting a square field into three lots of identical surface for a minimal length of separating wire… While this led me to conclude that the best solution was a T like separation, I ran a simulated annealing R code on my train trip to AutransValence, seemingly in agreement with this conclusion.I discretised the square into n² units and explored configurations by switching two units with different colours, according to a simulated annealing pattern (although unable to impose connectivity on the three regions!):

partz=matrix(1,n,n)
partz[,1:(n/3)]=2;partz[((n/2)+1):n,((n/3)+1):n]=3
#counting adjacent units of same colour
nood=hood=matrix(4,n,n)
for (v in 1:n2) hood[v]=bourz(v,partz)
minz=el=sum(4-hood)
for (t in 1:T){
colz=sample(1:3,2) #picks colours
a=sample((1:n2)[(partz==colz[1])&(hood<4)],1)
b=sample((1:n2)[(partz==colz[2])&(hood<4)],1)
partt=partz;partt[b]=colz[1];partt[a]=colz[2]
#collection of squares impacted by switch
nood=hood
voiz=unique(c(a,a-1,a+1,a+n,a-n,b-1,b,b+1,b+n,b-n))
voiz=voiz[(voiz>0)&(voiz<n2)]
for (v in voiz) nood[v]=bourz(v,partt)
if (nood[a]*nood[b]>0){
difz=sum(nood)-sum(hood)
if (log(runif(1))<difz^3/(n^3)*(1+log(10*rep*t)^3)){
el=el-difz;partz=partt;hood=nood
if (el<minz){ minz=el;cool=partz}
}}}


(where bourz computes the number of neighbours), which produces completely random patterns at high temperatures (low t) and which returns to the T configuration (more or less):if not always, as shown below:Once the (a?) solution was posted on The Riddler, it appeared that one triangular (Y) version proved better than the T one [if not started from corners], with a gain of 3% and that a curved separation was even better with an extra gain less than 1% [solution that I find quite surprising as straight lines should improve upon curved ones…]

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

## Le Monde puzzle [#1022 & #1023]

Posted in Books, Kids with tags , , , , , on September 29, 2017 by xi'an

Another Le Monde mathematical puzzle where I could not find a solution by R programming (albeit one by cissors and papers was readily available!):

An NT is a T whose head () is made of 3 50×50 squares and whose body (|) is made of N 50×50 squares.  What is the smallest possible side of a square containing four non-intersecting NT’s when N=1,2,4? And what is the smallest value of N such that this square also contains a fifth NT?

The questions could have been solved by brute force simulation (or a knapsack algorithm?!) but I could not fathom an efficient way to code throwing T’s at random over an MxM grid.So instead I took scissors and paper and tried to fit four 1T, 2T, and 4T into the smallest squares, ending up with 4×4, 5×5, and 7×7 squares. Interestingly, four 5T also fit in a 7×7 square. And a 9×9 square accommodates the extra 7T. Compared with the  “impossible” puzzle of last week, this is pretty anticlimactic..! (Actually, once the solutions were published, I realised the square containing the T’s did not have to be with integer side. Which means the smallest square for 3Ts was incorporating the glued T’s sideway. Fortunately, this did not impact the answer for the 7T’s!)

Going back to this “impossible” puzzle, the posted solution is somewhat… puzzling in that the resolution posits that the majority rule is the optimal allocation, when I am not sure it is [optimal]. Just because, when rerunning the same R code, I found instances when the minimal acceptable number of councillors was lower than the one returned by the majority rule.

And since this post get pushed down in the queue, here is as a bonus the equally anticlimactic puzzle #1023,

Find (a) a multiplication of two three-prime-digit numbers such that all digits everywhere in the long multiplication are prime and all three intermediary products have four prime digits, while the final result has six prime digits, and (b) a multiplication of two three-digit numbers such that the digits of the first one are odd (o), the digits of the second are even (e), the three intermediary products are all of the form eoe, and the final product is of the form eoeo. [The website has two pictures to help if this description is too unclear!]

This is indeed straightforward to code with one solution to (a) and two to (b) since the number of cases to examine is quite limited.

## Le Monde puzzle [#1021]

Posted in Books, Kids, R with tags , , , , , on September 17, 2017 by xi'an

A puzzling Le Monde mathematical puzzle for which I could find no answer in the allotted time!:

A most democratic electoral system allows every voter to have at least one representative by having each of the N voters picking exactly m candidates among the M running candidates and setting the size n of the representative council towards this goal, prior to the votes. If there are M=25 candidates, m=10 choices made by the voters, and n=10 representatives, what is the maximal possible value of N? And if N=55,555 and M=33, what is the minimum value of n for which m=n is always possible?

I tried a brute force approach by simulating votes from N voters at random and attempting to find the minimal number of councillors for this vote, which only provides an upper bound of the minimum [for one vote], and a lower bound in the end [over all votes]. Something like

for (i in 1:N) votz[i,]=sample(1:M,n)
#exploration by majority
remz=1:N;conz=NULL
while (length(remz)>0){
seatz=order(-hist(votz[remz,],
breaks=(0:M)+0.5,plot=FALSE)\$density)[1]
conz=c(conz,seatz);nuremz=NULL
for (v in remz)
if (!(seatz%in%votz[v,])) nuremz=c(nuremz,v)
remz=nuremz}
solz=length(conz)
#exploration at random
kandz=matrix(0,N,M)
for (i in 1:N) kandz[i,votz[i,]]=1
for (t in 1:1e3){
#random choice of councillors
zz=sample(c(0,1),M,rep=TRUE)
while (min(kandz%*%zz)!=1)
zz=sample(c(0,1),M,rep=TRUE)
solz=min(solz,sum(zz))
#random choice of remaining councillor per voter
remz=1:N;conz=NULL
while (length(remz)>0){
seatz=sample(votz[remz[1],],1)
conz=c(conz,seatz);nuremz=NULL
for (i in remz)
if (!(seatz%in%votz[i,])) nuremz=c(nuremz,i)
remz=nuremz}
solz=min(solz,length(conz))}
maxz=max(solz,maxz)}


which leads to a value near N=4050 for the first question, with 0% confidence… Obviously, the problem can be rephrased as a binary integer linear programming problem of the form

$n= \max_A \min_{c;\,\min Ac=1}\mathbf{1}^\text{T}c$

where A is the NxM matrix of votes and c is the vector of selected councillors. But I do not see a quick way to fix it!

## Le Monde puzzle [#1020]

Posted in Books, Kids, R with tags , , , on September 15, 2017 by xi'an

A collection of liars in this Le Monde mathematical puzzle:

1. A circle of 16 liars and truth-tellers is such that everyone states that their immediate neighbours are both liars. How many liars can there be?
2. A circle of 12 liars and truth-tellers is such that everyone state that their immediate neighbours are one liar plus one truth-teller. How many liars can there be?
3.  A circle of 8 liars and truth-tellers is such that four state that their immediate neighbours are one liar plus one truth-teller and four state that their immediate neighbours are both liars . How many liars can there be?

These questions can easily be solved by brute force simulation. For the first setting, using 1 to code truth-tellers and -1 liars, I simulate acceptable configurations as

tabz=rep(0,16)
tabz[1]=1 #at least one
tabz[2]=tabz[16]=-1
for (i in 3:15){
if (tabz[i-1]==1){
tabz[i]=-1}else{
if (tabz[i+1]==-1){
tabz[i]=1}else{
if (tabz[i+1]==1){
tabz[i]=-1}else{
if (tabz[i-2]==-1){
tabz[i]=1}else{
tabz[i]=sample(c(-1,1),1)
}}}}}


which produces 8, 9, and 10 as possible (and obvious) values.

The second puzzle is associated with the similar R code

tabz=sample(c(-1,1),12,rep=TRUE)
rong=FALSE
while (!rong){
for (i in sample(12)){
if (tabz[i-1+12*(i==1)]*tabz[i%%12+1]==-1){
tabz[i]=1}else{
tabz[i]=sample(c(-1,1),1)}
}
rong=TRUE
for (i in (1:12)[tabz==1])
rong=rong&(tabz[i-1+12*(i==1)]*tabz[i%%12+1]==-1)
if (rong){
for (i in (1:12)[tabz==-1])
rong=rong&(tabz[i-1+12*(i==1)]*tabz[i%%12+1]!=-1)
}}


with numbers of liars (-1) either 12 (obvious) or 4.

The final puzzle is more puzzling in that figuring out the validating function (is an allocation correct?) took me a while, the ride back home plus some. I ended up with the following code that samples liars (-1) and thruth-seekers (1) at random, plus forces wrong and right answers (in 0,1,2) on these, and check for the number of answers of both types:

rong=FALSE
while (!rong){
tabz=sample(c(-1,1),8,rep=TRUE) #truth
tabz[1]=1;tabz[sample(2:8,1)]=-1
tt=(1:8)[tabz==1];lr=(1:8)[tabz==-1]
statz=rep(0,8) #stmt
statz[tt]=(tabz[tt-1+8*(tt==1)]*tabz[tt%%8+1]==-1)+
2*(tabz[tt-1+8*(tt==1)]+tabz[tt%%8+1]==-2)
statz[lr]=2*(tabz[lr-1+8*(lr==1)]*tabz[lr%%8+1]==-1)+
(tabz[lr-1+8*(lr==1)]+tabz[lr%%8+1]==-1)+
sample(c(1,2),8,rep=TRUE)[lr]*
(tabz[lr-1+8*(lr==1)]+tabz[lr%%8+1]==1)
rong=(sum(statz==1)==4)&(sum(statz==2)==4)}


with solutions 3, 4, 5 and 6.

## Le Monde puzzle [#1019]

Posted in Books, Kids with tags , , , , , , on September 7, 2017 by xi'an

A gamey (and verbose) Le Monde mathematical puzzle:

A two-player game involves n+2 cards in a row, blue on one side and red on the other. Each player can pick any blue card among the n first ones and flip it plus both following ones. The game stops when no blue card is left to turn. The gain for the last player turning cards is 20-t, where t is the number of times cards were flipped, with gain t for its opponent. Both players aim at maximising their gain.

1. When n=4 and all cards are blue, can the first player win? If not, what is the best score for this player?

2. Among all 16 configurations at start, how many lead to the first player to win?

3. When n=10 and all cards are blue, how many cards are flipped an odd number of times for the winning configuration?

The first two questions can easily be processed by an R code like the following recursive function:

liplop <- function(x,n,i){
if (max(x[1:n])==0){
return(i)
}else{
sol=NULL
for (j in (1:n)[x[1:n]==1]){
y=x;y[j:(j+2)]=1-y[j:(j+2)]
sol=c(sol,20-liplop(y,n,i+1))}
return(max(sol))}}


Returning

> liplop(rep(1,6),4,0)
[1] 6


Meaning the first player cannot win, by running at most six rounds. Calling the same function for all 4⁴=16 possible configurations leads to 8 winning ones:

[1] 0 0 0 1
[1] 0 0 1 1
[1] 0 1 0 1
[1] 0 1 1 1
[1] 1 0 0 0
[1] 1 0 1 0
[1] 1 1 0 0
[1] 1 1 1 0


Solving the same problem with n=10 is not feasible with this function. (Even n=6 seems out of reach!)