Water and Wine

Some time ago I heard an interesting riddle that gave out quite a few headaches. I've been told this puzzle originated from The Republic by Plato, though I don't know if that's the real source of this riddle. His congratulations go out to whoever can solve this puzzle by thought experiment alone.

Here is the riddle:
1. Get 1 cup of wine and 1 cup of water.
2. Take a table spoon of wine and put it into the water.
3. Mix thoroughly.
4. Take a table spoon of the now water and wine mixture and put it back into the wine.

Now the question: at the end of the procedure which cup has a higher ratio of foreign substance to original substance? Is the water cup more polluted by wine or the wine cup more polluted by the water?

Most people's first reaction would be to say the water cup has surely been more polluted. We put a table spoon of pure wine into the water, but we only put a mixture of water and wine back into the wine glass. This is the most obvious observation of course, and there is a subtle observation that might lean you towards the other direction.

Even though we put a table spoon of pure wine into a the glass of water, and we put the mixture into the glass of wine. The effect of the wine glass being less than full means whatever we put into it should contaminate it more than if the glass had been full.

The last paragraph gives the argument for why it may be either side which is more polluted, or maybe an argument why they might be the same. I suggest to take your side now, as the rest of the post will describe the solution.

There are lots of ways to solve this puzzle, I will give the way I find the most elegant. It is similar to a type of argument that's used in mathematics called a combinatorial argument. We measure the same thing in two different ways and then since both measurements are of the same thing the measurements must be the same. This argument has the advantage in this situation of not worrying about the sequence of events outlined in the procedure. If we were to simply work out the amount of wine and water in each cup at each stage then we would come to a mess of fractions.

In order to use the strategy it's necessary to name the different pieces of fluid. The following image shows how I chose to label the water and wine in each glass. Now consider ways we can make a full glass of fluid. If we look at what's in the water glass it must measure up to 1 cup. This is because we took 1 table spoon of fluid out and put back 1 table spoon. Therefore $$A + B = 1 cup$$. On the other hand we started with 1 cup of water, so if we add up all the water we should get 1 cup. This means $$A + D = 1 cup.$$ These two equations cannot both be true unless $B = D$. So we can conclude both cups are equally polluted.

I hope you all enjoyed this one :).

Making Change

Since this is the first blog post on here I decided we could tackle a classic problem.  Given some collection of coins (say pennies, nickels, dimes, quarters, etc.) how many ways can the coins be combined to make some given amount of change?  More explicitly, given a set of distinct positive integers  $\{x_1, x_2, ... ,x_n\}$ and a value $V$, how many ways are there to make $V$ cents using coins valued $x_1, x_2, ... , x_n$?

This problem is given on Project Euler here.  In this post I'm going to show how to solve the Project Euler problem (using C#)..

From the link above:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

$$1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) \text{ and } £2 (200p)$$

How many different ways can £2 be made using any number of coins?

Running a brute force algorithm on this would take forever, so instead we can try to devise a clever algorithm.  First it might be helpful to imagine the problem if we didn't have so many coins.  It's quite a pain to keep track of how many different coins there are when we try to think of a way to solve this problem.  Instead we will solve a smaller problem by hand: how many ways are there to make 200p using only 1p and 2p coins?

This is a much easier problem.  We can easily divide this into cases.  There is as few as $0$ 2p pieces and as many as $100$.  In any configuration if we knew how many 2p pieces there were then we would automatically know how many 1p pieces there were since the total value of the coins is 200p.  Therefore, there are 101 ways to make 200p out of 1p and 2p pieces.

The 2 coin case was quite simple, so what if we add a third coin?  How many ways can we make 200p using 1p, 2p and 5p pieces?  We have an analog to the 2 coin case here.  If we know how many 5p pieces we are using can we determine the number of ways to make the remaining change with only 1 and 2 pence pieces?  To answer this critical question let's introduce the following notation.
$$p_k(n)=\text{the number of ways to make }n\text{ pence using coins of value }\leq{k}.$$

For example $p_1(n)=1$ for all $n$ because there is only one way to make any amount of change only using the 1p pieces.
How about $p_2(n)$?  Here we can do casework.  Above we solved a specific case  ($p_2(200)$) by dividing into cases depending on how many $2p$ pieces we used.  In general, $p_2(n)$ satisfies the recurrence $$p_2(n)=p_1(n)+p_1(n-2)+p_1(n-4)+...+p_1(n-2\lfloor{\frac{n}{2}}\rfloor)$$
The first term being the number of ways to make $n$ pence if we used no 2p pieces, the second term being the number of ways if we used 1, the third term if we used 2, etc. And the last term being if we used the maximum allowable number of 2p pieces.  It's clear that there is nothing special about the fact we are using 2p pieces here and we could in fact make the same argument for 5p pieces and derive an expression of the form $$p_5(n)=p_2(n)+p_2(n-5)+p_2(n-10)+...+p_2(n-5\lfloor{\frac{n}{5}}\rfloor).$$
Here the skip from 5 to 2 is because there is no 3p piece and no 4p piece.  This gives us an outline for an argument we can use for any coinage amount.
On your own you might try deriving the expression for 10p pieces and above.

All said and done here is an example of the code we might get  solving this problem:

Now this solves the particular case from the Project Euler site. Running the code tells us the total number of ways to make $£2$ using the above coin combinations is $73,682$!