Page 1 of 1

### Different Numbers of Coins, Different Totals

Posted: Tue Nov 19, 2013 4:06 am UTC
A while back I noticed something interesting about US coins and their denominations. Suppose I have some pennies, nickels, dimes, and quarters in my pocket such that I have a different number of each denomination, at least 1 of each but no more than 4 of each. (For example, I could have 1 nickel, 2 quarters, 3 pennies, and 4 dimes.) Then you can figure out exactly which coins are in my pocket just by knowing the total value of the coins.

Mathematically, you can express this as follows:

If [a1, a2, a3, a4] is any arbitrary permutation of [1, 2, 3, 4], then there are 4! = 24 possible values of a1+5a2+10a3+25a4.

Alternatively:

Let a = [1, 2, 3, 4] and v = [1, 5, 10, 25]. Then across all possible 4×4 permutation matrices P, the values aPvT are all distinct.

I'm curious as to necessary and sufficient conditions on v such that this holds for arbitrary sizes, i.e., when a = [1, 2, ..., n], P is an n×n permutation matrix, and v is any arbitrary n-dimensional vector with distinct elements.

For n = 2, this is pretty trivial: any v with two distinct elements will work.

I've managed to solve this for n = 3:
Spoiler:
All six values are distinct if and only if the elements of v are not consecutive terms in an arithmetic sequence.

However, it seems to get hairier for n ≥ 4. Any thoughts?

### Re: Different Numbers of Coins, Different Totals

Posted: Sat Nov 23, 2013 9:08 pm UTC
This is really interesting. I know you said you solved the 3-coin case, but let's look at it in a little more detail.

Let's say the values of the three types of coin are v1 < v2 < v3. Let's also define

f(a,b,c) = a*v3 + b*v2 + c*v1 = the total value of a of the most valuable coin, b of the next most valuable coin, and c of the least valuable coin.

We want the six numbers

f(1,2,3), f(1,3,2), f(2,1,3), f(2,3,1), f(3,1,2), f(3,2,1)

all to be different.

We notice that some of them are automatically different. For example, we must have f(3,2,1) > f(3,1,2). If we have 2 coins of value v2 and 1 coin of value v3, and we exchange for 1 coin of value v2 and 2 coins of value v3, we lose money.

More generally, if there are more than 3 types of coin, inequalities of the following type will always be true:

If i<j, then f(...,j,...,i,...) > f(...,i,...,j,...). (This notation may be imprecise. I mean that the lists of arguments are identical except that i and j have been switched.)

Let's define S to be the set of formal expressions {f(1,2,3), f(1,3,2), f(2,1,3), f(2,3,1), f(3,1,2), f(3,2,1)}. These are six different formal objects, but some of them may evaluate to the same number, depending on the values of the coins. More generally, let's define S to be the analogous set of formal expressions for the corresponding problem with 4 or more coins.

We can define a partial order on the set S. We write f(u,v,w) > f(x,y,z) if the inequality is true regardless of the values of the coins. By our earlier remarks, there are many relations of this type that are true. Here are some examples of "chains" in our partial order.

f(3,2,1) > f(2,3,1) > f(1,3,2) > f(1,2,3)
f(3,2,1) > f(2,3,1) > f(2,1,3) > f(1,2,3)
f(3,2,1) > f(3,1,2) > f(1,3,2) > f(1,2,3)
f(3,2,1) > f(3,1,2) > f(2,1,3) > f(1,2,3)

However, this partial order is probably not a linear order in general. For instance, maybe f(2,3,1) and f(3,1,2) are incomparable in our partial order -- there may be some sets of coin values where f(2,3,1) evaluates to a larger number than f(3,1,2), and some where it's the other way around (as well as some where the two evaluate to the same number).

To understand the 4 coin case, maybe it would be helpful to study the corresponding partial order. But the details seem complicated. Some examples of "chains" in that partial order would look like

f(4,3,2,1) > f(3,4,2,1) > f(2,4,3,1) > f(1,4,3,2) > f(1,3,4,2) > f(1,3,2,4) > f(1,2,3,4)
f(4,3,2,1) > f(3,4,2,1) > f(2,4,3,1) > f(2,3,4,1) > f(2,3,1,4) > f(2,1,3,4) > f(1,2,3,4)

