Archive for knapsack problem

Le Monde puzzle [#1053]

Posted in Books, Kids, R with tags , , , , , , , on June 21, 2018 by xi'an

An easy arithmetic Le Monde mathematical puzzle again:

  1. If coins come in units of 1, x, and y, what is the optimal value of (x,y) that minimises the number of coins representing an arbitrary price between 1 and 149?
  2.  If the number of units is now four, what is the optimal choice?

The first question is fairly easy to code

coinz <- function(x,y){
  z=(1:149)
  if (y<x){xx=x;x=y;y=xx}
  ny=z%/%y
  nx=(z%%y)%/%x
  no=z-ny*y-nx*x
  return(max(no+nx+ny))
}

and returns M=12 as the maximal number of coins, corresponding to x=4 and y=22. And a price tag of 129.  For the second question, one unit is necessarily 1 (!) and there is just an extra loop to the above, which returns M=8, with other units taking several possible values:

[1] 40 11  3
[1] 41 11  3
[1] 55 15  4
[1] 56 15  4

A quick search revealed that this problem (or a variant) is solved in many places, from stackexchange (for an average—why average?, as it does not make sense when looking at real prices—number of coins, rather than maximal), to a paper by Shalit calling for the 18¢ coin, to Freakonomics, to Wikipedia, although this is about finding the minimum number of coins summing up to a given value, using fixed currency denominations (a knapsack problem). This Wikipedia page made me realise that my solution is not necessarily optimal, as I use the remainders from the larger denominations in my code, while there may be more efficient divisions. For instance, running the following dynamic programming code

coz=function(x,y){
  minco=1:149
  if (x<y){ xx=x;x=y;y=xx}
  for (i in 2:149){
    if (i%%x==0)
      minco[i]=i%/%x
    if (i%%y==0)
      minco[i]=min(minco[i],i%/%y)
    for (j in 1:max(1,trunc((i+1)/2)))
          minco[i]=min(minco[i],minco[j]+minco[i-j])
      }
  return(max(minco))}

returns the lower value of M=11 (with x=7,y=23) in the first case and M=7 in the second one.

Le Monde puzzle [#1022 & #1023]

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

Another Le Monde mathematical puzzle where I could not find a solution by R programming (albeit one by cissors and papers was readily available!):

An NT is a T whose head () is made of 3 50×50 squares and whose body (|) is made of N 50×50 squares.  What is the smallest possible side of a square containing four non-intersecting NT’s when N=1,2,4? And what is the smallest value of N such that this square also contains a fifth NT?

The questions could have been solved by brute force simulation (or a knapsack algorithm?!) but I could not fathom an efficient way to code throwing T’s at random over an MxM grid.So instead I took scissors and paper and tried to fit four 1T, 2T, and 4T into the smallest squares, ending up with 4×4, 5×5, and 7×7 squares. Interestingly, four 5T also fit in a 7×7 square. And a 9×9 square accommodates the extra 7T. Compared with the  “impossible” puzzle of last week, this is pretty anticlimactic..! (Actually, once the solutions were published, I realised the square containing the T’s did not have to be with integer side. Which means the smallest square for 3Ts was incorporating the glued T’s sideway. Fortunately, this did not impact the answer for the 7T’s!)

Going back to this “impossible” puzzle, the posted solution is somewhat… puzzling in that the resolution posits that the majority rule is the optimal allocation, when I am not sure it is [optimal]. Just because, when rerunning the same R code, I found instances when the minimal acceptable number of councillors was lower than the one returned by the majority rule.

And since this post get pushed down in the queue, here is as a bonus the equally anticlimactic puzzle #1023,

Find (a) a multiplication of two three-prime-digit numbers such that all digits everywhere in the long multiplication are prime and all three intermediary products have four prime digits, while the final result has six prime digits, and (b) a multiplication of two three-digit numbers such that the digits of the first one are odd (o), the digits of the second are even (e), the three intermediary products are all of the form eoe, and the final product is of the form eoeo. [The website has two pictures to help if this description is too unclear!]

This is indeed straightforward to code with one solution to (a) and two to (b) since the number of cases to examine is quite limited.

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 [#958]

Posted in Books, Kids, R with tags , , , on April 11, 2016 by xi'an

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.