Exact Analysis of Exact Change.
We introduce the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using k disjoint subsets of the coins.  The goal is to minimize the number of coins for any given N and k, while allowing the actual payments to be made on-line, namely without the need to know all payment requests in advance. The problem is motivated by the electronic cash model, where each coin is a long bit sequence, and typical electronic wallets have only limited storage capacity.  The k-payment problem has additional applications in other resource-sharing scenarios.Our results include a complete characterization of the k-payment problem as follows.  First, we prove a necessary and sufficient condition for a given set of coins to solve the problem.  Using this characterization, we prove that the number of coins in any solution to the k-payment problem is at least k HN/k, where Hn denotes the nth element in the harmonic series. This condition can also be used to efficiently determine k (the maximal number of exact payments) which a given set of coins allows in the worst case. Secondly, we give an algorithm which produces, for any N and k, a solution with a minimal number of coins.  In the case that all denominations are available, the algorithm finds a coin allocation with at most (k+1)HN/(k+1) coins.  (Both upper and lower bounds are the best possible.) Finally, we show how to generalize the algorithm to the case where some of the denominations are not available.
Introduction
Consider the following everyday scenario. You want to withdraw N units of money from your
bank. The teller asks you "how would you like to have it?" Let us assume that you need to
have "exact change," i.e., given any payment request P - N , you should be able to choose a
subset of your "coins" whose sum is precisely P . Let us further assume that you would like
to withdraw your N units with the least possible number of coins. In this case, your answer
depends on your estimate of how many payments you are going to make. In the worst case, you
may be making N payments of 1 unit each, forcing you to take N coins of denomination 1. On
the other extreme, you may need to make only a single payment P . In this case, even if you
don't know P in advance, log coins are sometimes sufficient (as we explain later). In
this article, we provide a complete analysis of the general question, which we call the k-payment
problem: what is the smallest set of coins which enables one to satisfy any k exact payment
requests of total value up to N .
Motivation. In any payment system, be it physical or electronic, some transactions require
payments of exact amounts. Forcing shops to provide change to a customer, if she does not
possess the exact change, simply shifts the problem from the customers to the shops. The
number of coins is particularly important in electronic cash (see, e.g., [2, 3]), because electronic
coins are inherently long bit sequences and their handling is computationally intensive, while the
typical "smart-card" used to store them has small memory space and computational power [7].
Another interesting application of the problem arises in the context of resource sharing. For
concreteness, consider a communication link whose total bandwidth is N . When the link is
shared by time-multiplexing, there is a fixed schedule which assigns the time-slots (say, cells in
ATM lines) to the different connections. Typical schedules have small time slots, since assigning
big slots to small requests entails under-utilization. It is important to note, however, that there
is an inherent fixed overhead associated with each time slot (e.g., the header of an ATM cell).
It would be therefore desirable to have a multiplexing schedule (with time slots of various sizes)
which can accommodate any set of requests with the least number of slots. Similarly to the
withdrawal scenario, an improvement upon the trivial N unit-slot solution can be achieved, if
we know how many connections might be running in parallel. When we know a bound k on
this number, and if we restrict ourselves to long-lived connections, the problem of designing a
schedule naturally reduces to the k-payment problem.
The k-payment problem: Definition. Formally, the problem is as follows. There are two
parameters, the budget, denoted N , and the number of payments, denoted k. The problem is
to find, for each i - 1, the number of i-coins (also called coins of denomination i), denoted c i ,
such that the following two requirements are satisfied.
Budget compliance:
k-partition: For any sequence of k payment requests, denoted
N , there exists a way to exactly satisfy these payments using the coins. That is, there exist
non-negative integers represents the number of i-coins used in the j-th payment),
such that
The problem can thus be broken into two parts as follows. The coin allocation problem is to to
partition N into coins given N and k, i.e., determining the c i 's. The coin dispensing problem
is how, given the c i 's, to actually make a payment.
There are a few possible variants of the k-payment problem. First, in many systems, not all
denominations are available (for example, we do not know of any system with 3-coins). Even
in the electronic cash realm, denominations may be an expensive resource. (This is because
each denomination requires a distinct pair of secret/public keys of the central authority; see,
e.g., [1, 8].) Thus an interesting variant of the allocation problem is the restricted denominations
version, where the set of possible solutions is restricted to only those in which c
for a given allowed denomination set D.
Also, one may consider the on-line coin dispensing problem, where the algorithm is required
to dispense coins after each payment request, without knowledge of future requests, or the
off-line version, where the value of all k payments is assumed to be known before the first coin
is dispensed.
Results. It turns out that the coin dispensing problem is easy: the greedy strategy works,
even in the on-line setting. Most of our results concern the coin allocation problem, and we
sometimes refer to this part of the problem as the k-payment problem. Our basic result is a
simple necessary and sufficient condition for a sequence c 1 of coins to solve the allocation
problem (Theorem 3.1). Using this characterization, we prove (in Theorem 3.6) a lower bound
of kHN=k - k ln(N=k) on the number of coins in any solution for all N and k, where H n denotes
the nth element of the harmonic series. The lower bound is the best possible in the sense that it
is met with equality for infinitely many N 's and k's (Theorem 3.8). The characterization can be
used to efficiently determine the maximal number k for which a given collection of coins solves
the k payment problem (Corollary 3.9). Our next major result is an efficient algorithm which
finds a solution for any N and k using the least possible number of coins. We first deal with
the case where all denominations are allowed (Theorem 4.1). In this case the number of coins
is never more than (Theorem 4.7). Similarly to our lower bound, the upper
bound is the best possible in general (Theorem 4.8). Finally, using the same ideas in a slightly
more refined way, we extend the algorithm to the general case of restricted denomination set
(Theorem 5.1).
Related work. To the best of our knowledge, the current work is the first to formulate the
general k-payment problem, and hence the first to analyze it. One related classic combinatorial
problem is k-partition, where the question is in how many ways can a natural number N be
represented as a sum of k positive integers. This problem is less structured than the k-payment
problem, and can be used to derive lower bounds (however, these bounds are suboptimal: see
Section 2). The postage-stamp problem is also closely related: cast in our terms, the postage-
stamp problem is to find a set of denominations which will allow to pay any request of value
using at most h coins, so that N is maximized. The postage-stamp problem can
be viewed as an inverse of the 1-payment problem: there is one payment to make, the number of
coins is given, and the goal is to find a denomination set of a given size which will maximize the
budget. We remark that the postage-stamp problem is considered a difficult problem even for
a very small number of denominations. See, e.g., [10, 11, 4]. Another related question is change
making [6], which is the problem of how to represent a given budget with the least number
of coins from a given allowed denomination set. General change-making is (weakly) NP-hard.
Kozen and Zaks [5], and Verma and Xu [14], study the question of which denominations sets
allow one to use the greedy strategy for optimal change making.
Organization. In Section 2 we introduce notation, give some preliminary observations and
briefly discuss a few suboptimal results. In Section 3 we prove a characterization of the k-
payment problem and a lower bound on the number of coins in any solution. In Section 4 we
present and analyze an optimal algorithm for the unrestricted denomination case. In Section 5
we extend the algorithm for the case of restricted denominations. Finally, in Section 6 we give
a short overview of the applications of our results for electronic cash.
Notation and simple results
In this section we develop some intuition for the k-payment problem by presenting a few simple
upper and lower bounds on the number of coins required. The notation we shall use throughout
this article is summarized in Figure 1. The solution S to which the c
to should be clear from the context.
For the remainder of this article, fix N and k to be arbitrary given positive integers. Note
that we may assume without loss of generality that k - N , since payment requests of value 0
can be ignored.
Let us now do some rough analysis of the k-payment problem. As already mentioned above,
the case is trivial to solve: take c no better solution
is possible since c 1 ! k would not satisfy k payments of value 1 each. The case of
quite simple, at least when for an integer 1: we can solve it with
coins of denominations Given any request P , we can satisfy it by using the
coins which correspond to the ones in the binary representation of P .
However, it is not immediately clear how can one generalize this solution to arbitrary N and
k. Consider an arbitrary N : the usual technique of "rounding up" to the next power of 2 does
Parameters of problem specification:
the total budget.
ffl k: the number of payments.
ffl D: the set of allowed denominations. In the unrestricted case,
Quantities related to solution specification S:
the number of coins of denomination i (a.k.a. i-coins) in S. By convention,
the budget allocated in S using coins of denomination i or less. Formally,
ffl m: the largest denomination of a coin in S. Formally,
always.)
Quantities related to making a payment:
refer to the respective quantities after a payment has been made.
Standard quantities:
. By convention, H

