[seqfan] Re: two jug problem
Dmitry Kamenetsky
dmitry.kamenetsky at rsise.anu.edu.au
Sun Aug 15 14:55:38 CEST 2010
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/
>
More information about the SeqFan
mailing list