This blog is highly personal, makes no attempt at being politically correct, will occasionaly offend your sensibility, and certainly does not represent the opinions of the people I work with or for.
Messing around with coins [updated]

Every so often, I enter into a shop to buy something, decide to pay with cash, then notice that I have lots of coins in my purse, and if there are no other customers in the shop, I look at the shopkeeper and say "Hang on a second, I will give you some change..."; and then the following happen.

So I will give you an example. Say that I need to pay £2.40. I will get two coins of £1, two coins of £0.20 and put them on the counter (at which point I may have to say "No, wait! Don't take them. I am not done yet"). So at than point there is £2.40 on the counter.

Then I will look at inside the purse and notice that I have, say, two £0.10 coins in there. I take them, put then on the counter, and put one of the £0.20 coins back into the purse. Then, I notice that I have, say, four £0.05 coins in the purse, will put them on the counter, and will put the other £0.20 coin back in the purse. And so on with other coins...

So now you get it. I apply atomic transitions where each transition consists in replacing one coin from the counter by two or more coins from my purse. And I carry on applying those transitions until the moment there is no other possible transition. At which point I look at the shopkeeper and say "I am done (^_^)".

Then always comes my favourite part: first they look at me wondering "What the fuck just happened", then they look at the mountain of coins on the counter, decide to patiently count the money as if it had suddenly appeared there, while I stand smiling, and eventually they say "Correct, exact amount", to which I like replying "I knew that (^_^)"

Maybe none of them ever realised that each transition maintains a mathematical invariant: the amount of money.

Anyway, I was thinking this evening of two things: First, can I mathematically prove that the process always terminates, and second, can I prove that the final state (set of coins on the counter) is the same regardless of the order in which I replaced the coins. The first question is really trivial, but for the second it actually took me few seconds to formulate a proper mathematical proof in my mind.

I will update this entry with the proofs in few days, to let your readers have time to think about it :)

Few days later...

So the outstanding items from the original entry are (1) showing that the process terminates, and (2) showing that the final state is independent on the order in which the atomic replacements have been performed.

To show that the process always terminates it is enough to say that at each operation, the number of coins left in the purse strictly decreases. Indeed, the atomic operation was stated as "replacing one coin from the counter by two or more coins from my purse", therefore at each step the number of coins left in the purse is at least one less than it was before. Then, it is just enough to remark that there are no infinite strictly decreasing sequences of natural integers.

For the other one, things get a bit tricky. Turns out that the claim as I gave it wasn't true (I knew that of course, and the readers who did the exercise of trying to figure out the formal proof also must have noticed). You see, the transition rule was given as "replacing one coin from the counter by two or more coins from my purse". With such a rule it is not true that the final state is unique. To see why, consider that there are two £0.50 coins on the table and that I have five £0.20 coins in the purse. It feels like we should replace the two coins by the five coins, but there is no number of £0.20 coins that is equal to one £0.50 coin. Therefore with the transition rule as stated, there are cases where the final state is not unique and depends on the order the operations were performed. In the example I gave, there might be a sequence of substitutions leading to two £0.50 coins (and no possible further transition) while there could also be another sequence leading directly to all five £0.20 coins on the table (and the two £0.50 coins in the purse) and no further transitions.

The correct transition rule (and the one I actually use in reality) is "to replace a given number of coins on the counter by a strictly greater number of coins from the purse". With this better rule, we are then able to replace two £0.50 coins by five £0.20 coins in one transition. Leading to the final state always being five £0.20 coins on the counter.

So now, what about the formal proof ? Well, imagine that we have a situation where we think that we have two final states, A and B, with no further transition from. Note that necessarily, A and B represent the same amount of money (remember the invariant). If one of the two states, say A, has more coins on the table than B, then this simply means that A wasn't a final state and that there is an additional transition consisting in replacing all the coins of A by all the coins of B.

So what we have just learnt is that if there are two final states, then not only they represent the same amount of money, but also they have the same number of coins.

Let us now make the following observation: If those two states, A and B, have a coin in common (say that they both have one £0.10 coin in common), then let us remove that common coin from both sides, leading to states A(1) and B(1). What can we say about A(1) and B(1) ? Well, they represent the same amount of money, they have the same number of coins and the both have one coin less than A or B. Let's redo the same operation (removing a common coin from both sides) until we cannot do it anymore.

If at the end of this process there are no coins left on either sides, then this means that A and B were identical, and therefore not different.

So, having started from the assumption that A and B were different, this process will lead to states A(n) and B(n), such that: A(n) and B(n) have at least one coin (are not empty), are the same amount of money, have the same amount of coins, and have no coins in common.

So here is the interesting part: it is not possible two have two piles of coins with the above properties: ie: same amount of money, same number of coins and no coins in common. You can actually check this manually (because, after all, there are only 8 coins in circulation in the UK monetary system £0.01, £0.02, £0.05, £0.10, £0.20, £0.50, £1 and £2).

[ add a comment ]