That's all I have for now. I'm basically just thinking out loud. But I agree that it's an interesting problem.

Maybe somebody should write a computer program to do some of the number crunching for the four coin case, which might help us come up with the right conjecture to make.

### Re: Different Numbers of Coins, Different Totals

Posted: Tue Nov 26, 2013 11:53 pm UTC
I like this problem, even if we're the only two here who do.

Now that some time has passed, I'll post spoilers freely. Hope that's OK.

For the three coin case, the condition is that the three values not be in arithmetic progression.

Here's another way of saying that. If the values of the three types of coin are a<b<c, then the condition that a,b,c form an arithmetic progression is equivalent to the condition that b is the average of a and c.

If a,b,c satisfy that, then:

3 coins of value a + 1 coin of value b + 2 coins of value c = 3a+1b+2c
2 coins of value a + 3 coins of value b + 1 coin of value c = 2a+3b+1c

The difference between those is a-2b+c, which is 0 if b is the average of a and c.

Now, suppose there are four coins. This is just a guess, but if there's an easy-to-state necessary and sufficient condition (there might not be) then it might be something along the lines of "there are two disjoint subsets of the set of values that have the same average".

Examples:

Suppose the values of the four types of coin are 17, 19, 41, 43. More generally, suppose they have the form a, a+k, b, b+k. Then

4 coins of value a + 3 coins of value a+k + 1 coin of value b + 2 coins of value b+k = 4a+3(a+k)+1b+2(b+k) = 7a+3b+5k
3 coins of value a + 4 coins of value a+k + 2 coins of value b + 1 coin of value b+k = 3a+4(a+k)+2b+1(b+k) = 7a+3b+5k

Those two have the same value, and the set {a,b+k} has the same average as the set {b,a+k}.

A different example. Suppose the values of the four types of coin are 1, 10, 12, 25. Notice that 12 is equal to the average of 1, 10, and 25.

The following have the same value as each other:

4 coins of value 1 + 3 coins of value 10 + 1 coin of value 12 + 2 coins of value 25
3 coins of value 1 + 2 coins of value 10 + 4 coins of value 12 + 1 coin of value 25

The first row minus the second will give 1*1 + 1*10 - 3*12 + 1*25, which is zero.

### Re: Different Numbers of Coins, Different Totals

Posted: Thu Nov 28, 2013 10:20 pm UTC
Here's a brute-force O(n!2) way to find the constraints. Compute all n!(n!-1)/2 "difference constraints" dij=a(Pi-Pj), where the Pi are distinct permutation matrices. A set v of coins has all of these values distinct iff all dijvT!=0.

Note that any permutation of the elements of a difference constraint dij is also a difference constraint, so really you "only" need to compute n! differences. Each difference constraint forbids the values of the coins from lying on a particular hyperplane (i.e., a line for n=2, a plane for n=3, etc.).

For n=2 there's only one difference constraint, d12=[+1,-1]. So two coins have this property iff [+1,-1].[v1,v2]!=0, i.e. iff v1!=v2, as you already found.

For n=3, up to permutations the difference constraints are [+1,-1,0] and [+1,+1,-2]. The first one is the same as for n=2, i.e. forbidding two coins' values from being equal. (Obviously in general all of the constraints for a given n will carry forward to n+1.) The second constraint is that no two coins' values can sum to the third; equivalently, as you already found, the three coins' values can't lie in arithmetic sequence.

For n=4, up to permutations there are eight difference constraints, two from earlier and six new ones:
[1,-1,0,0] - the constraint from n=2 (no two values equal)
[1,1,-2,0] - the constraint from n=3 (no three coins in arithmetic sequence)
[2,1,-3,0]
[3,1,-1,-3]
[2,2,-1,-3]
[1,1,1,-3]
[2,1,-1,-2]
[1,1,-1,-1]
Some of these have simpler plain-English interpretations than others. The last one [1,1,-1,-1], for example, can be stated as "no pair of coins has the same sum as the other pair", or as "no pair of coins has the same difference as the other pair". (With the second interpretation you can give similar interpretations for e.g. [2,1,-1,-2] and [3,1,-1,-3], and for [1,1,-2,0] and [2,1,-3,0] with a further generalization.)

For n=5 there are 27 difference constraints.

I suspect there won't be simple interpretations for all of these constraints, especially as n gets bigger.