Postby **skullturf** » 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.