Le Monde puzzle [#958]

A knapsack Le Monde mathematical puzzle:

Given n packages weighting each at most 5.8kg for a total weight of 300kg, is it always possible to allocate these packages  to 12 separate boxes weighting at most 30kg each? weighting at most 29kg each?

This can be checked by brute force using the following R code

#generate packages
paca=runif(1,0,5.8)
while (sum(paca)<300){ 
  paca=c(paca,runif(1,0,5.8))} 
paca=paca[-length(paca)] 
paca=c(paca,300-sum(paca)) 

and

#check if they can be partitioned into 
#12 groups of weight less than 30 
box=vector(mode="list",length=12) 
#random allocation 
alloc=sample(1:12,length(paca),rep=TRUE) 
content=rep(0,12) 
for (i in 1:12){ 
box[[i]]=paca[alloc==i] 
content[i]=sum(box[[i]])} 
content=content*(content>0) 
#wrong allocation 
 while (max(content)>30){
  i=sample(1:12,1,prob=content)
  j=sample(1:length(box[[i]]),1,prob=box[[i]])
#reallocation
  k=sample(1:12,1,prob=max(content)-content)
  while (k==i){
    k=sample(1:12,1,prob=max(content)-content)}
  content[i]=content[i]-box[[i]][j]
  content[i]=content[i]*(content[i]>0)
  content[k]=content[k]+box[[i]][j]
  box[[k]]=c(box[[k]],box[[i]][j])
  box[[i]]=box[[i]][-j]}

repeatedly and could not find an endless while loop. (Empty boxes sometimes lead to negative contents, hence my fix setting negative contents to zero.) But neither did I find an issue when the upper bound on the weight is 29kg… So it is either possible or rarely impossible! The R code immediately gets stuck when setting the bound at 25kg.

After reading the solution of April 13 in Le Monde, it appears that there is a counter example for the 29kg limit, namely 60 packages weighting 4.91kg plus one package weighting 5.4kg, since the first 60 packages fit inside 12 boxes and the last one is left out.

2 Responses to “Le Monde puzzle [#958]”

  1. Luca Scrucca Says:

    Here is a possible solution using Genetic Algorithms:

    # generate packages
    set.seed(123)
    paca = runif(1,0,5.8)
    while(sum(paca) < 300)
    { paca = c(paca, runif(1,0,5.8)) }
    paca = paca[-length(paca)]
    paca = c(paca,300-sum(paca))
    n = length(paca) # 104 packages generated
    weightBox = 30 # constraint on the maximum weight of a box
    # fitness function to optimise
    knapsack <- function(x)
    {
    x = floor(x) # assignment of packages to boxes (integer 1,…,12)
    w = tapply(paca, x, sum) # weight of each box
    wdiff = (w – weightBox)
    # penalised fitness function (more heavily max weight constraint violation)
    -sum(ifelse(wdiff < 0, abs(wdiff), 100*wdiff^2))
    }

    library(GA)
    GA = ga(type = "real-value",
    fitness = knapsack, min = rep(1,n), max = rep(13, n),
    maxiter = 1000, run = 200, popSize = 50)
    plot(GA)
    summary(GA)
    x = floor(GA@solution[1,])
    table(x) # allocation of packages in each box
    (w = tapply(paca, x, sum)) # weight of each box
    sum(w) # sum of all the boxes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s