Le Monde puzzle [#1088]

A board (Ising!) Le Monde mathematical puzzle in the optimisation mode, again:

On a 7×7 board, what is the maximal number of locations that one can occupy when imposing at least two empty neighbours ?

Which I tried to solve by brute force and simulated annealing (what else?!), first defining a target

targ=function(tabz){
  sum(tabz[-c(1,9),-c(1,9)]-1.2*(tabz[-c(1,9),-c(1,9)]*tabz[-c(8,9),-c(1,9)]
      +tabz[-c(1,9),-c(1,9)]*tabz[-c(1,2),-c(1,9)]
      +tabz[-c(1,9),-c(1,9)]*tabz[-c(1,9),-c(8,9)]
      +tabz[-c(1,9),-c(1,9)]*tabz[-c(1,9),-c(1,2)]>2))}

on a 9×9 board where I penalise prohibited configuration by a factor 1.2 (a wee bit more than empty nodes). The perimeter of the 9×9 board is filled with ones and never actualised. (In the above convoluted products, the goal is to count how many neighbours of the entries equal to one are also equal to one. More than 2 is penalised.) The simulated annealing move is then updating the 9×9 grid gridz:

temp=1
maxarg=curarg=targ(gridz)
for (t in 1:1e3){
  for (v in 1:1e4){
    i=sample(2:8,1);j=sample(2:8,1)
    newgrid=gridz;newgrid[i,j]=1-gridz[i,j]
    newarg=targ(newgrid)
    if (log(runif(1))<temp*(newarg-curarg)){
      gridz=newgrid;curarg=newarg}}
temp=temp+.01}

and calls to the procedure always return 28 entries as the optimum, as in

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

As it happens, I had misread the wording of the original puzzle, which considered a dynamic placement of the units on the board, one at a time with two free neighbours imposed.

Le Monde puzzle [#1086]

A terse Le Monde mathematical puzzle in the optimisation mode:

What is the maximal fraction of the surface of a triangle occupied by an inner triangle ABC where Abigail picks a summit A on a first side, Berenice B on a second side, and then Abigails picks C on the third side, towards Abigail maximising and Berenice minimising this surface?

Which I first tried to solve by pen & paper, completing another black block for the occasion, as coding the brute force R version sounded too painful:

leading me to conclude that, for a rectangle triangle (although the result sounds independent of this feature), the optimum was the middle triangle, weighting one-fourth of the original surface. Reprogramming the question in the plane to Angkor produced the same output, modulo my approximation of the triangle continuum with a 200×200/2grid:

Le Monde puzzle [#1072]

The penultimate Le Monde mathematical puzzle  competition problem is once again anti-climactic and not worth its points:

For the figure below [not the original one!], describing two (blue) half-circles intersecting with a square of side 20cm, and a (orange) quarter of a circle with radius 20cm, find the radii of both gold circles, respectively tangent to both half-circles and to the square and going through the three intersections.

Although the problem was easily solvable by some basic geometry arguments, I decided to use them a minima and resort to a mostly brute-force exploration based on a discretisation of the 20×20 square, from which I first deduced the radius of the tangent circle by imposing (a) a centre O on the diagonal (b) a distance from O to one (half-)circle equal to the distance to the upper side of the square, leading to a radius of 5.36 (and a centre O at a distance 20.70 from the bottom left corner):

diaz=sqrt(2)*20
for (diz in seq(5/8,7/8,le=1e4)*diaz){#position of O
  radi=sqrt(diz^2/2+(diz/sqrt(2)-10)^2)-10
  if (abs(20-(diz/sqrt(2))-radi)<3e-3){
      print(c(radi,diz));break()}}

In the case of the second circle I first deduced the intersections of the different circles by sheer comparison of black (blue!) pixels, namely A(4,8), B(8,4), and C(10,10), then looked at the position of the centre O’ of the circle such that the distances to A, B, and C were all equal:

for (diz in seq(20*sqrt(2)-20,10*sqrt(2),le=1e4)){
  radi=10*sqrt(2)-diz
  distA=sqrt((diz/sqrt(2)-4)^2+(diz/sqrt(2)-8)^2)
  if (abs(distA-radi)<4e-4){
    print(c(radi,diz));break()}}

even though Heron’s formula was enough to produce the radius. In both approaches, this radius is 3.54, with the position of the centre O’at 10.6 from the lower left corner. When plotting these results, which showed consistency at this level of precision,  I was reminded of the importance of plotting the points with the option “asp=1” in plot() as otherwise, draw.circle() does not plot the circles at the right location!

Le Monde puzzle [#1067]

The second Le Monde mathematical puzzle in the new competition is sheer trigonometry:

When in the above figures both triangles ABC are isosceles and the brown segments are all of length 25cm, find the angle in A and the value of DC², respectively.

This could have been solved by R coding the various possible angles of the three segments beyond BC until the isosceles property is met, but it went much faster by pen and paper, leading to an angle of π/9 in the first case and a square of 1250 in the second case. The third puzzle is basic arithmetic that only seems solvable by enumeration…

Le Monde puzzle [#1707]

A geometric Le Monde mathematical puzzle:

1. Given a pizza of diameter 20cm, what is the way to cut it by two perpendicular lines through a point distant 5cm from the centre towards maximising the surface of two opposite slices?
2.  Using the same point as the tip of the four slices, what is the way to make four slices with equal arcs in four cuts from the tip again towards maximising the surface of two opposite slices?
   

For both questions, I did not bother with the maths but went itself to a discretisation of the disk, counting the proportion of points within two opposite slices and letting the inclination of these slices move from zero to π/2. Unsurprisingly, for the first question, the answer is π/4, given that there is no difference between both surfaces at angles 0 and π/2. My R code is as follows, using (5,0) as the tip:

M=100
surfaz=function(alpha){
surfz=0
cosal=cos(alpha);sinal=sin(alpha)
X=Y=seq(-10,10,le=M)
Xcosal=(X-5)*cosal
Xsinal=(X-5)*sinal
for (i in 1:M){
norm=sqrt(X[i]^2+Y^2)
scal1=Xsinal[i]+Y*cosal
scal2=-Xcosal[i]+Y*sinal
surfz=surfz+sum((norm<=10)*(scal1*scal2>0))}
return(4*surfz/M/M/pi)}

The second puzzle can be solved by a similar code, except that the slice area between two lines has to be determined by a cross product:

surfoz=function(alpha,ploz=FALSE){
  sinal=sin(alpha);cosal=cos(alpha)
  X=Y=seq(-10,10,le=M)
  frsterm=cosal*(10*cosal-5)+sinal*(10*sinal-5)
  trdterm=cosal*(10*cosal+5)+sinal*(10*sinal+5)
  surfz=0
  for (i in 1:M){
    norm=sqrt(X[i]^2+Y^2)
    scal1=(10*(Y[i]-5)*cosal-(10*sinal-5)*X)*frsterm
    scal2=-(-10*(Y[i]-5)*sinal-(10*cosal-5)*X)*frsterm
    scal3=(-10*(Y[i]-5)*cosal+(10*sinal+5)*X)*trdterm
    scal4=-(10*(Y[i]-5)*sinal+(10*cosal+5)*X)*trdterm
    surfz=surfz+sum((norm<=10)* 
    ((scal1>0)*(scal2>0)+
     (scal3>0)*(scal4>0)))}
 return(4*surfz/M/M/pi)}

a code that shows that all cuts lead to identical surfaces for bot sets of slices. A fairly surprising result!