Figure

1: Glossary of notation.
not seem appropriate in the k-payment problem: can we ask the teller of the bank to round up
the amount we withdraw just because it is more convenient for us? But let us ignore this point
for the moment, and consider the problem of general k. If we were allowed to make the dubious
assumption that we may enlarge N , then one simple solution would be to duplicate the solution
for 1-payment k times, and let each payment use its dedicated set of coins. Specifically, this
means that we allocate k 1-coins, k 2-coins, k 4-coins and so on, up to k 2 dlog 2
-coins.
The result is approximately k log 2 N coins, and the guarantee we have based on this simplistic
construction is that we can pay k payments, but for all we know each of these payments must
be of value at most N . However, the total budget allocated in this solution is in fact kN , and
thus it does not seem to solve the k-payment problem as stated, where the only limit on the
value of payments is placed on their sum, rather than on individual values.
As an aside, we remark that one corollary of our work (specifically, Theorem 3.1) is that
if coin dispensing is done using the greedy strategy (see below), then the above "binary"
construction for coin allocation indeed solves the general k-payment problem. More precisely,
highest possible denomination
use as many i-coins as possible
4 dispense j i-coins

Figure

2: The greedy algorithm for coin dispensing. P is the amount to be paid.
assume that a power of 2. Then the coin allocation algorithm allocates k coins of
each denomination
. Clearly, the number of coins is k log 2
and their sum is N . Coin dispensing is made greedily: at each point, the largest possible coin
is used. description of the greedy dispensing algorithm is presented in Figure 2.)
However, one should note that, perhaps surprisingly, our results also indicate that the binary
algorithm is not the right generalization for 1: the best algorithm (described in Section
yields a factor of about improvement, i.e., roughly 30% fewer coins.
Let us now re-consider the question of a general N . Once we have an algorithm for infinitely
many values of k and N , generalizing to arbitrary N and k is easy: find a solution for N 0 and
dispense a payment of value . The remaining set
of coins is a coin allocation of total budget N , and it can be used for k additional payments
since the original set solved the 1)-payment problem.
We close this section with a simple lower bound on the number of coins required in any
solution to the k-payment problem. The bound is based on a counting argument, and we only
sketch it here. For the number of distinct possible payment requests is
allowed). Observe that the algorithm must dispense a different set of coins in response to each
request. It follows that the number of coins in any solution must be at least log 2 (N 1).
This argument can be extended to a general k, using the observation that the number of
distinct responses of the algorithm (disregarding order), is at least p k (N ), the number of ways
to represent N as a sum of k positive integers. Using standard bounds for partitions (see, e.g.,
[13]), and since the number of responses is exponential in the number of coins, one can conclude
that the number of coins is \Omega\Gamma k log(N=k 2 )).
3 Problem characterization
In this section we first prove a simple condition to be necessary and sufficient for a set of coins
to correctly solve the k-payment problem. Using this result, we obtain a sharp lower bound on
the number of coins in any solution to the k-payment problem. Finally, we outline an efficient
algorithm which, given a set of coins S, determines the maximal k for which S is a solution of
the k-payment problem. Please refer to Figure 1 for notation.
3.1 A Necessary and sufficient condition
Theorem 3.1 S solves the k-payment problem if and only if T i - ki for all
The theorem is proven by a series of lemmas below. The necessity proof is not hard: the intuition
is that the "hardest" cases are when all payment requests are equal. The more interesting part
is the sufficiency proof. We start by upper bounding m, the largest denomination in a solution.
Lemma 3.2 If S solves the k-payment problem, then m - dN=ke :
Proof: By contradiction. Suppose m ? dN=ke, and consider k payments of values bN=kc and
dN=ke such that their total sum is N . Clearly, none of these payments can use m-coins, and
since c m - 1 by definition, the total budget available for these payments is at most N \Gamma m,
contradiction.
The following lemma is slightly stronger than the condition in Theorem 3.1. We use this
version in the proof of Theorem 3.6.
Lemma 3.3 If S solves the k-payment problem, then T i - ki for all
Proof: Let i - bN=kc. Then ki - N . Consider k payments of value i each such
payment can be done only with coins of denomination at most i, hence T i - ki.
We now turn to sufficiency. We start by showing that if the condition of Theorem 3.1 holds
single payment of value up to N can be satisfied by S under the greedy
algorithm.
Lemma 3.4 Let P be a payment request, and suppose that in S we have that for some j,
1.
2.
Then P can be satisfied by the greedy algorithm using only coins of denomination j or less.
Proof: We prove, by induction on j, that the claim holds for j and any P . The base case is
and hence there are at least P 1-coins, which can be used to pay
any amount up to their total sum. For the inductive step, assume that the claim holds for j
and all P , and consider j 1. Let a be the number of (j 1)-coins dispensed by the greedy
algorithm, namely,
Let R denote the remainder of the payment after the algorithm dispenses the (j
1). Note that (2) trivially holds after dispensing the (j + 1)-coins; we need to
show that (1) holds as well. We consider two cases. If a = c j+1 , then using (1) we get
and we are done for this case.
If a ! c j+1 , then since the algorithm is greedy, it must be the case that R 1. On the
other hand, by (2) we have that T j - j, and hence T j - R and we are done in this case too.
The following lemma is the key invariant preserved by the greedy algorithm. It is interesting
to note that while the algorithm proceeds from larger coins to smaller ones, the inductive proof
goes in the opposite direction. Recall that "primed" quantities refer to the value after a payment
is done.
Lemma 3.5 If T i - ki holds for all after the greedy algorithm dispenses any
amount up to Tm , T 0
holds for all
Proof: By induction on i. For the claim is trivial. Assume that the claim holds for all
is the amount dispensed using coins of denomination
at most i).
namely j is the smallest remaining denomination which
is larger than i. Note that j is well defined since namely i is not the largest remaining
coin. Next, note that since all the coins of denomination (whose sum is
used by the algorithm, we have that
Now, observe that since the algorithm is greedy, and since at least one j-coin was not used by
the algorithm, it must be the case that the total amount dispensed using coins of denomination
smaller than j is less than j, i.e., Using Eq. (1), we get that T i -
Finally, using the assumption applied to
We now complete the proof of the characterization.
Proof (of Theorem 3.1): The necessity of the condition follows directly from Lemmas 3.2
and 3.3. For the sufficiency, assume that T i - ik for all m, and consider a sequence
of up to k requests of total value at most N . After the l-th request is served by the greedy
algorithm, we have, by inductive application of Lemma 3.5, that T 0
Moreover, by Lemma 3.4, any amount up to the total remainder can be paid from S, so long
as which completes the proof.
3.2 A lower bound on the number of coins
Using Theorem 3.1, we derive a lower bound on the number of coins in any solution to the
k-payment problem.
Theorem 3.6 The number of coins in any solution to the k-payment problem is at least
We first prove a little lemma we use again in Theorem 4.7.
Lemma 3.7 For any number j,
Proof:
Proof (of Theorem 3.6): By Lemma 3.7 and Lemma 3.3:
bN=kc
ki
The lower bound of Theorem 3.6 is the best possible in general, as shown in the following
theorem.
Theorem 3.8 For any natural numbers are infinitely many N ?
that there exists a solution for the k-payment problem with budget N with exactly kH bN=kc coins.
Proof: Choose a natural number m such that m! ?
km. In this case the solution with solves the k-payment problem
by Theorem 3.1, and its total number of coins is precisely kH bN=kc .
3.3 Determining k for a given set
Consider the "inverse problem:" we are given a set of coins, with c i coins of denomination i
for each i, and the question is how many payments can we make using these coins, i.e., find k.
Note that k is well defined: we say that k is 0 if there is a payment request which cannot be
satisfied by the set, and k is never more than the total budget. Theorem 3.1 can be directly
applied to answer such a question efficiently, as implied by the following simple corollary.
Corollary 3.9 Let S be a given coin allocation. Then S solves the k-payment problem if and
only if k - min fbT i =ic mg.
4 An optimal algorithm for unrestricted denominations
We now present a coin allocation algorithm which finds a minimal solution to the k-payment for
arbitrary N and k, assuming that all denominations are available. We first prove the optimality
of the algorithm, and then give an upper bound on the number of coins it allocates. In Section
5 we generalize the algorithm to handle a restricted set of denominations.
The algorithm. Given arbitrary integers N - k ? 0, the algorithm presented in Figure
3 finds an optimal coin allocation. Intuitively, the algorithm works by scanning all possible
denominations for each i, the least number of i-coins which suffices
to make T i - ki. The number of coins c i is thus an approximation of the i-th harmonic element
multiplied by k. When the budget is exhausted, the remainder is added simply as a single
addiotinal coin.
4.1 Optimality of Allocate
Theorem 4.1 Let S denote the solution produced by Allocate. Then S solves the k-payment
problem using the least possible number of coins.
Allocate(N;
4 while denominations in order
add i-coins but don't overflow
9 if N ? t   add remainder

Figure

3: Algorithm for optimal solution of the k-payment problem with unrestricted denominations

Proof: Follows from Lemma 4.3 and Lemma 4.5 below.
The important properties of the algorithm are stated in the following loop invariant.
Lemma 4.2 Whenever Allocate executes line 4, the following assertions hold.
(ii) if
Proof: Line 4 can be reached after executing lines 1-3 or after executing the loop of lines 5-8.
In the former case, we have and the lemma holds trivially.
Suppose now that line 4 is reached after an iteration of the loop. We denote by t 0 the value
of the variable t before the last execution of the loop. If lines 7 and 8 are not executed, then (i)
holds trivially. If they are executed, then we have that
and hence (i) holds after the loop is executed. Also note that t -
l ki\Gammat 0
1), and therefore (iii) holds true after the execution of the loop.
Finally, we prove that (ii) holds after executing the loop. If lines 7-8 are not executed, (ii)
holds trivially. Suppose that lines 7-8 are executed, and that i t. In this case, by line
which means that
Therefore, by line 7, c
l ki\Gammat
, and hence
l ki\Gammat 0
and we are
done.
Using Lemma 4.2 and Theorem 3.1, correctness is easily proven. We introduce some notation
to facilitate separate handling of the remainder:
i , for all i, is the value of the c i variable when line 9 is executed.
.
Lemma 4.3 S solves the k-payment problem.
Proof: By (i) of Lemma 4.2, in conjunction with lines 9-10 of the code, we have that upon
completion of the algorithm,
By (ii) of Lemma 4.2, and since (by lines 4 and 10)
the largest denomination is m -
m , we have that T i - T
denominations
therefore, by Theorem 3.1, S solves the k-payment problem.
Proving optimality takes more work. We first deal with the the coins allocated before line 9
is reached, and then show that even if the remainder was non-zero (and an additinal coin was
allocated in line 10), the solution S produced by Allocate is still optimal. To this end, we fix
an arbitrary solution T for the k-payment problem, and use the following additional notation:
ffl d i is the number of i-coins in T .
ffl U i is the budget allocated in T using coins of denomination i or less: U
ffl n is the largest denomination of a coin in T : Formally,
Note that by the definitions, the following holds for all i - 0:
c
The lemma shows that Allocate is optimal-ignoring the remainder.
Lemma 4.4
c
Proof: By contradiction. Suppose
that l is the
smallest such index, i.e., using Eq. (2), l. Hence, by Eq. (3),
we have that d l ! c
which implies, by integrality, that d l - c
since T
by (iii) of Lemma 4.2, we have
ld l
ic
i.e., U l ! kl, contradiction to Theorem 3.1, since l ! n.
We now prove that S is optimal even when considering the remainder.
Lemma 4.5
d i .
Proof: We consider two cases. If n ? m then using Lemma 4.4, and the fact that d n - 1 by
definition of n, we get
c
and we are done for this case.
So suppose n - m. Let
We prove the lemma by showing that
First, note that since by Lemma 4.4 we have using Eq. (3),
we get
On the other hand, since U
Therefore, it follows from Eq. (2) that
We now consider two subcases. If T
reduces to
nb
and we are done for this subcase.
Otherwise,
and the proof of Lemma 4.5 is complete.
4.2 The number of coins allocated by Allocate
Theorem 4.1 proved that the number of coins in the solution produced by Allocate is optimal.
We now give a tight bound on that number in terms of N and k. There is a nice interpretation to
the bound: it says that the worst penalty for having N and k which are not "nice" is equivalent
to requiring an extra payment (i.e., solving the 1)-payment problem) for "nice" N an k.
We remark that we do not know of any direct reduction which proves this result.
First, we prove an upper bound on m, which is slightly sharper than the general bound of
Lemma 3.2.
Lemma 4.6 The largest denomination of a coin generated by Allocate satisfies m -
l N
Proof: By (iii) of Lemma 4.2 we have T
1)i, and in particular
By (ii) of Lemma 4.2 we have that T
have that T
m. Using also Eq. (5), we get that
1, and by integrality, m -
l N
Theorem 4.7 The number of coins in the solution produced by Allocate is at most (k
Proof: By (iii) of Lemma 4.2, and by integrality, T
in conjunction with Lemmas 3.7 and 4.6, implies that
c
and therefore,
The upper bound given by theorem 4.7 is the best possible in general, as proven in the
following theorem.
Theorem 4.8 For any natural numbers are infinitely many N ?
that any solution for the k-payment problem for budget N requires at least (k
coins.
Proof: Choose a natural number m such that
and divisible by 2; 3;
these N and k, we have that the algorithm produces largest denomination
and c It follows that the number of coins in
this case is precisely
5 Generalization to a restricted set of denominations
We now turn our attention to the restricted denomination case. In this setting, we are given a
set D of natural numbers, and the requirement is that in any solution, c
D.
To get an optimal algorithm for an arbitrary set of denominations which allows for a
solution, 1 we follow the idea of algorithm Allocate: ensure, with the least number of coins,
that m. The treatment of the remainder is more complicated here, but
has the same motivation: add the remainder with the least possible number of coins. We also
have to make sure that the invariant maintained by the main loop is not broken, so we restrict
the remainder allocation to use only denominations which were already considered. In fact,
remainder allocation is precisely the change-making problem, solvable by dynamic program-
ming. (For some allowed denomination sets [5, 14], the greedy strategy works too.) The main
algorithm Allocate-Generalized is given in Figure 4. For completeness, we also include,
in

Figure

5, a description of a dynamic programming algorithm for optimal change-making. In
Allocate-Generalized, and in the analysis, we use the following additional notation.
ig, the largest allowed denomination smaller than i.
ig, the smallest denomination larger than i.
We now prove that Allocate-Generalized is correct and that the number of coins
it allocates is optimal. We remark that the general arguments are similar to those for the
unrestricted case, but are somewhat more refined here.
Theorem 5.1 Let S denote the solution produced by Allocate-Generalized. Then S
solves the k-payment problem with allowed denominations D using the least possible number
of coins.
Proof: Follows from Lemmas 5.3 and 5.8 below.
We again use a loop invariant to capture the important properties of the algorithm.
Lemma 5.2 Whenever Allocate-Generalized executes line 4, the following assertions
hold.
(ii) if
Proof: Line 4 can be reached after executing lines 1-3 or after executing the loop of lines
5-10. In the former case and the lemma holds trivially.
1 Observe that the problem is solvable if and only if 1 2 D: if there are no 1-coins then certainly we cannot
satisfy any payment request of value 1; and if 1 is allowed, then the trivial solution of N 1-coins works for all k.
Allocate-Generalized(N; k; D)
4 while
is the largest den. smaller than the next one in D
l up to j
8 then if
l kj \Gammat
check if budget is exhausted
9 then c i /
l kj \Gammat
if not, add coins
else goto 12
13 then D 0 / fd j d 2 D; d - ig   add remainder without greater denominations

Figure

4: Algorithm for optimal solution of the k-payment problem with allowed denominations
D.
In the latter case, let t 0 denote the value of the variable t before the last execution of the
loop. If lines 9 and 10 are not executed, then (i) holds trivially. If they are executed, then
holds after the loop is executed. Then,
whether or not lines 9 and 10 are executed t -
l kj \Gammat 0
thus (iii) is true after the execution of the loop.
Finally, we show (ii) holds after executing the loop. If line 8 is not executed, or if line 11
is executed then (ii) holds trivially. Otherwise lines 9-10 are executed, and c
l kj \Gammat
, hence
l kj \Gammat 0
The correctness of Allocate-Generalized is proven in the next lemma. Following the
conventions of Section 4, we denote by S   the allocation produced by Allocate-Generalized
before line 12. We denote by c
i the values in S   corresponding to c i and T i in S,
respectively.
Lemma 5.3 S solves the k-payment problem with allowed denominations D.
Proof: By (i) of Lemma 5.2, in conjunction with lines 12-14 of the code, we have that upon
completion of the algorithm,
be the highest denomination allocated by the
algorithm. Then, by (ii) of Lemma 5.2, and the fact that Make-Change does not use coins
with higher denominations (line 13), we have that for all 1
Therefore, by Theorem 3.1, S solves the k-payment problem.
Make-Change(R;D)
do if i 2 D
6 do for i / R downto 1
7 do if M
8 then for all
9 do if M [i \Gamma j]
return M [R]

Figure

5: Dynamic programming algorithm for finding least number of coins whose sum is R
units using denomination set D. M is an array of multisets.
We now turn to prove optimality of the algorithm. The analysis proceeds similarly to that
of Section 4: We first show that the allocation of the coins up to the remainder (i.e., just
before line 12 is executed), is optimal. We then prove that the handling of the remainder is
optimal as well. The proof here is complicated by the fact that in order to ensure correctness,
Allocate-Generalized allocates the remainder by using only denominations which were
already considered in the main loop, and hence it is not immediately clear that the remainder
is allocated optimally.
For the remainder of this section, fix an arbitrary "competitor" solution T . We define for T
notions analogous to those defined for the solution S produced by Allocate-Generalized.
ffl d i is the number of i-coins in T .
ffl U i is the budget allocated in T using coins of denomination i or less: U
ffl n is the largest denomination of a coin in T : Formally,
To facilitate treatment of the remainder, we fix an arbitrary subsulotion T   of T which
solves the k-payment problem for budget T
. (This is possible since a solution for budget N is
also a solution for any budget smaller than N .) We use the following additional definitions.
jd
. (Analogous to T
i in S).
is the largest denomination in T   .
is the largest denomination allocated up to line 12 by Allocate-Generalized.
Hence, T
Finally, we define
As before, by the definitions,
for all i - 0 we have
d
c
d
We start by proving that Allocate-Generalized produces an optimal solution-ignoring
the remainder.
Lemma 5.4 For all 1
d
c
Proof: Suppose
that l is the smallest such index, i.e., using
l. Hence, by Eq. (7), we have that d
which implies, by integrality, that d
l - c
l by (iii) of
Lemma 5.2. Therefore, since l
U
ld
l
id
ic
or U
a contradiction to Theorem 3.1, since l
Corollary 5.5 n   - m   .
Proof: Suppose not. Then, by Lemma 5.4, U
which
is a contradiction to the fact that U
Next, we prove that no solution can use a denomination larger than the largest one used by
S.
Lemma 5.6 n - m.
Proof: We consider two cases. Suppose first that line 12 is reached after testing the condition
line 4. Then m  hence the remainder allocated by the dynamic algorithm is
m. Note that n - max(n
and therefore, n - max(m   and we are done for this case.
Suppose next that line 12 is reached from line 11. In this case we have
and since T
and hence
or
Now suppose for contradiction that n ? m. Then at least one coin of denomination
allocated by T , hence N - we get from
Eq. (8) that a contradiction to Theorem 3.1 since
It follows that the remainder is allocated optimally (for any choice of a subsolution T   ).
Corollary 5.7
d
c
Proof: By Lemma 5.6, the amount of
m must be allocated in T using only denominations
used in S. The statement therefore follows from the optimality of dynamic programming used
in Make-Change.
We can now prove optimality of the full solution S.
Lemma 5.8
d i .
Proof: By Corollary 5.7, it is sufficient to prove that the number of coins in T   is at least as
much as in S   . If n   - m   , then we are done by Lemma 5.4. It remains to consider the case of
. We do it similarly to Lemma 4.5: define
. With this notation, it is
sufficient to show that
By Lemma 5.4 we have using Eq. (7) we get
U
i(d
Also, since U
U
c
ic
Hence,
b. Thus, from Eq. (6) we get
(d
as required.
6 Exact payments in electronic cash
In this section we discuss the issue of exact payments in the model of electronic cash (e-cash).
Briefly, in this model we have a bank, a set of users and a set of shops. There are withdrawal
and deposit protocols involving the bank and a user or shop, and a payment protocol, involving
a shop and a user. It is required that the users are anonymous: given a coin, it should be
impossible to infer which user withdrew it, even if the shops and bank collaborate. On the
other hand, the identity of the user should be revealed if the user pays with the same coin
more than once. The model has to be implemented with "electronic wallets" called smart cards
which have a severely limited capacity for storage and computation [7].
There are a few ways to implement exact payments in e-cash. The simplest way is to use
multiple coins. In this case, the results presented in this paper explain what coins should be
withdrawn. Another approach is divisible coins [9, 8, 12]: arbitrary portions of the coin can be
spent so long as their sum does not exceed the value of the coin. As expected, the size of a
divisible coin and the computational resources (such as time and communication) required for
its manipulation are greater than those of non-divisible coins.
An intermediate approach is presented in [12]: a composite coin is divisible only to a set
of prescribed set of subcoins. Subcoins can be used for payment and deposit, but cannot be
divided further. Although the size of the composite coin grows linearly with the number of its
constituent subcoins (for C subcoins, a typical size of the composite coin is 500
the size is still smaller than the size of arbitrarily divisible coins for a sufficiently small number
of subcoins. The results of this paper are particularly useful for the composite coin
if one can get a reasonable bound k on the number of exact payments, then composite coins
are better than arbitrarily divisible coins in all respects for certain ranges of N and k. With
current technology, the technique of [12] is better when k

Acknowledgments

We thank Mike Saks, Richard Stanley and Yishay Mansour for helpful discussions, Eric Bach
for bringing the postage stamp problem to our attention, Rakesh Verma for providing us with
a copy of [14], and Agnes Chan for valuable suggestions and comments.



--R

Untraceable off-line cash in wallets with observers
Blind signatures for untraceable payments.
Untraceable electronic cash.
Construction of distributed loop networks.
Optimal bounds for the change-making problem
Knapsack Problems: Algorithms and Computer Implementations.
Cryptographic smart cards.
An efficient divisible electronic cash scheme.
Universal electronic cash.
On the postage stamp problem with 3 denominations.
Associate bases in the postage stamp problem.
Efficient Electronic Notions and Techniques.
A Course in Combinatorics.
On optimal greedy change making.
--TR
coin allocation;change-making;exact change;electronic cash;k-payment problem