Archive for permutation

overlap, overstreched

Posted in Books, Kids, R, Statistics with tags , , , , , , on June 15, 2020 by xi'an

An interesting challenge on The Riddler on the probability to see a random interval X’ing with all other random intervals when generating n intervals from Dirichlet D(1,1,1). As it happens the probability is always 2/3, whatever n>1, as shown by the R code below (where replicate cannot be replaced by rep!):

qro=function(n,T=1e3){
  quo=function(n){
     xyz=t(apply(matrix(runif(2*n),n),1,sort))
  sum(xyz[,1]<min(xyz[,2])&xyz[,2]>max(xyz[,1]))<0}
  mean(replicate(quo(n),T))}

and discussed more in details on X validated. As only a property on permutations and partitions. (The above picture is taken from this 2015 X validated post.)

Le Monde puzzle [#1036]

Posted in Books, Kids, R with tags , , , , on January 4, 2018 by xi'an

lemondapariAn arithmetic Le Monde mathematical puzzle to conclude 2017:

Find (a¹,…,a¹³), a permutation of (1,…,13) such that

a¹/a²+a³=a²+a³/a³+a⁴+a⁵=b¹<1
a⁶/a⁶+a⁷=a⁶+a⁷/a⁷+a⁸+a⁹=a⁷+a⁸+a⁹/a⁵+a⁹+a¹⁰=b²<1
a¹¹+a¹²/a¹²+a¹³=a¹²+a¹³/a¹³+a¹⁰=b³<1

The question can be solved by brute force simulation, checking all possible permutations of (1,…,13). But 13! is 6.6 trillion, a wee bit too many cases. Despite the problem being made of only four constraints and hence the target function taking only five possible values, a simulated annealing algorithm returned a solution within a few calls:

(a¹,…,a¹³)=(6,1,11,3,10,8,4,9,5,12,7,2,13)
(b¹,b²,b³)=(1/2,2/3,3/5)

using the following code:

checka=function(a){ #target to maximise
 return(1*(a[1]/sum(a[2:3])==sum(a[2:3])/sum(a[3:5]))+
  1*(sum(a[6:7])/sum(a[7:9])==a[6]/sum(a[6:7]))+
  1*(sum(a[7:9])/(a[5]+sum(a[9:10]))==a[6]/sum(a[6:7]))+
  1*(sum(a[11:12])/sum(a[12:13])==sum(a[12:13])/
    (a[10]+a[13])))}
parm=sample(1:13)
cheka=checka(parm)
beta=1
for (t in 1:1e6){
  qarm=parm
  idx=sample(1:13,sample(2:12))
  qarm[idx]=sample(qarm[idx])
  chekb=checka(qarm)
  if (log(runif(1))<beta*(chekb-cheka)){
     cheka=chekb;parm=qarm}
  beta=beta*(1+log(1.00001))
  if (cheka==4) break()}

Le Monde puzzle [#932]

Posted in Books, Kids, Statistics, University life with tags , , , , on October 15, 2015 by xi'an

A Sudoku-like Le Monde mathematical puzzle:

A 12×8 grid contains the first 96 integers, as in R matrix(1:96,ncol=12). If one picks 24 of those integers including 3 for each row and 2 for each column, what are the extreme values of the sum of the selected integers?

I obviously rephrased quite strongly the question (and possibly changed it!). Before rushing to the R simulation of a random collection of 24 such integers, I pondered how this sum could vary among random samples since there were the same terms in all samples. More clearly, using the 10×10 grid instead as a basis for reasoning, picking e.g. 20 integers with 2 per row and 2 per colum for all rows and columns, we end up with 2 copies of every integer between 0 and 9 and 2 copies of every decimal between 0 and 90. Random simulation confirms this reasoning:

grid=matrix(1:96,ncol=12)
#pick a subset at random
coleft=sample(rep(1:12,2))
sub7=grid[1,coleft[1:3]]
coleft=coleft[-(1:3)]
for (i in 2:8){
  sub7=c(sub7,grid[i,coleft[1:3]])
  coleft=coleft[-(1:3)]}
resl=sum(sub7)

since repeated call to the above keeps returning the same value, 1164, which is also

> sum(3*(0:7))*12+2*sum(1:12)
[1] 1164

another viral math puzzle

Posted in Books, Kids, R, University life with tags , , , , , , , on May 25, 2015 by xi'an

After the Singapore Maths Olympiad birthday problem that went viral, here is a Vietnamese primary school puzzle that made the frontline in The Guardian. The question is: Fill the empty slots with all integers from 1 to 9 for the equality to hold. In other words, find a,b,c,d,e,f,g,h,i such that

a+13xb:c+d+12xef-11+gxh:i-10=66.

With presumably the operation ordering corresponding to

a+(13xb:c)+d+(12xe)f-11+(gxh:i)-10=66

although this is not specified in the question. Which amounts to

a+(13xb:c)+d+(12xe)f+(gxh:i)=87

and implies that c divides b and i divides gxh. Rather than pursing this analytical quest further, I resorted to R coding, checking by brute force whether or not a given sequence was working.

baoloc=function(ord=sample(1:9)){
if (ord[1]+(13*ord[2]/ord[3])+ord[4]+
12*ord[5]-ord[6]-11+(ord[7]*ord[8]/
ord[9])-10==66) return(ord)}

I then applied this function to all permutations of {1,…,9} [with the help of the perm(combinat) R function] and found the 128 distinct solutions. Including some for which b:c is not an integer. (Not of this obviously gives a hint as to how a 8-year old could solve the puzzle.)

As pointed out in a comment below, using the test == on scalars is a bad idea—once realising some fractions may be other than integers—and I should thus replace the equality with an alternative that bypasses divisions,

baoloc=function(ord=sample(1:9)){
return(((ord[1]+ord[4]+12*ord[5]-ord[6]-87)*
ord[3]*ord[9]+13*ord[2]*ord[9]+
ord[3]*ord[7]*ord[8]==0)*ord)}

leading to the overall R code

sol=NULL
perms=as.matrix(data.frame(permutations(9)),ncol=9,byrow=TRUE)
for (t in 1:factorial(9)){
  a=baoloc(perms[t,])
  if (a[1]>0) sol=rbind(sol,a)}
sol=sol[do.call(order, as.data.frame(sol)),]

and returning the 136 different solutions…