## linear Diophantine equations

Posted in Statistics with tags , , , , , , on May 10, 2018 by xi'an

When re-expressed in maths terms, the current Riddler is about finding a sequence x⁰,x¹,…,x⁷ of integers such that

x⁰=7x¹+1
6x¹=7x²+1

6x⁶=7x⁷+1
6x⁷=7x⁸

which turns into a linear equation with integer valued solutions, or a system of linear Diophantine equation. Which can be easily solved by brute-force R coding:

A=matrix(0,7,7)
for (i in 1:7) A[i,i]=6
for (i in 1:6) A[i,i+1]=-7
for (x in 1:1e6){
zol=solve(a=A,b=c(rep(1,6),7*x))
if (max(abs(zol-round(zol)))<1e-3) print(x)}
x=39990 #x8=5.6.31.43
7*solve(a=A,b=c(rep(1,6),7*x))[1]+1 #x0


which produces x⁰=823537. But it would be nicer to directly solve the linear system under the constraint. For instance, the inverse of the matrix A above is an upper triangular matrix with (upper-)diagonals

1/6, 7/6², 7²/6³,…,7⁶/6⁷

but this does not help considerably, except for x⁸ to be solutions to 7 equations involving powers of 6 and 7… This system of equations can be solved by successive substitutions but this still feels very pedestrian!

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


## cyclic riddle [not in NYC!]

Posted in Kids, R, Running, Travel with tags , , , , , , , , , , on December 29, 2017 by xi'an

In the riddle of this week on fivethirtyeight, the question is to find the average number of rounds when playing the following game: P=6 players sitting in a circle each have B=3 coins and with probability 3⁻¹ they give one coin to their right or left side neighbour, or dump the coin to the centre. The game ends when all coins are in the centre. Coding this experiment in R is rather easy

situz=rep(B,P)
r=1
while (max(situz)>0){
unz=runif(P)
newz=situz-(situz>0)
for (i in (1:P)[unz<1/3])
newz[i%%P+1]=newz[i%%P+1]+(situz[i]>0)
for (i in (1:P)[unz>2/3])
newz[i-1+P*(i==1)]=newz[i-1+P*(i==1)]+(situz[i]>0)
situz=newz
r=r+1}


resulting in an average of 15.58, but I cannot figure out (quickly enough) an analytic approach to the problem. (The fit above is to a Gamma(â-1,ĝ) distribution.)

In a completely unrelated aparté (aside), I read earlier this week that New York City had prohibited the use of electric bikes. I was unsure of what this meant (prohibited on sidewalks? expressways? metro carriages?) so rechecked and found that electric bikes are simply not allowed for use anywhere in New York City. Because of the potential for “reckless driving”. The target is apparently the high number of delivery e-bikes, but this ban sounds so absurd that I cannot understand it passed. Especially when De Blasio has committed the city to the Paris climate agreement after Trump moronically dumped it… Banning the cars would sound much more in tune with this commitment! (A further aparté is that I strongly dislike e-bikes, running on nuclear power plants,  especially when they pass me on sharp hills!, but they are clearly a lesser evil when compared with mopeds and cars.)

## a quincunx on NBC

Posted in Books, Kids, pictures, Statistics with tags , , , , , , , , , , on December 3, 2017 by xi'an

Through Five-Thirty-Eight, I became aware of a TV game call The Wall [so appropriate for Trumpian times!] that is essentially based on Galton’s quincunx! A huge [15m!] high version of Galton’s quincunx, with seven possible starting positions instead of one, which kills the whole point of the apparatus which is to demonstrate by simulation the proximity of the Binomial distribution to the limiting Normal (density) curve.

But the TV game has obvious no interest in the CLT, or in the Beta binomial posterior, only in a visible sequence of binary events that turn out increasing or decreasing the money “earned” by the player, the highest sums being unsurprisingly less likely. The only decision made by the player is to pick one of the seven starting points (meaning the outcome should behave like a weighted sum of seven Normals with drifted means depending on the probabilities of choosing these starting points). I found one blog entry analysing an “idiot” strategy of playing the game, but not the entire game. (Except for this entry on the older Plinko.) And Five-Thirty-Eight surprisingly does not get into the optimal strategies to play this game (maybe because there is none!). Five-Thirty-Eight also reproduces the apocryphal quote of Laplace not requiring this [God] hypothesis.

[Note: When looking for a picture of the Quincunx, I also found this desktop version! Which “allows you to visualize the order embedded in the chaos of randomness”, nothing less. And has even obtain a patent for this “visual aid that demonstrates [sic] a random walk and generates [re-sic] a bell curve distribution”…]

## easy riddle

Posted in Books, Kids, R with tags , , , , , on July 12, 2017 by xi'an

From the current Riddler, a problem that only requires a few lines of code and a few seconds of reasoning. Or not.

