Archive for mathematical puzzle

Sunday morning puzzle

Posted in Books, Kids, R with tags , , , on November 22, 2015 by xi'an

A question from X validated that took me quite a while to fathom and then the solution suddenly became quite obvious:

If a sample taken from an arbitrary distribution on {0,1}⁶ is censored from its (0,0,0,0,0,0) elements, and if the marginal probabilities are know for all six components of the random vector, what is an estimate of the proportion of (missing) (0,0,0,0,0,0) elements? 

Since the censoring modifies all probabilities by the same renormalisation, i.e. divides them by the probability to be different from (0,0,0,0,0,0), ρ, this probability can be estimated by looking at the marginal probabilities to be equal to 1, which equal the original and known marginal probabilities divided by ρ. Here is a short R code illustrating the approach that I wrote in the taxi home yesterday night:

#generate vectors
zprobs=c(.1,.9) #iid example
#estimated original size

A broader question is how many values (and which values) of the sample can be removed before this recovery gets impossible (with the same amount of information).

Le Monde puzzle [#937]

Posted in Books, R with tags , , , , on November 11, 2015 by xi'an

A combinatoric Le Monde mathematical puzzle that resembles many earlier ones:

Given a pool of 30 interns allocated to three person night-shifts, is it possible to see 31 consecutive nights such that (a) all the shifts differ and (b) there are no pair of shifts with a single common intern?

In fact, the constraint there is very strong: two pairs of shift can only share zero or two interns. For one given shift, there are 26 other shifts with which it can share two interns, but then any two of those 26 others must share zero or two, which makes the two common to all and exclude any additional shift. But this is not the only approach to allocate the interns over the shifts since, as pointed out by Jean-Louis and checking with the following R code, 28 and not 27 is the maximum possible number of shifts under those conditions.


while (((length(acpt)==1)+(length(acpt==3)))>0){
for(i in 3:31){
  for (j in 2:(i-1))
  while ((acpt>0)&(k<4061)){
    for (j in 2:(i-1))
  if (k==4061) break()

Continue reading

Le Monde puzzle [#934]

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

Another Le Monde mathematical puzzle with no R code:

Given a collection of 2€ coins and 5€ bills that sum up to 120€, find the number of 5€ bills such that the collection cannot be divided into 5 even parts.

Indeed, as soon as one starts formalising the problem, it falls apart: if there are a 5€ bills and b 2€ coins, we have 5a+2b=120, hence 2b=120-5a=5(24-a), meaning that b must be a multiple of 5, b=5b’ and a must be even, a=2a’, with b’=12-a’.  Hence, 10 possible values for both pairs (a’,b’) and (a,b), since a>0 and b>0. If these 120 Euros can be evenly divided between 5 persons, each gets 24€. Now, 24€ can be decomposed in 5€ bills and 2€ coins in three ways:


Each of the five persons using any of the 3 above decompositions means there exist integers α, β, and γ such that


with α+β+γ=5; therefore a=4α+2γ and b=2α+12β+7γ, which implies 2α+γ=a’ and 2α+12β+87γ=5×12-5a’=2α+5×12-12α-12γ+7γ, or 5a’=10α+5γ. That is, 2α+γ=a’ again… If a’=11, there is no solution with α+γ≤5, and this is the only such case. For any other value of a’, there is a way to divide the 120€ in 5 even parts. As often, I wonder at the point of the puzzle if this is the answer or at its phrasing if I have misunderstood the question.

Just to check the above by R means, I still wrote a short R code

for (a in 1:11){
# find integer solutions to 2x+y=a
  while ((z<a)&(z<6)&(sum<2)){

which returned

[1]  2 50  0  4  1
[1]  4 45  1  4  0
[1]  6 40  1  3  1
[1]  8 35  2  3  0
[1] 10 30  2  2  1
[1] 12 25  3  2  0
[1] 14 20  3  1  1
[1] 16 15  4  1  0
[1] 18 10  4  0  1
[1] 20  5  5  0  0
[1] 22  0  5 -1  1

meaning that a’=11 does not produce a viable solution.

Le Monde sans puzzle #933

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

While Le Monde mathematical puzzle is purely geometric this week

If twelve points in a plane are such that, for any 5-uplet of those, at least 4 are on the same circle, and if M is the largest number of those points on the same circle, what is the minimal value of M?

and not straightforward to solve with an R code, there are several entries of interest in the Sciences and Medicine leaflet. One about capture-mark-recapture: making fun of a PLOS One paper on a capture-recapture study about the movements of bed bugs in New Jersey apartments. Another one on the resolution by Terry Tao of Erdös’ discrepancy conjecture. Which states that. for any (deterministic) sequence f:N{1,+1} taking values in {1,+1}, the discrepancy of f is infinite, when the discrepancy is defined as

\sup_{n,d} \left|\sum_{j=1}^n f(jd)\right|

The entry in Le Monde tells the story of the derivation of the result and in particular the role of the Polymath5 project launched by Tao. It is interesting it is such a hard problem when considering the equivalent for a random sequence, which is more or less the gambler’s ruin result of Huygens. And a third entry on the explosion of the predatory journals, which publish essentially every submission in open access provided the authors accept to pay “charges”. And borrow titles and formats from existing reviews to a point where they can fool authors…

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:

#pick a subset at random
for (i in 2:8){

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

Le Monde puzzle [#930]

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

A game Le Monde mathematical puzzle:

On a linear board of length 17, Alice and Bob set alternatively red and blue tokens. Two tokens of the same colour cannot sit next to one another. Devise a winning strategy for the first player.

In the ‘Og tradition, this calls for a recurrent R code:

   # stopping rule
   if (sum(tak==col)==0){
     for (i in (1:n)[tak!=-col])
   # left positions
   if (sum(frei)>0){
     for (i in (1:n)[frei==1]){
   # outcome of best choice

While I did not run the rudimentary recursive function for n=17, I got a zero return from n=2 till n=12, meaning that the starting player is always going to lose if the other player plays optimally.

Le Monde puzzle [#929]

Posted in Books, Kids, R with tags , on September 29, 2015 by xi'an

A combinatorics Le Monde mathematical puzzle:

In the set {1,…,12}, numbers adjacent to i are called friends of i. How many distinct subsets of size 5 can be chosen under the constraint that each number in the subset has at least a friend with him?

In a brute force approach, I tried a quintuple loop to check all possible cases:

for (a in 1:(12-4))
for (b in (a+1):(12-3))
for (c in (b+1):(12-2))
for (d in (c+1):(12-1))
for (e in (d+1):12)

which returns 64 possible cases. Note that the second and last loop are useless since b=a+1 and e=d+1, necessarily. And c is either (b+1) or (d-1), which means 2 choices for c, except when e=a+4. This all adds up to

8 + 2\sum_{a=1}^7\sum_{e=a+5}^{12} = 8+2.7.8-2.7.8/2=8.8=64

A related R question: is there a generic way of programming a sequence of embedded loops like the one above without listing all of the loops one by one?


Get every new post delivered to your Inbox.

Join 946 other followers