## Le Monde puzzle [#1087]

Posted in Books, Kids, R, Statistics with tags , , , , , on February 25, 2019 by xi'an

A board-like Le Monde mathematical puzzle in the digit category:

Given a (k,m) binary matrix, what is the maximum number S of entries with only one neighbour equal to one? Solve for k=m=2,…,13, and k=6,m=8.

For instance, for k=m=2, the matrix

$\begin{matrix} 0 &0\\ 1 &1\\ \end{matrix}$

is producing the maximal number 4. I first attempted a brute force random filling of these matrices with only a few steps of explorations and got the numbers 4,8,16,34,44,57,… for the first cases. Since I was convinced that the square k² of a number k previously exhibited to reach its maximum as S=k² was again perfect in this regard, I then tried another approach based on Gibbs sampling and annealing (what else?):

gibzit=function(k,m,A=1e2,N=1e2){
temp=1 #temperature
board=sole=matrix(sample(c(0,1),(k+2)*(m+2),rep=TRUE),k+2,m+2)
board[1,]=board[k+2,]=board[,1]=board[,m+2]=0 #boundaries
maxol=counter(board,k,m) #how many one-neighbours?
for (t in 1:A){#annealing
for (r in 1:N){#basic gibbs steps
for (i in 2:(k+1))
for (j in 2:(m+1)){
prop=board
prop[i,j]=1-board[i,j]
u=runif(1)
if (log(u/(1-u))<temp*(counter(prop,k,m)-val)){
board=prop;val=counter(prop,k,m)
if (val>maxol){
maxol=val;sole=board}}
}}
temp=temp*2}
return(sole[-c(1,k+2),-c(1,m+2)])}


which leads systematically to the optimal solution, namely a perfect square k² when k is even and a perfect but one k²-1 when k is odd. When k=6, m=8, all entries can afford one neighbour exactly,

> gibzbbgiz(6,8)
[1] 48
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    1    0    0    1    1    0    0    1
[2,]    1    0    0    0    0    0    0    1
[3,]    0    0    1    0    0    1    0    0
[4,]    0    0    1    0    0    1    0    0
[5,]    1    0    0    0    0    0    0    1
[6,]    1    0    0    1    1    0    0    1


but this does not seem feasible when k=6, m=7, which only achieves 40 entries with one single neighbour.

## Le Monde puzzle [#1075]

Posted in Books, Kids, R with tags , , , , , , , on November 22, 2018 by xi'an

A Le Monde mathematical puzzle from after the competition:

A sequence of five integers can only be modified by subtracting an integer N from two neighbours of an entry and adding 2N to the entry.  Given the configuration below, what is the minimal number of steps to reach non-negative entries everywhere? Is this feasible for any configuration?

As I quickly found a solution by hand in four steps, but missed the mathematical principle behind!, I was not very enthusiastic in trying a simulated annealing version by selecting the place to change inversely proportional to its value, but I eventually tried and also obtained the same solution:

      [,1] [,2] [,3] [,4] [,5]
-3    1    1    1    1
1   -1    1    1   -1
0    1    0    1   -1
-1    1    0    0    1
1    0    0    0    0


But (update!) Jean-Louis Fouley came up with one step less!

      [,1] [,2] [,3] [,4] [,5]
-3    1    1    1    1
3   -2    1    1   -2
2    0    0    1   -2
1    0    0    0    0


The second part of the question is more interesting, but again without a clear mathematical lead, I could only attempt a large number of configurations and check whether all admitted “solutions”. So far none failed.

## Le Monde puzzle [#1071]

Posted in Books, Kids with tags , , , , , , , , , , , on October 18, 2018 by xi'an

A “he said she said” Le Monde mathematical puzzle sixth competition problem that reminded me of the “Singapore birthday problem” (nothing to do with the original birthday problem!):

