a chain of collapses

Posted in Books, Kids, R with tags , , , on June 20, 2018 by xi'an A quick riddler resolution during a committee meeting (!) of a short riddle: 36 houses stand in a row and collapse at times t=1,2,..,36. In addition, once a house collapses, the neighbours if still standing collapse at the next time unit. What are the shortest and longest lifespans of this row?

Since a house with index i would collapse on its own by time i, the longest lifespan is 36, which can be achieved with the extra rule when the collapsing times are perfectly ordered. For the shortest lifespan, I ran a short R code implementing the rules and monitoring its minimum. Which found 7 as the minimal number for 10⁵ draws. However, with an optimal ordering, one house plus one or two neighbours of the most recently collapsed, leading to a maximal number of collapsed houses after k time units being

1+2(k-1)+1+2(k-2)+….=k+k(k-1)=k²

which happens to be equal to 36 for k=6. (Which was also obtained in 10⁶ draws!) This also gives the solution for any value of k.

Le Monde puzzle [#928]

Posted in Books, Kids, R with tags , , , on September 10, 2015 by xi'an A combinatorics Le Monde mathematical puzzle:

How many distinct integers between 0 and 16 can one pick so that all positive differences are distinct?

If k is the number of distinct integers, the number of positive differences is

1+2+…+(k-1) = k(k-1)/2,

which cannot exceed 16, because it is a subset of {1,2,…,16}, meaning k cannot exceed 6 if all differences are distinct. From there, picking k integers at random makes it easy to check for the condition:

k=6
N=16
x=sort(sample(0:N,k-1))
y=outer(x[-1],x[-k],"-")
while (max(duplicated(y[!upper.tri(y)]))==1){
x=sort(sample(0:N,k-1))
y=outer(x[-1],x[-k],"-")}

which quickly returns for k=5

> x
 0 1 7 12 15

as a solution. And is still running for k=6, meaning there is apparently no solution for k=6. (An exhaustive search shows there is indeed no solution for k=6 and N=16, while there are several for k=6 and N=17.) Now, reading the puzzle solution of Le Monde today, on September 09, I discovered that the authors proposed a sequence of length 7, (0,1,2,4,5,7,11,16), which does not work since 1-0=2-1… and proved that 8 is an impossible value by quite a convoluted argument. Did I misread again?!

In the earlier version of the R code posted today, I used

...y[lower.tri]...

which does not include the diagonal, instead of the proper

...y[!upper.tri(y)]..

a mistake that led to a wrong solution for k=6, as pointed out by Stephan.