The coin changing problem - ISISS M. Casagrande (Pieve di Soligo)

The aim of this article is to study a new operation that given two finite sets it yields a new finite set whose elements correspond to all the possible sums between the elements of the two separate sets. In this paper we will focus on the case in which the operation is iterated k times for the same finite set in order to determine the cardinality of the set at each iteration. We will find a connection with the coin changing problem by considering the finite set as a coin system that can be used to express any natural value. Given a coin system we will search for the minimum number of necessary coins to obtain any natural value. Eventually we will determine a series of conditions that must be satisfied by the coins of the system with which it will be possibile to get any natural value with the greedy algorithm.