<$BlogRSDURL$>

15.3.04

The Miller and Donkey Problem - the reason of the discrepancy 

1. Introduction

Before explaining the reason of the existent discrepancy between both the analytical and the computer solutions let me first to develop an alternative and more elementary approach for the problem.

2. An alternative solution

Suppose that the home-mill path is a coordinate line divided in n equal parts or segments, as shown in the Fig. 1.

y(0).......... y(1)..........y(2)...........................................y(k-1)..........y(k)
I---------------I---------------I.................................................I--------------I
0..............1...............2..............................................k-1.............k

Fig. 1

where the terms y(0), y(1), y(2), ......... y(k-1), y(k) are the remaining amounts of wheat at the the endpoints along of the x path, and 0, 1, 2,......., k-1, k are the respective term numbers, being k a nonnegative integer.

Our goal is to maximize the wheat amount to arrive at the mill. For such a purpose it is nedeed to imagine the path divided in n segments and to assume one adequate strategy. According to this the donkey must carry one bag of 100 kg each time, as it is possible, and perform a determinate number of reciprocating motions between the endpoints of the 1st segment until the rest (r) at the origin is zero.*

The method must be repeated for the remaining segments.

It is intuitively clear that the smaller the segments the greater the wheat amount to arrive at the mill and the better the degree of accuracy of the approximation.

If n---> infinity then y(k) tends toward a limit. Such a limit give us the maximum amount of weat and wich can be evaluate by a formula. The next section should be concerned with that.


3. Some terminology

In theory, we can imagine the donkey like a particle that in each infinitesimal segment executes a determined number of goings and comings, similar to the motion of a piston. For our purpose the coming motions do not interest since while they are occurring the donkey eats nothing.

Therefore, in this approach, we shall only consider as trips the forwards motions.

Let

p(k) and p(k+1) = the endpoints of an arbitrary segment;

b = a bag containing 100 kg of wheat;

y(k) = the remaining amount of wheat at p(k);

To move y(k) from p(k) into p(k+1) the donkey has to perform a determined number of trips (goings), subtracting 100 kg at a time, if possible, until the remainder is zero.

So

y(k) = g b

Consequently

(1) g = y(k) / b

where g = number of goings perfomed by the donkey along any arbitrary segment.

The remainder is usually defined by the following equation:

(2) r = y(k) - g b

In general, y(k) and g, both the one and the other rapidly become decimal numbers as according to the divisional process advances even if n is a small number. Consequently in this approach the donkey ends always performing a noninteger number of trips in the great majority of the segments.

For instance, let us consider the path (100 km) divided in 5 equal parts of 20 km. According to the formula y(k) = yo (1 - 1/ n)^k we can elaborate the following table:

Table I

endpoints.............amounts in kg...........trips

p(0)........................10 000...................100
p(1)......................... 8 000...................80
p(2)..........................6 400...................64
p(3)..........................5 120...................51,2
p(4)..........................4 096...................40,96
p(5)..........................3 276,8................32,768

It must be noted that the donkey unloads 80 kg/ trip.

As shown in the table above we can see that there is a segment where the donkey executes 51,2 goings. Decomposing the number we get 51 goings + 0,2 of a going. The fractional part of the number means that the remainder arrives at 0,2x20 km, that is, 4 km beyond the origin of the 4 th segment. In other words: the donkey is at 16 km's distance from the next endpoint where is the mount of the bags. As the animal has already eaten 4 kg it means that the remaining portion became in 16 kg. Taking into consideration that 16 km is a distance to cover it follows that the donkey arrives at the next point with zero kg. So the donkey finishes unloading 51x80 kg at the end of the 4 th segment, that is, 4080 kg and not 4096 kg.

However the formula implies that the remainder portion (16 kg) is added to the mount of bags.

It is easy to see that such a proceeding is mathematically incorrect since to get the next endpoint the donkey has to eat 1 kg/km, that is, 16 kg. This wheat amount must no be added to the bags in no way. Being added it goes to contribute for the increase of the final result. In reality, the amount to be added to the bags should be zero. This fact is happened again throughout other segments and explains the error in the aproximation.

Here it is the reason because both the analytic and algebraic results exceed the correct value in 0,86%.

In the last analysis, the fractionary parts of the quotients are the great responsibles for the inaccuracy of the formula y = yo/e.

4. How do we get Yo/e ?

Let

n = number of parts dividing the path
Yo = initial amount of wheat at the origin
g = number of trips (goings)
b= bag containing 100 kg of wheat
c = rate constant meanig the fractional loss of mass per unit length
p = amount of wheat that the donkey eats in the 1st segment in g trips
y(1) = amount of wheat that the donkey unloads at the end of the 1st segment in g trips
y(2) = amount of wheat that the donkey unloads at the end of the 2nd segment in g trips
y(k) = amount of wheat that the donkey unloads at the end of the kth segment in g trips

In the first segment the donkey will have eaten

p = (c b/n) (Yo/b)

Since c = 1 kg/1 km we have after simplifying:

p = Yo/n

If Yo/n is the amount of wheat that the donkey eats in the 1st segment then the amount unloaded by the animal must be

y(1) = Yo - Yo/n

Factoring we have

y(1) = Yo (1-1/n)

y(1) = Yo(1-1/n)^1

Similarly, for the 2nd segment:

Y(2) = (Yo - Yo/n) - (Yo - Yo/n)/n

Y(2) = Yo(1-1/n) (1-1/n)

Y(2) = Yo(1-1/n)^2

generalizing we get

(4) y(k) = yo (1 - 1/ n)^k

where