Arwen and Brandwein are privately and respectively given the day and month of Caradoc’s birthday [in the Gregorian calendar] with the information that the month number is at least the day number. Arwen starts by stating she knows Brandwein cannot deduce the birthday, followed by Brandwein who says the same about Arwen. If this “she says he says” goes on for the largest possible number of steps before Arwen says she knows, when is Caradoc’s birthday? Arwen and Brandwein are later given two numbers corresponding to Deirdre’s birthday with no indication of which one is the day and which one is the month. They know both numbers end up with the same digit and that the month number is strictly less than the day number. Arwen states she does not know the date and she knows Brandwein cannot know either. Then Brandwein says he indeed does not the date but he knows whether he got the day or the month. This prompts Arwen to conclude she knows, then Brandwein to do the same. When is Deirdre’s birthday?

Since this was a fairly easy puzzle (and since I had spent too much time debugging the previous R code!), I did not try coding this one but instead drew the possibilities and remove the impossibilities on a blackboard. The first question is quite simple actually since the day numbers stand between 1 and 12 and that each “I cannot know” excludes one of the remaining endpoints, removing first excludes 1 from both lists, then 12, then 2, then …. 8, ending up with 7. And 07/07 as Caradoc’s birthday. The second case sees 13,…,20,23,…,30 eliminated from Arwen’s numbers, then 3,…,10 as well, which eliminates the same numbers from Brandwein’s possibilities. That he knows whether it is a month or a day leaves only 1,2,21,22,31 as possible numbers. Then Arwen’s certainty reduces her numbers to be 2, 21, 22, or 31, and since Brandwein is also sure, the only possible cases are (2,22) and (22,2). Meaning Deirdre’s birthday is on 22/02. I dunno if this symmetry was to be expected! (And I cannot fathom why this puzzle is awarded so many points, when compared with the others.)

## Le Monde puzzle [#1068]

Posted in Books, Kids, R with tags , , , , , , on October 3, 2018 by xi'an

A purely (?) algorithmic Le Monde mathematical puzzle

For the table below, what is the minimal number of steps required to reach equal entries when each step consists in adding ones to three entries sitting in a L, such as (7,11,12) or (5,6,10)? Same question for the inner table of four in yellow.

For the inner table, this is straightforward as there are four possible L’s, three equations like 6+n⁶=7+n⁷,  and two degrees of freedom leading to a unique entry of N=13 (impossible!)  or 16 (feasible). Hence adding 10 L’s. For the entire table, summing up all entries after completion leads to 16N, which is also equal to 1+3+3+…+16+M, where M is the number of added L’s, itself equal to 138+3O, if O denotes the number of ones added. Hence M can only take the values 18, 21, … It took me quite a while to R code an approach to complete the table into 16 18’s, as my versions of simulated annealing did not seem to converge. In the end, I used a simplified version where the table was completed by multinomial draws, like a M(17;3⁻¹,3⁻¹,3⁻¹) for the upper left corner, corresponding to random draws of one of the 36 available L’s, which should be used 50 times in total, and then augmented or reduced of one L depending on the value at a randomly selected entry. Leading to the result

> aneal(grid=c(1,3,3:13,15,15,16),maxT=1e5)
[1] 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18


## Le Monde puzzle [#1068]

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

And here is the third Le Monde mathematical puzzle  open for competition:

Consider for this puzzle only integers with no zero digits. Among these an integer x=a¹a²a³… is refined if it is a multiple of its scion, the integer defined as x without the first digit, y=a²a³…. Find the largest refined integer x such the sequence of the successive scions of x with more than one digit is entirely refined. An integer x=a¹a²a… is distilled if it is a multiple of its grand-scion, the integer defined as x without the first two digits, z=a³… Find the largest distilled integer x such the sequence of the successive scions of x with more than two digits is entirely distilled.

Another puzzle amenable to a R resolution by low-tech exploration of possible integers, first by finding refined integers, with  no solution between 10⁶ and 10⁸ [meaning there is no refined integer larger than 10⁶] and then checking which refined integers have refined descendants, e.g.,

raf=NULL
for (x in (1e1+1):(1e6-1)){
y=x%%(10^trunc(log(x,10)))
if (y>0){
if (x%%y==0)
raf=c(raf,x)}}


that returns 95 refined integers. And then

