Archive for mathematical puzzle

a riddle at the end of its tether

Posted in R, Statistics with tags , , on February 24, 2017 by xi'an

A simply worded riddle this week on The Riddler, about four ropes having non-uniform and unknown burning rates, the only constraint being they all burn completely in one hour. With the help of a lighter (or even a single match), what are the possible units of time one can measure by burning them?

While I had worked out a range of possible times for each of the ropes to complete its combustion, I went for a simulation based confirmation. The starting point is that a new fire can only be started when a burning rope ends up burning. Which only happens for a finite number of possibilities. I found 24 of them, consisting of

> total*prec
[1]  0.000 0.5000 0.750 0.875 0.9375 1.000 1.125 1.1875 1.25 1.3125
[11] 1.375 1.4375 1.500 1.625 1.7500 1.875 2.000 2.1250 2.25 2.5000
[21] 2.750 3.0000 3.500 4.000

i.e., some combinations of 1, 2⁻¹, …, 2⁻⁴, with the comment that those times cannot all be obtained within a single arson experiment.

Continue reading

A knapsack riddle [#2]?

Posted in Kids, R, Statistics with tags , , , on February 17, 2017 by xi'an

gear

Still about this allocation riddle of the past week, and still with my confusion about the phrasing of the puzzle, when looking at a probabilistic interpretation of the game, rather than for a given adversary’s y, the problem turns out to search for the maximum of

\mathbb{E}[L(x,Y)]=\sum_{i=1}^{10} i\{P(Y_i<x_i)-P(Y_i>x_i)\}

where the Y’s are Binomial B(100,p). Given those p’s, this function of x is available in closed form and can thus maximised by a simulated annealing procedure, coded as

utility=function(x,p){
  ute=2*pbinom(x[1]-1,100,prob=p[1])+
   dbinom(x[1],100,p[1])
  for (i in 2:10)
   ute=ute+2*i*pbinom(x[i]-1,100,prob=p[i])+
    i*dbinom(x[i],100,p[i])
  return(ute)}
#basic term in utility
baz=function(i,x,p){
  return(i*dbinom(x[i],100,p[i])+
   i*dbinom(x[i]-1,100,p[i]))}
#relies on a given or estimated p
x=rmultinom(n=1,siz=100,prob=p)
maxloz=loss=0
newloss=losref=utility(x,p)
#random search
T=1e3
Te=1e2
baza=rep(0,10)
t=1
while ((t<T)||(newloss>loss)){
 loss=newloss
 i=sample(1:10,1,prob=(10:1)*(x>0))
#moving all other counters by one
 xp=x+1;xp[i]=x[i]
#corresponding utility change
 for (j in 1:10) baza[j]=baz(j,xp,p)
  proz=exp(log(t)*(baza-baza[i])/Te)
#soft annealing move
 j=sample(1:10,1,prob=proz)
 if (i!=j){ x[i]=x[i]-1;x[j]=x[j]+1}
newloss=loss+baza[j]-baza[i]
if (newloss>maxloz){
 maxloz=newloss;argz=x}
t=t+1
if ((t>T-10)&(newloss<losref)){
 t=1;loss=0
 x=rmultinom(n=1,siz=100,prob=p)
 newloss=losref=utility(x,p)}}

which seems to work, albeit not always returning the same utility. For instance,

> p=cy/sum(cy)
> utility(argz,p)
[1] 78.02
> utility(cy,p)
[1] 57.89

or

> p=sy/sum(sy)
> utility(argz,p)
[1] 82.04
> utility(sy,p)
[1] 57.78

Of course, this does not answer the question as intended and reworking the code to that purpose is not worth the time!

Le Monde puzzle [#990]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on January 12, 2017 by xi'an

To celebrate the new year (assuming it is worth celebrating!), Le Monde mathematical puzzle came up with the following:

Two sequences (x¹,x²,…) and (y¹,y²,…) are defined as follows: the current value of x is either the previous value or twice the previous value, while the current value of y is the sum of the values of x up to now. What is the minimum number of steps to reach 2016 or 2017?

By considering that all consecutive powers of 2 must appear at least one, the puzzles boils down to finding the minimal number of replications in the remainder of the year minus the sum of all powers of 2. Which itself boils down to deriving the binary decomposition of that remainder. Hence the basic R code (using intToBits):

deco=function(k=2016){
 m=trunc(log2(k))
 while (sum(2^(0:m))>k) m=m-1
 if (sum(2^(0:m))==k){ return(rep(1,m+1))
 }else{
 res=k-sum(2^(0:m))
 return(rep(1,m+1)+as.integer(intToBits(res))[1:(m+1)])

which produces

> sum(deco(2016))
[1] 16
> sum(deco(2017))
[1] 16
> sum(deco(1789))
[1] 18

untangling riddle

Posted in Statistics with tags , , on December 23, 2016 by xi'an

Boston1This week riddle is rather anticlimactic [my rewording]:

N wires lead from the top of a tower down to the ground floor. But they have become hopelessly tangled. The wires on the top floor are all labelled, from 1 to N. The wires on the bottom, however, are not.

You need to figure out which ground-floor wire’s end corresponds to which top-floor wire’s end. On the ground floor, you can tie two wire ends together, and you can tie as many of these pairs as you like. You can then walk to the top floor and use a circuit detector to check whether any two of the wires at the top of the tower are connected or not.

What is the smallest number of trips to the top of the tower you need to take in order to correctly label all the wires on the bottom?

Indeed, first, if N=2, the wires cannot be identified, if N=3, they can be identified in 2 steps, and if N=4, they can also be identified in 2 steps (only pair two wires first, which gives their values and the values of the other two up to a permutation, then pair one of each group). Now, in general,  it seems that, by attaching the wires two by two, one can successively cut the number of wires by two at each trip. This is due to the identification of pairs: if wires a and b are connected in one step, identifying the other end of a will automatically determine the other end of b if one keeps track of all connected pairs at the top. Hence, if N=2^k, in (k-2) steps, we are down to 4 wires and it takes an extra 2 steps to identify those 4, hence all the other wires. Which leads to identification in N trips. If N is not a power of 2, things should go faster as “left over” wires in the binary division can be paired with set-aside wires and hence identify 3 wires on that trip, then further along the way… Which leads to a 2^{\lfloor \log_2(N) \rfloor} number of trips maybe (or even less). Continue reading

Le Monde puzzle [#940]

Posted in Kids, Statistics, Travel, University life with tags , , , on November 11, 2016 by xi'an

A sudoku-like Le Monde mathematical puzzle:

On a 3×3 grid, all integers from 1 to 9 are present. Considering all differences between adjacent entries, the value of the grid is the minimum difference. What is the maximum possible value?

In a completely uninspired approach considering random permutations on {1,..,9}, the grid value can be computed as

neigh=c(1,2,4,5,7,8,1,4,2,5,3,6)
nigh=c(2,3,5,6,8,9,4,7,5,8,6,9)
perm=sample(9)
val<-function(perm){
min(abs(perm[neigh]-perm[nigh]))}

which produces a value of 3 for the maximal value. For a 4×4 grid

neigh=c(1:3,5:7,9:11,13:15,1+4*(0:2),2+4*(0:2),3+4*(0:2),4*(1:3))
nigh=c(2:4,6:8,10:12,14:16,1+4*(1:3),2+4*(1:3),3+4*(1:3),4*(2:4))
perm=sample(16)
val<-function(perm){
min(abs(perm[neigh]-perm[nigh]))}

the code returns 5. For the representation

[,1] [,2] [,3] [,4]
[1,] 8 13 3 11
[2,] 15 4 12 5
[3,] 9 14 6 16
[4,] 2 7 1 10

The CS detective

Posted in Books, Kids, Travel, University life with tags , , , , , , , on October 29, 2016 by xi'an

A few weeks ago, I received a generic email from No Starch Press promoting The CS Detective, and as I had liked their earlier Statistics Done Wrong, I requested a review copy of the book. Which I received in Warwick while I was there, last week. And read over my trip back to Paris. As it is a very quick read.

“The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.” T. Pratchett

The idea of the book is to introduce some concepts of tree searching algorithms through a detective-cum-magic story, a very shallow story if somewhat à la Terry Pratchett. (While this reference does not appear in the book, there are enough mentions made of turtles to suspect the filiation. Even though it is turtles all the way down. Hence I could not swear Frank Runtime was 100% inspired from Sam Vimes. But it rhymes.) I cannot say I am a bit fan of this approach as the story is an hindrance rather than an help, I do not find it particularly funny or enticing, and I keep wishing for the next concept to appear to end the current chapter and its inane plot. Of course, once the story is set aside, the book contains not that much in terms of search algorithms, because they all are limited to discrete tree structures. Namely, exhaustive, binary, breadth- and depth-first, iterative deepening, best-first, search algorithms, along with the notions of arrays, queues, stacks, and heaps. This fills about 50 pages of technical vignettes found at the end of each chapter…

So I end up wondering at what age this book would appeal to a young reader. Trying to remember from my own experience with summer vacation riddle and puzzle books, I would think the range 10-12 could be most appropriate although mileage will vary. Since the author, Jeremy Kubica, animates the Computational Fairy Tales blog with stories of the same flavour, you may start by tasting and testing this approach to popular science before getting the entire book

Le Monde puzzle [#977]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , , on October 3, 2016 by xi'an

A mild arithmetic Le Monde mathematical puzzle:

Find the optimal permutation of {1,2,..,15} towards minimising the maximum of sum of all three  consecutive numbers, including the sums of the 14th, 15th, and first numbers, as well as the 15th, 1st and 2nd numbers.

If once again opted for a lazy solution, not even considering simulated annealing!,

parme=sample(15)
max(apply(matrix(c(parme,parme[-1],
parme[1],parme[-(1:2)],parme[1:2]),3),2,sum))

and got the minimal value of 26 for the permutation

14 9 2 15 7 1 11 10 4 12 8 5 13 6 3

Le Monde gave a solution with value 25, though, which is

11 9 7 5 13 8 2 10 14 6 1 12 15 4 3

but there is a genuine mistake in the solution!! This anyway shows that brute force may sometimes fail. (Which sounds like a positive conclusion to failing to find the proper solution! But trying with a simple simulated annealing version did not produce any 25 either…)