k = term number
n = total number of parts dividin the path
Yo = initial amount with x = 0
y(k) = amount of wheat that the donkey unloads at the end of the kth segment in g trips

When the donkey arrives at the mill k = n so that (4) becomes

(5) y(n) = yo (1 - 1/ n)^n

Since lim (1-1/n)^n is pratically equal to

(6) lim (1+1/n)^- n as n ---> infinite

and knowing that (6) is equal to e^-1 we can conclude that

(7) (1 - 1/ n)^n = e^-1

if n ---> infinity

Substituting (1-1/n) by e^-1 into (4) we get

y(n) = Yo e^ - 1

If n---> infinity

or

y(n) = Yo / e

If n ---> infinity

wich is precisely the equation we have obtained in the first approach.

5. In summary

Analytic general solution: y(x) = Yo e^- (x/s)

Analytic particular solution: y(s) = Yo/e

Algebraic general solution: y(k) = yo (1 - 1/ n)^k

Algebraic particular solution: y(n) = Yo/e

Note 1: The algebraic equations imply that k and n ---> infinity.
Note 2: Both the analytic and the algebraic solutions are approximations with an error < 0,86%.

6. Solution of the problem by computational programming

As we could see till now there is no formula to give an exact result for this problem. As far as I know the exact solution can only be obtained by a computer program. I tried some programs and all of them led to the same result.

For example, the table I in section 3 should have the following aspect:

Table II

endpoints.............amounts in kg...........trips

p(0)........................10 000...................100
p(1)......................... 8 000...................80
p(2)..........................6 400...................64
p(3)..........................5 120...................52
p(4)..........................4 080...................41
p(5)..........................3 260..................33

In this case, for n = 5, the donkey arrives at the mill with 3 260 kg, that is, less 16,8 kg than the value obtained in the table I.

If n = 10^10 parts then the round result is equal to 3 647,428 kg.

difference: less 31,366 kg than the analytic result.


7. APPENDIX: Pascal program

7.1 Some values obtained by the program

n parts..................................... Amount of wheat in kg

..10.............................................3 470
..100............................................3 627
..1 000..........................................3 645,6
..10 000.........................................3 647,24
..100 000........................................3 647,409
..1 000 000......................................3 647,425 899 999 997 300
..10 000 000.....................................3 647,427 600 000 004 460
..100 000 000....................................3 647,427 767 999 870 130
..1000 000 000...................................3 647,427 785 408 556 700
..10 000 000 000.................................3 647,427 786 904 417 320

7.2 Conclusion

From 7.1 we can conclude that the correct solution of the problem is 3 647,428 kg

7.3 Pascal program

It follows a Pascal program written by Jaime Gaspar, a student of maths, at Lisbon University:

----- Início do código fonte -----

{$N+}
program Ciclotrao;

uses Crt;

var
m: Extended; { Valor corrente da sucessao }
batidas: Longint absolute 0:$46C; { Numero de batidas do relogio }
batidas_i, { Instante em que se inicia o
calculo }
batidas_f, { Instante em que termina o
calculo }
p: LongInt; { Numero de intervalos }
{============================================================================}
{ Le as opcoes do programa }
procedure Opcoes;
begin
repeat { Repete o input ate' que seja valido }
Write('Introduza o numero de milhares de intervalos: ');

ReadLn(p);
if p < 1 then
begin WriteLn('Tem de escolher um inteiro maior que 0.');
end;
until p >= 1;
end;
{============================================================================}
{ Funcao ceil(x) = menor inteiro maior ou igual a x }
function ceil(x: Extended): LongInt;
begin
if x = Trunc(x) then ceil := Trunc(x)
else ceil := Trunc(x) + 1;
end;
{============================================================================}
{ Calcula o valor de m_p }
procedure Calcular;
var
i : LongInt; { Variavel de controlo de um ciclo }
divisao: Extended; { Variavel auxiliar }
begin
WriteLn('A calcular...');
batidas_i := batidas; { Regista o instante em que se inicia o
calculo }

m := 10000; { Define o valor inicial m_0 }
divisao := 100 / p;

for i := 1 to p do { Calcula m_p por recorrencia }
m := m - divisao * ceil(m / 100);

batidas_f := batidas; { Regista o instante em que termina o calculo
}
end;
{============================================================================}
{ Apresenta o resultado }
Procedure Resultado;
begin
{ Apresenta o resultado do calculo }
WriteLn('Resultado: ', m:18:18);

{ Apresenta o tempo de calculo }
WriteLn('Tempo de calculo: ', Round(0.055 * (batidas_f -
batidas_i)), ' s');

WriteLn('Pressione qualquer tecla para terminar...')
end;
{============================================================================}
{ Apresenta os creditos }
procedure Creditos;
begin
GotoXY(68, 1); Write('Ciclotrao 1.1');
GotoXY(67, 2); Write('(simplificado)');
GotoXY(69, 3); Write('Jaime Gaspar');
GotoXY(62, 4); WriteLn('www.jaimegaspar.com');
end;
{============================================================================}
{ Espera que o utilizador pressione uma tecla para continuar }
procedure Pausa;
begin
repeat until KeyPressed;
ReadKey; { Limpa a tecla da memoria }
if KeyPressed then ReadKey; { Se ainda restar uma tecla, limpa-a }
end;
{============================================================================}
begin;

ClrScr;
Opcoes;
Calcular;
Resultado;
Creditos;
Pausa;

end.

----- Fim do código fonte -----


Email: manuelcruzsousa@sapo.pt

Comments: Enviar um comentário

This page is powered by Blogger. Isn't yours?