Puzzle solving with solver

[Dinesh]

I used solver to solve a mathemathical puzzle but it is not giving the sam
answer everytime. I can mail the excel file to anyone who can help. Anyone
willing to help may please give your email address.

 

[Harlan Grove]

Dinesh wrote...

I used solver to solve a mathemathical puzzle but it is not giving the sam
answer everytime. I can mail the excel file to anyone who can help. Anyone
willing to help may please give your email address.

If there are multiple feasible solutions or the problem depends on
volatile functions, there's no guarantee Solver will always arrive at
the same solution.

That said, please don't consider this an invitation to e-mail your file
to me. Just describe the problem in plain text.

 

[Dinesh]

The puzzle goes like this. Try to solve it with solver.
3 Robbers rob some mangoes. Since the mongoes are green, they hide it at one
place for ripening and decide to meet after 10 days for equal distribution.
However on the 5th day first robber comes to the place alone and divides all
the mongoes into 3 equal shares. After division there remains one mongo extra
which he eats and goes away taking one part of the share. Now there remains
two shares only. On the 6th day second robber comes to the place alone and
divides the remaining mongoes again into 3 equal shares. After division there
remains one mongo which he eats and goes away taking one part of the share.
Now there remains again two shares only. Then on the 7th day third robber
comes to the place alone and divides the remaining mongoes again into 3 equal
shares. After division there remains one mongo extra which he eats and goes
away taking one part of the share. Now again there remains two shares only.
On the 10th day all the three come, divide the reamaining mangoes equally
into 3 shares. Each one takes their own share and goes away. So what was the
initial quantity of mangoes?

Now this puzzle has many solutions ie for the initial quantity. So I
specified the maximum and minimum values for this in constraints by
specifying these numbers in two different cells. So when I give the
constraints for the initial quantity of mangoes ie min 100 and maximum 120,
I should get answer as 116 which fits the equations. But solver says it did
not find a feasible solution. However if I put the maximum as 200 and minimum
as 100 solver gives answer as 116. Why is it so?

 

[Dana DeLouis]

I should get answer as 116 which fits the equations.

I may be wrong, but on the first division...

38*3+1 = 115
or
39*3+1 = 118

I don't show 116 as a possible solution.
Again, I may not have understood the question.
Or did you mean 106, as that's a possible solution?

With Solver, if your model is set up with a lot of equality constraints (ie
x = y)
you may be having problems with precision. Solver's "Integers" are not true
integers, but close.
Solver may not be recognizing that x=y due to precision.
You may want to start by going to Solver's options, and increasing both
Tolerance & Precision.

 

[Tushar Mehta]

Obviously, I don't know how much you know about the method Solver uses
to solve these kinds of problems. But, if you specify the problem in a
way that constitutes what is called a "linear model," Solver will work
much better. One way to ensure Solver knows you want to use a linear
model is the check the 'Assume linear model' checkbox in Solver's Option
dialog box. [If Solver disagrees with you claim of a linear model, it
will let you know.]

Suppose you set up your problem as follows:

In col. A starting with A1 enter:
After robbery, the total is p
After 1st robber split, the total is q
After 2nd robber split, the total is r
After 3rd robber split, the total is s
After final split, each individual gets t

Then, the equations you need to solve are:
q=2/3*(p-1)
r=2/3*(q-1)
s=2/3*(r-1)
s=3*t
where each of p,q,r,s, and t is an integer.

Clearly, the above can be reduced to a single equation in 2 unknowns, p
and t. So, yes, there will be an infinite number of solutions.

To create the model in XL, in col. B starting with B2 enter
=2/3*(B1-1)
=2/3*(B2-1)
=2/3*(B3-1)
=B4/3

We will also store the min. allowed value for the starting quantity, p,
in D1 and the max. allowed quantity in F1.

Typically, in Solver we cannot specify intermediate results (calculated
values) as being constrained as integer. And, using the MOD() or INT()
function to enforce an integer constraint will make the model non-
linear. So, we simulate the effect by creating several dummy variables,
each of which is constrained as integer, and ensuring that they equal
the corresponding intermediate result.