for (i in length(raf):1){
gason=raf[i]
keep=(gason%in%raf)
while (keep&(gason>100)){
gason=gason%%(10^trunc(log(gason,10)))
keep=keep&(gason%in%raf)}
if (keep) break()}}


that returns 95,625 as the largest refined integer with the right descendance. Rather than finding all refined integers at once, going one digit at a time and checking that some solutions have proper descendants is actually faster.

Similarly, running an exploration code up to 10⁹ produces 1748 distilled integers, with maximum 9,977,34,375, so it is unlikely this is the right upper bound but among these the maximum with the right distilled descendants is 81,421,875. As derived by

rad=(1:99)[(1:99)%%10>0]
for (dig in 2:12){
for (x in ((10^dig+1):(10^{dig+1}-1))){
y=x%%(10^{dig-1})
if (y>0){
if (x%%y==0){
if (min(as.integer(substring(x,seq(nchar(x)),seq(nchar(x)))))>0){
y=x%%(10^dig)
while (keep&(y>1e3)){
y=y%%(10^trunc(log(y,10)))
if (keep) solz=x}}}}
if (solz<10^dig) break()
topsol=max(solz)}


## Le Monde puzzle [#1066]

Posted in Books, Kids, R with tags , , , , , , , on September 13, 2018 by xi'an

Recalling Le Monde mathematical puzzle  first competition problem

For the X table below, what are the minimal number of lights that are on (green) to reach the minimal and maximal possible numbers of entries (P) with an even (P as pair) number of neighbours with lights on? In the illustration below, there are 16 lights on (green) and 31 entries with an even number of on-neighbours.

As suggested last week, this was amenable to a R resolution by low-tech simulated annealing although the number of configurations was not that large when accounting for symmetries. The R code is a wee bit long for full reproduction here but it works on moving away from a random filling of this cross by 0’s and 1’s, toward minimising or maximising the number of P’s, this simulated annealing loop being inserted in another loop recording the minimal number of 1’s in both cases. A first round produced 1 and 44 for the minimal and maximal numbers of P’s, respectively, associated with at least 16 and 3 1’s, respectively, but a longer run exhibited 45 for 6 1’s crossing one of the diagonals of the X, made of two aligned diagonals of the outer 3×3 tables. (This was confirmed by both Amic and Robin in Dauphine!) The next [trigonometry] puzzle is on!

## Le Monde puzzle [#1650]

Posted in Books, Kids, R with tags , , , , , , , , , on September 5, 2018 by xi'an

A penultimate Le Monde mathematical puzzle  before the new competition starts [again!]

For a game opposing 40 players over 12 questions, anyone answering correctly a question gets as reward the number of people who failed to answer. Alice is the single winner: what is her minimal score? In another round, Bob is the only lowest grade: what is his maximum score?

For each player, the score S is the sum δ¹s¹+…+δ⁸s⁸, where the first term is an indicator for a correct answer and the second term is the sum over all other players of their complementary indicator, which can be replaced with the sum over all players since δ¹(1-δ¹)=0. Leading to the vector of scores

worz <- function(ansz){
scor=apply(1-ansz,2,sum)
return(apply(t(ansz)*scor,2,sum))}


Now, running by brute-force a massive number of simulations confirmed my intuition that the minimal winning score is 39, the number of players minus one [achieved by Alice giving a single good answer and the others none at all], while the maximum loosing score appeared to be 34, for which I had much less of an intuition!  I would have rather guessed something in the vicinity of 80 (being half of the answers replied correctly by half of the players)… Indeed, while in SIngapore, I however ran in the wee hours a quick simulated annealing code from this solution and moved to 77.

And the 2018 version of Le Monde maths puzzle competition starts today!, for a total of eight double questions, starting with an optimisation problem where the adjacent X table is filled with zeros and ones, trying to optimise (max and min) the number of positive entries [out of 45] for which an even number of neighbours is equal to one. On the represented configuration, green stands for one (16 ones) and P for the positive entries (31 of them). This should be amenable to a R resolution [R solution], by, once again!, simulated annealing. Deadline for the reply on the competition website is next Tuesday, midnight [UTC+1]