**T**oday is the launching day of PRAIRIE, one of the four Instituts Interdisciplinaires d’Intelligence Artificielle (3IA) supported by the French government. Taking place in Paris Dauphine, with Yann Le Cun as guest speaker. I have been fortunate to be endowed with one of these chairs for the coming years, along with my CEREMADE colleagues Laurent Cohen and Irène Waldspurger.

## Archive for CEREMADE

## Prairie chair

Posted in pictures, Statistics, University life with tags 3IA, art photographs, artificial intelligence, Canada, CEREMADE, chair, Facebook, prairie, PSL Research University, The Prairie Chair, Université Paris Dauphine, Yann Le Cun on October 2, 2019 by xi'an## Le Monde puzzle [#1075]

Posted in Books, Kids, R with tags CEREMADE, competition, Dauphine, Le Monde, mathematical puzzle, optimisation, R, simulated annealing 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 affaire de logique, Alice and Bob, birthday problem, CEREMADE, competition, Dauphine, Le Monde, logic, mathematical puzzle, she said he said, simulated annealing, Singapore 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 [#1070]

Posted in Books, Kids, R, University life with tags CEREMADE, competition, Dauphine, dynamic programming, Le Monde, mathematical puzzle, optimisation, R on October 11, 2018 by xi'an**R**ewording Le Monde mathematical puzzle fifth competition problem

For the 3×3 tables below, what are the minimal number of steps to move from left to rights when the yellow tokens can only be move to an empty location surrounded by two other tokens?

In the 4×4 table below, there are 6 green tokens. How many steps from left to right?

Painful and moderately mathematical, once more… For the first question, a brute force simulation of random valid moves of length less than 100 returns solutions in 4 steps:

[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1

But this is not an acceptable move because of the “other” constraint. Imposing this constraint leads to a solution in 9 steps, but is this the lowest bound?! It actually took me most of the weekend (apart from a long drive to and from a short half-marathon!) to figure out a better strategy than brute force random exploration: the trick I eventually figured out is to start from the finishing (rightmost) value F of the grid and look at values with solutions available in 1,2,… steps. This is not exactly dynamic programming, but it keeps the running time under control if there is a solution associated with the starting (leftmost) value S. (Robin proceeded reverse-wise, which in retrospect is presumably equivalent, if faster!) The 3×3 grid has 9 choose 5, ie 126, possible configurations with 5 coins, which means the number of cases remains under control. And even so for the 4×4 grid with 6 coins, with 8008 configurations. This led to a 9 step solution for n=3 and the proposed starting grid in yellow:

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

and a 19 step solution for n=4:

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

The first resolution takes less than a minute and the second one just a few minutes (or less than my short morning run!). Surprisingly, using this approach does not require more work, which makes me wonder at the solution Le Monde journalists will propose. Given the (misguided) effort put into my resolution, seeing a larger number of points for this puzzle is no wonder.

## Le Monde puzzle [#1068]

Posted in Books, Kids, R with tags CEREMADE, competition, Dauphine, Le Monde, mathematical puzzle, optimisation, R, simulated annealing on September 26, 2018 by xi'an**A**nd 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³… isrefinedif 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){ rad=c(rad,x) y=x%%(10^dig) keep=(y%in%rad) while (keep&(y>1e3)){ y=y%%(10^trunc(log(y,10))) keep=keep&(y%in%rad)} if (keep) solz=x}}}} if (solz<10^dig) break() topsol=max(solz)}

## Le Monde puzzle [#1066]

Posted in Books, Kids, R with tags CEREMADE, competition, Dauphine, Le Monde, mathematical puzzle, optimisation, R, simulated annealing on September 13, 2018 by xi'an**R**ecalling 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!*

## journée algorithmes stochastiques à Dauphine vendredi

Posted in Statistics, University life with tags CEREMADE, computational statistics, MCMC, Paris, sequential Monte Carlo, Statistics, stochastic algorithms, stochastic optimisation, tea, Université Paris Dauphine, workshop on November 28, 2017 by xi'an**A** final reminder (?) that we hold a special day of five talks around stochastic algorithms at Dauphine this Friday, from 10:00 till 17:30. Attendance is free, coffee and tea are free (while they last!), come and join us!