So, we designate C2:C5 as the dummy variables. In D2 enter =B2-C2 and
copy D2 down to D35.

Now, we can create the Solver model.

There is *no* optimization value. Leave the 'Set Target Cell' empty.

The 'By changing cells' are B1, C2:C5. The constraints are
B1, C2:C5 are integer,
B1 <= F1,
B1 >= D1
D25=0

In the Solver dialog box, click the Options button. In that dialog box,
check the 'Assume Linear Model' box and the 'Assume non-negative' box.

If you duplicated the problem as described above, you can load the
complete Solver model by saving the below in the an empty range of the
worksheet and loading it through the 'Load Model' button of the Solver
Options dialog box.

=COUNT($B$1,$C$2:$C$5)
=$B$1=INT($B$1)
=$C$2:$C$5=INT($C$2:$C$5)
=$D$2:$D$5=0
=$B$1<=Sheet2!$F$1
=$B$1>=Sheet2!$D$1
={100,100,0.000001,0.05,TRUE,FALSE,FALSE,1,1,1,0.0001,TRUE}

And, yes, the above works just fine with 100 <= p <= 120.
--
Regards,

Tushar Mehta
www.tushar-mehta.com
Multi-disciplinary business expertise
+ Technology skills
= Optimal solution to your business problem
Recipient Microsoft MVP award 2000-2005

 

[Dana DeLouis]

Just to add for your testing. Solving equations, I show a minimum solution
of 25, with differences of 27 for each solution. (ie 25+27*n)
The following would be valid solutions...
{25, 52, 79, 106, 133, 160, 187, 214, 241 ...ect}

--
HTH :>)
Dana DeLouis
Windows XP & Office 2003

I may be wrong, but on the first division...

38*3+1 = 115
or
39*3+1 = 118

I don't show 116 as a possible solution.
Again, I may not have understood the question.
Or did you mean 106, as that's a possible solution?

<snip>

 

[Tushar Mehta]

Hi Dana,

Looks like the OP has disappeared.

I interpreted the problem to include a requirement that the count left for
the final three-way split be an integer divisible by three. With that
additional requirement, the increments become 81 with the first feasible
value still 25.

Given the total initial quantity as p and the final individual share as t,
the relationship is p=81/8*t+19/4

--
Regards,

Tushar Mehta
www.tushar-mehta.com
Excel, PowerPoint, and VBA add-ins, tutorials
Custom MS Office productivity solutions

 

[Dana DeLouis]

Hi Tushar! Thanks. I did leave out that last requirement. Ahh.
I now get the same solution as you. Thanks for the catch. :>0
--
Dana DeLouis

Hi Dana,

Looks like the OP has disappeared.

I interpreted the problem to include a requirement that the count left for
the final three-way split be an integer divisible by three. With that
additional requirement, the increments become 81 with the first feasible
value still 25.

Given the total initial quantity as p and the final individual share as t,
the relationship is p=81/8*t+19/4

--
Regards,

Tushar Mehta
www.tushar-mehta.com
Excel, PowerPoint, and VBA add-ins, tutorials
Custom MS Office productivity solutions

<snip>

 

[Dinesh]

Hi Tushar and Dana,

The equation derived by tushar seems to be correct. I ll try and
get back.

Dinesh

 

[Dinesh]

Hi, Tushar and Dana,

The equation derived by Tushar seems to be the right one. Let
me try this one and get back to you.

Dinesh

 

[Dinesh]

Hi Tushar,
Thanks very much for the reply. One thing I learned that
we can work without specifying the target cell. I loaded the model given by
you along with the max and min values. But I got the reply as solver could
not find a feasible solution. Is it that I might have missed something while
entering? Can you foward me the excel file in which you have solved the
problem?

Dinesh

