[seqfan] Re: two jug problem

[Dmitry Kamenetsky]

Hello Doug and Charles,

Thank you for your feedback. I decided to separate this into a few
Triangular arrays T(A,B), one for each N. Below is an example for N=1. Does
the description make sense?

%I A000001
%S A000001 1,2,1,2,2,1,2,1,2,1,2,4,6,2,1,2,1,1,1,2,1,2,6,4,6,10,2,1,2,
%T A000001 1,8,1,8,1,2,1,2,8,1,4,6,1,14,2,1,2,1,6,1,1,1,10,1,2,1
%V A000001
1,2,-1,2,2,-1,2,-1,2,-1,2,4,6,2,-1,2,-1,-1,-1,2,-1,2,6,4,6,10,2,-1,2,
%W A000001
-1,8,-1,8,-1,2,-1,2,8,-1,4,6,-1,14,2,-1,2,-1,6,-1,-1,-1,10,-1,2,-1
%N A000001 Triangular array T(A,B) read by rows: minimal number of steps
required to obtain exactly 1 litre in jug A (irrespective of jug B),
starting with infinite supply of water and two empty jugs with capacities A
and B litres. -1 if not possible. A>=B>=1. 
%C A000001 In the two jug problem we are given an infinite supply of water
and two empty jugs with integer litre capacities A and B, A>=B>=1. We must
use the least number of steps to measure exactly N integer litres of water
in jug A, irrespective of jug B. Each step is one of the following: empty a
jug, fill a jug, or pour from one jug to the other. Pouring stops as soon as
the source jug is empty or the destination jug is full. It is known that the
amount N can be made if only if N is a multiple of gcd(A,B). 
%H A000001 1997 ACM South Central USA programming contest, [Problem and Code

%H A000001 Wolfram Mathworld, Three Jug Problem ->
http://www.ntnu.edu.tw/acm/ProblemSetArchive/B_US_SouthCen/1997/Jugs.html] 
%e A000001 Triangle begins:
%e A000001 1
%e A000001 2,-1
%e A000001 2,2,-1
%e A000001 2,-1,2,-1
%e A000001 2,4,6,2,-1
%e A000001 2,-1,-1,-1,2,-1
%e A000001 2,6,4,6,10,2,-1
%e A000001 2,-1,8,-1,8,-1,2,-1
%e A000001 2,8,-1,4,6,-1,14,2,-1
%e A000001 2,-1,6,-1,-1,-1,10,-1,2,-1 
%K A000001 nonn
%O A000001 1,2
%A A000001 Dmitry Kamenetsky (dkamen(AT)rsise.anu.edu.au), Aug 15 2010


Cheers,
Dmitry
 
----------------original message-----------------
From: "Douglas McNeil" mcneil at hku.hk
To: "Sequence Fanatics Discussion list" seqfan at list.seqfan.eu
Date: Mon, 9 Aug 2010 12:21:52 +0800
-------------------------------------------------
 
 
> I like it too, and think I can confirm the values. But it might be
> worth being more explicit about what you mean by to measure exactly N
> integer litres of water: IIUC, to have N litres in jug A irrespective
> of B. I'd originally allowed jug B as well (making it a little
> easier), and required the other jug to be empty (for no real reason
> except tidiness).
> 
> 
> Doug
> 
> --
> Department of Earth Sciences
> University of Hong Kong
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
>