Archive for triangle

an attempt at code golf

Posted in Kids, R with tags , , , , , , , , , on May 15, 2019 by xi'an

Having discovered codegolf on Stack Exchange a few weeks ago, I spotted a few interesting puzzles since then but only got the opportunity at a try over a quiet and rainy weekend (and Robin being on vacation)! The challenge was to write an R code for deciding whether or not a given integer n is congruent or not, when congruent means that it is the surface of a rectangle triangle with all three sides rational. The question included a pointer to the Birch and Swinnerton-Dyer conjecture as a mean to check congruence although the real solution was provided by Tunnell’s Theorem, which states that n is congruent if and only if the number of integer solutions to 2x²+y²+8z²=n is twice as much as the number of integer solutions to 2x²+y²+32z²=n if n is odd and  the number of integer solutions to 8x²+y²+16z²=n is twice as much as the number of integer solutions to 8x²+y²+64z²=n if n is even. Although this is only true for squared-free integers. (I actually spent more time on figuring out the exact wording of the theorem than on optimising the R code!)

My original solution

p=function(n){
 for (i in(n:2)^2)if(n%%i<1)n=n/i
 if(n%%2){d=8;f=2;g=16}else{d=2;f=1;g=8}
 A=0;b=(-n:n)^2
 for(x in d*b)for(y in x+f*b)for(z in g*b)
  A=A+(y+z==n)-2*(y+4*z==n)
 A==0}

was quite naïve, as shown by the subsequent improvements by senior players, like the final (?) version of Guiseppe:

function(n){b=(-n:n)^2
for(i in b[b>0])n=n/i^(!n%%i)
P=2^(n%%2)
o=outer
!sum(!o(y<-o(8/P*b,2*b,"+")/P-n,z<-16/P*b,"+"),-2*!o(y,4*z,"+"))}

exhibiting a load of code golf tricks, from using an anonymous function to renaming functions with a single letter, to switching from integers to booleans and back with the exclamation mark.

Le Monde puzzle [#1088]

Posted in Books, Kids, R with tags , , , , , , , , on March 29, 2019 by xi'an

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]

Posted in pictures, Statistics, Travel with tags , , , , , , on March 7, 2019 by xi'an

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:

a one-chance meeting [puzzle]

Posted in Books, Kids, pictures, R with tags , , , , , , on March 6, 2018 by xi'an

This afternoon, I took a quick look at the current Riddler puzzle, which sums up as, given three points A, B, C, arbitrarily moving on a plane with a one-shot view of their respective locations, find a moving rule to bring the three together at the same point at the same time. And could not spot the difficulty.

The solution seems indeed obvious when expressed as above rather than in the tell-tale format of the puzzle. Since every triangle has a circumscribed circle, and all points on that circle are obviously at the same distance of the centre O, the three points have to aim at the centre O. Assuming they all move at the same velocity, they will reach O together…

The question gets a wee bit more interesting when the number of points with the same one-time one-shot view option grows beyond 3, as these points will almost surely not all lie on a single circumscribed circle. While getting them together can be done by (a) finding the largest circle going through 3  points and containing all others [in case there is no such circle, adding an artificial point solves the issue!], triplet on which one can repeat the above instructions to reach O, and (b) bringing all points inside the circle to meet with one of the three points [the closest] on its straight-line way to O, by finding a point on that line at equal distance from both, a subsidiary question is whether or not this is the fastest way. Presumably not.  (Again I may be missing one item of the puzzle.)

When experimenting with a short R code, I quickly figured out that the circumscribed circles associated with all triplets do not necessarily contain all points. The resolution of this difficulty is however straightforward as it suffices to add an artificial point by considering all circumcentres and their distances to the farthest point, minimising over these distances and adding the extra point at random over the circumference. As in the example below.Incidentally, it took me much longer to write this post than to solve the puzzle, as I was trying to use the R function draw.circle, which supposedly turns a centre and a radius into the corresponding circle, but somehow misses its target by adapting the curve to the area being displayed. I am still uncertain of what the function means. I hence ended up writing a plain R function for this purpose:

dracirc=function(A,B,C){
  O=findcentr(A,B,C)
  ro=dist(rbind(A,O))
  lines(x=O[1]+ro*sin(2*pi*seq(0,1,le=180)),
  y=O[2]+ro*cos(2*pi*seq(0,1,le=180)))}

Le Monde puzzle [#1012]

Posted in Books, Kids with tags , , , , , on June 14, 2017 by xi'an

A basic geometric Le Monde mathematical puzzle:

Take a triangle ABC such that the side AB is c=42 long, each side has an integer length, and the area is 756. Given an inner point D, draw three lines parallel to the three sides of ABC through D in order to construct three triangles with common summit D and bases supported by these three sides.

  1. How far is D from the base AB when all three triangles have perimeters equal to the sides that support their basis?
  2. How far is D from the previous solution when the sum of the areas of the three triangles is minimal?

Since the puzzle is purely geometric, I was quite tempted to bypass it and to watch instead the British elections and the Comey audition! However, the sides a and b are easily found by an exhaustive search, a=39 and b=45 (or the reverse). From there, the problem resolution proceeds by a similar triangles argument, since all triangles constructed by the game rule have the same angles, hence proportional sides. For the first question, this leads to a straightforward determination of the basis of each triangle by the perimeter equation, meaning that D is then 12 units away from AB. The second question is not harder in that the surface of a triangle with basis a and opposite angles β and γ can be written as

a²sin(β)sin(γ)/2sin(β+γ)

meaning it suffices to minimise a²+a’²+a”² under the constraint that the sum of the three sides parallel to BC is the complete length of BC, a²+a’²+a”²=39. The solution is then that all triangles are identical, leading to a summit D’ at a distance 12 from AB, again!, but in the middle of the segment, hence distance to the earlier D equal to one.

Bertand’s paradox [R details]

Posted in Books, R, Statistics with tags , , , , , , , on March 20, 2011 by xi'an

Some may have had reservations about the “randomness” of the straws I plotted to illustrate Bertrand’s paradox. As they were all going North-West/South-East. I had actually made an inversion between cbind and rbind in the R code, which explained for this non-random orientation. Above is the corrected version, which sounds “more random” indeed. (And using wheat as the proper, if weak, colour!) The outcome of a probability of 1/2 has not changed, of course. Here is the R code as well:


lacorde=rep(0,10^3)
plot(0,0,type="n",xlim=c(-2,2),ylim=c(-2,2))

for (t in 1:10^3){

 #distance from O to chord
 dchord=10

 while (dchord>1){
 #Generate "random" straw in large box till it crosses unit circle

 a=runif(2,-10,10)
 b=runif(2,-10,10)

 #endpoints outside the circle
 if ((sum(a^2)>1)&&(sum(b^2)>1)){

 theta=abs(acos(t(b-a)%*%a/sqrt(sum((b-a)^2)*sum(a^2))))
 theta=theta%%pi
 thetb=abs(acos(t(a-b)%*%b/sqrt(sum((b-a)^2)*sum(b^2))))
 thetb=thetb%%pi

 #chord inside
 if (max(abs(theta),abs(thetb))<pi/2)
 dchord=abs(sin(theta))*sqrt(sum(a^2))
 }
 }

 lacorde[t]=2*sqrt(1-dchord)
 if (runif(1)<.1) lines(rbind(a,b),col="wheat")
 }

lecercle=cbind(sin(seq(0,2*pi,le=100)),cos(seq(0,2*pi,le=100)))
lines(lecercle,col="sienna")

As a more relevant final remark, I came to the conclusion (this morning while running) that the probability of this event can be anything between 0 and 1, rather than the three traditional 1/4, 1/3 and 1/2. Indeed, for any distribution of the “random” straws, hence for any distribution on the chord length L, a random draw can be expressed as L=F⁻¹(U), where U is uniform. Therefore, this draw is also an acceptable transform of a uniform draw, just like Bertrand’s three solutions.