Obviously, I don't know how much you know about the method Solver uses
to solve these kinds of problems. But, if you specify the problem in a
way that constitutes what is called a "linear model," Solver will work
much better. One way to ensure Solver knows you want to use a linear
model is the check the 'Assume linear model' checkbox in Solver's Option
dialog box. [If Solver disagrees with you claim of a linear model, it
will let you know.]

Suppose you set up your problem as follows:

In col. A starting with A1 enter:
After robbery, the total is p
After 1st robber split, the total is q
After 2nd robber split, the total is r
After 3rd robber split, the total is s
After final split, each individual gets t

Then, the equations you need to solve are:
q=2/3*(p-1)
r=2/3*(q-1)
s=2/3*(r-1)
s=3*t
where each of p,q,r,s, and t is an integer.

Clearly, the above can be reduced to a single equation in 2 unknowns, p
and t. So, yes, there will be an infinite number of solutions.

To create the model in XL, in col. B starting with B2 enter
=2/3*(B1-1)
=2/3*(B2-1)
=2/3*(B3-1)
=B4/3

We will also store the min. allowed value for the starting quantity, p,
in D1 and the max. allowed quantity in F1.

Typically, in Solver we cannot specify intermediate results (calculated
values) as being constrained as integer. And, using the MOD() or INT()
function to enforce an integer constraint will make the model non-
linear. So, we simulate the effect by creating several dummy variables,
each of which is constrained as integer, and ensuring that they equal
the corresponding intermediate result.

So, we designate C2:C5 as the dummy variables. In D2 enter =B2-C2 and
copy D2 down to D35.

Now, we can create the Solver model.

There is *no* optimization value. Leave the 'Set Target Cell' empty.

The 'By changing cells' are B1, C2:C5. The constraints are
B1, C2:C5 are integer,
B1 <= F1,
B1 >= D1
D25=0

In the Solver dialog box, click the Options button. In that dialog box,
check the 'Assume Linear Model' box and the 'Assume non-negative' box.

If you duplicated the problem as described above, you can load the
complete Solver model by saving the below in the an empty range of the
worksheet and loading it through the 'Load Model' button of the Solver
Options dialog box.

=COUNT($B$1,$C$2:$C$5)
=$B$1=INT($B$1)
=$C$2:$C$5=INT($C$2:$C$5)
=$D$2:$D$5=0
=$B$1<=Sheet2!$F$1
=$B$1>=Sheet2!$D$1
={100,100,0.000001,0.05,TRUE,FALSE,FALSE,1,1,1,0.0001,TRUE}

And, yes, the above works just fine with 100 <= p <= 120.
--
Regards,

Tushar Mehta
www.tushar-mehta.com
Multi-disciplinary business expertise
+ Technology skills
= Optimal solution to your business problem
Recipient Microsoft MVP award 2000-2005

The puzzle goes like this. Try to solve it with solver.
3 Robbers rob some mangoes. Since the mongoes are green, they hide it at one
place for ripening and decide to meet after 10 days for equal distribution.
However on the 5th day first robber comes to the place alone and divides all
the mongoes into 3 equal shares. After division there remains one mongo extra
which he eats and goes away taking one part of the share. Now there remains
two shares only. On the 6th day second robber comes to the place alone and
divides the remaining mongoes again into 3 equal shares. After division there
remains one mongo which he eats and goes away taking one part of the share.
Now there remains again two shares only. Then on the 7th day third robber
comes to the place alone and divides the remaining mongoes again into 3 equal
shares. After division there remains one mongo extra which he eats and goes
away taking one part of the share. Now again there remains two shares only.
On the 10th day all the three come, divide the reamaining mangoes equally
into 3 shares. Each one takes their own share and goes away. So what was the
initial quantity of mangoes?

Now this puzzle has many solutions ie for the initial quantity. So I
specified the maximum and minimum values for this in constraints by
specifying these numbers in two different cells. So when I give the
constraints for the initial quantity of mangoes ie min 100 and maximum 120,
I should get answer as 116 which fits the equations. But solver says it did
not find a feasible solution. However if I put the maximum as 200 and minimum
as 100 solver gives answer as 116. Why is it so?