N households each stole the earnings from one of the (N-1) other households, one at a time. What is the probability that a given household is not burglarised? And what are the expected final earnings of each household in the list, assuming they all start with \$1?

The first question is close to Feller’s enveloppe problem in that

$\left(1-\frac{1}{N-1}\right)^{N-1}$

is close to exp(-1) for N large. The second question can easily be solved by an R code like

N=1e3;M=1e6
fina=rep(1,N)
for (v in 1:M){
ordre=sample(1:N)
vole=sample(1:N,N,rep=TRUE)
while (min(abs(vole-(1:N)))==0)
vole[abs(vole-(1:N))==0]=sample(1:N,
sum(vole-(1:N)==0))
cash=rep(1,N)
for (t in 1:N){
cash[ordre[t]]=cash[ordre[t]]+cash[vole[t]];cash[vole[t]]=0}
fina=fina+cash[ordre]}


which returns a pretty regular exponential-like curve, although I cannot figure the exact curve beyond the third burglary. The published solution gives the curve

${\frac{N-2}{N-1}}^{999}\times 2+{\frac{1}{N-1}}^{t-1}\times{\frac{N-1}{N}}^{N-t}\times\frac{N}{N-1}$

corresponding to the probability of never being robbed (and getting on average an extra unit from the robbery) and of being robbed only before robbing someone else (with average wealth N/(N-1)).

## continental divide

Posted in Books, Kids, pictures, R with tags , , , , on May 19, 2017 by xi'an

While the Riddler puzzle this week was anticlimactic,  as it meant filling all digits in the above division towards a null remainder, it came as an interesting illustration of how different division is taught in the US versus France: when I saw the picture above, I had to go and check an American primary school on-line introduction to division, since the way I was taught in France is something like that

with the solution being that 12128316 = 124 x 97809… Solved by a dumb R exploration of all constraints:

for (y in 111:143)
for (z4 in 8:9)
for (oz in 0:999){
z=oz+7e3+z4*1e4
x=y*z
digx=digits(x)
digz=digits(z)
if ((digz[2]==0)&(x>=1e7)&(x<1e8)){
r1=trunc(x/1e4)-digz[5]*y
if ((digz[5]*y>=1e3)&(digz[4]*y<1e4) &(r1>9)&(r1<100)){
r2=10*r1+digx[4]-7*y
if ((7*y>=1e2)&(7*y<1e3)&(r2>=1e2)&(r2<1e3)){
r3=10*r2+digx[3]-digz[3]*y
if ((digz[3]*y>=1e2)&(digz[3]*y<1e3)&(r3>9)&(r3<1e2)){
r4=10*r3+digx[2]
if (r4<y) solz=rbind(solz,c(y,z,x))
}}}}


Looking for a computer-free resolution, the constraints on z exhibited by the picture are that (a) the second digit is 0 and the fourth digit is 7.  Moreover, the first and fifth digits are larger than 7 since y times these digits is a four-digit number. Better, since the second subtraction from a three-digit number by 7y returns a three-digit number and the third subtraction from a four-digit number by ny returns a two-digit number, n is larger than 7 but less than the first and fifth digits. Ergo, z is necessarily 97809! Furthermore, 8y<10³ and 9y≥10³, which means 111<y<125. Plus the constraint that 1000-8y≤99 implies y≥112. Nothing gained there! This leaves 12 values of y to study, unless there is another restriction I missed…

## “In short, the French presidential election is a mess”

Posted in Statistics with tags , , , , , , on April 23, 2017 by xi'an

Harry Enten (and not Nate Silver as reported by Le Monde) published yesterday a post on Five-Thirty-Eight about the unpredictability of the French elections. Which essentially states the obvious, namely that the four major candidates all stand a chance to make it to the runoff. (The post classifies Macron as a former left-wing socialist, which shows a glaring misunderstanding of the candidate or a massive divergence of what left-wing means between France and the USA.) The tribune states both that the polls could exhibit a bigger mistake than in the previous elections and that Le Pen score is unlikely to be underestimated, because voters are no longer shy to acknowledge they vote for a fascist candidate. One argument for the error in the polls is attributed to pollsters “herding” their results, i.e., shrinking the raw figures towards the global average taken over previous polls. A [rather reasonable] correction dismissed by Le Monde and French pollsters. While Enten argues that the variability of the percentages over fifty polls is too small to be plausible, assuming a Normal distribution that may not hold because French pollsters use quotas to build their polling population. In any case, this analysis, while cautious and reasonably so!, does not elaborate on the largest question mark, the elephant in the room, namely the percentage of abstentions today and their distribution among the political spectrum, which may eventually make the difference tonight. Indeed, “the bottom line is that we don’t know what’s going to happen on Sunday.” And it is definitely frightening!