Friday 27 October 2017

Friday Factoid: There are 451 unique ways to make up 50p.

During The Man who knew Infinity I mentioned an interesting problem:

How many ways were there of making coins add up to the value of 50p?

In the UK, we have coins of value 1,2,5,10,20,50,100, and 200. To get them to add up to 50, we can have three 10p pieces plus one 20p.  Or we could have 25 tuppences (2p pieces). Or many other combinations.

I got this problem via a phone call from a friend of mine who said that their grandchild had been sent home from school with a challenge. I was in the pub with two statistics professors, and we all scratched our heads.


This problem turned out to be quite fun. I thought the answer would be quite large, but I was surprised that there are 451 ways. No wonder running the economy is so difficult!

I eventually came up with a graph which manages to show how we generalise this to any monetary amount.

See how quickly the graph rises with the amount of money to be made up in change? This seems a very difficult problem for a small person, so I suspect the teacher set it as a way to keep a bright child quiet for a few hours!

(Edited to add US Coins: Look how much difference there is for UK and US coins, mostly because USA does not have a 2c coin.)
I looked for a sensible way to do it, but the only real way I can explain it is to come up with some logical way to write these out. I cannot see a clever mathematical trick, so I used a recursive algorithm, which means that we keep using the algorithm within itself until we get the answer.

Either you use one 50p piece (count 1 way)
or you don't use any 50p piece (Call this X).

Now we need X:
Either you use two 20p pieces (call this X1)
or you use one 20p piece (Call this X2)
or you use no 20p pieces (Call this X3)

So X=X1+X2+X3

Now we find X1- we have to find ways to make 10p with no coin bigger than a 10p.
Either we use one 10p piece (count 1)
or we use none (Call this Y1)...

All this algebra produces a complicated sum. Although you can reuse bits of it, it is laborious, and probably very hard to get right.

I got bored in the end, so I cheated. I wrote this short piece of code in MatLab which will take any amount of money, any collection of change, and print out all possible combinations of change to get the required sum. The code can be found below.

The function takes in three arguments, "amount", "possCoins" and "strIn".
  • amount is the amount of money we are partitioning;
  • possCoins is the set of coins we are partitioning the amount into. For example, in Britain we use coins of denomination of 1p, 2p, 5p, 10p, 20p, 50p, £1 and £2. In America, they have a 25c coin, rather than a 20c coin.
  • strIn is a string which is the list of all the coin combinations we have already found if we are part way through the recursion.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function numWays = coins(amount,possCoins,strIn)
    if ((isempty(possCoins)) | (amount<=0))
            numWays=0;
    else
        if (amount==possCoins(1))
           strOut=[strIn,' ',num2str(possCoins(1))];
           disp(strOut)
           numWays=1+coins(amount,possCoins(2:length(possCoins)),strIn);
         else
           strOut=[strIn,' ',num2str(possCoins(1))];
           numWays=coins(amount-possCoins(1),possCoins,strOut)+...
           coins(amount,possCoins(2:length(possCoins)),strIn);
        end
    end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The above code does essentially the same process as described. Using it for the 50p case, we first define the possible coins we can use:

>> possCoins=[50,20,10,5,2,1]
possCoins =

    50    20    10     5     2     1

Then we define strIn to be empty (we start at the beginning so we haven't started the recursion) :

>> strIn=' '

Finally, we call the function above, which gives the following output, in a logical order:

>> coins(amount,possCoins,strIn)

  50
  20 20 10
  20 20 5 5
  20 20 5 2 2 1
  20 20 5 2 1 1 1
  20 20 5 1 1 1 1 1
  20 20 2 2 2 2 2
  20 20 2 2 2 2 1 1
  20 20 2 2 2 1 1 1 1
  20 20 2 2 1 1 1 1 1 1
  20 20 2 1 1 1 1 1 1 1 1
  20 20 1 1 1 1 1 1 1 1 1 1
  20 10 10 10
  20 10 10 5 5
  20 10 10 5 2 2 1
  20 10 10 5 2 1 1 1
  20 10 10 5 1 1 1 1 1
  20 10 10 2 2 2 2 2
  20 10 10 2 2 2 2 1 1
  20 10 10 2 2 2 1 1 1 1
  20 10 10 2 2 1 1 1 1 1 1
  20 10 10 2 1 1 1 1 1 1 1 1
  20 10 10 1 1 1 1 1 1 1 1 1 1
  20 10 5 5 5 5
  20 10 5 5 5 2 2 1
  20 10 5 5 5 2 1 1 1
  20 10 5 5 5 1 1 1 1 1
  20 10 5 5 2 2 2 2 2
  20 10 5 5 2 2 2 2 1 1
  20 10 5 5 2 2 2 1 1 1 1
  20 10 5 5 2 2 1 1 1 1 1 1
  20 10 5 5 2 1 1 1 1 1 1 1 1
  20 10 5 5 1 1 1 1 1 1 1 1 1 1
  20 10 5 2 2 2 2 2 2 2 1
  20 10 5 2 2 2 2 2 2 1 1 1
  20 10 5 2 2 2 2 2 1 1 1 1 1
  20 10 5 2 2 2 2 1 1 1 1 1 1 1
  20 10 5 2 2 2 1 1 1 1 1 1 1 1 1
  20 10 5 2 2 1 1 1 1 1 1 1 1 1 1 1
  20 10 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 10 2 2 2 2 2 2 2 2 2 2
  20 10 2 2 2 2 2 2 2 2 2 1 1
  20 10 2 2 2 2 2 2 2 2 1 1 1 1
  20 10 2 2 2 2 2 2 2 1 1 1 1 1 1
  20 10 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  20 10 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  20 10 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  20 10 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 10 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 10 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 5 5 5 5
  20 5 5 5 5 5 2 2 1
  20 5 5 5 5 5 2 1 1 1
  20 5 5 5 5 5 1 1 1 1 1
  20 5 5 5 5 2 2 2 2 2
  20 5 5 5 5 2 2 2 2 1 1
  20 5 5 5 5 2 2 2 1 1 1 1
  20 5 5 5 5 2 2 1 1 1 1 1 1
  20 5 5 5 5 2 1 1 1 1 1 1 1 1
  20 5 5 5 5 1 1 1 1 1 1 1 1 1 1
  20 5 5 5 2 2 2 2 2 2 2 1
  20 5 5 5 2 2 2 2 2 2 1 1 1
  20 5 5 5 2 2 2 2 2 1 1 1 1 1
  20 5 5 5 2 2 2 2 1 1 1 1 1 1 1
  20 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1
  20 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 2 2 2 2 2 2 2 2 2 2
  20 5 5 2 2 2 2 2 2 2 2 2 1 1
  20 5 5 2 2 2 2 2 2 2 2 1 1 1 1
  20 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1
  20 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  20 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  20 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 2 2 2 2 2 2 2 2 2 2 2 1
  20 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  20 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  20 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  20 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  20 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  20 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  20 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  20 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 10 10
  10 10 10 10 5 5
  10 10 10 10 5 2 2 1
  10 10 10 10 5 2 1 1 1
  10 10 10 10 5 1 1 1 1 1
  10 10 10 10 2 2 2 2 2
  10 10 10 10 2 2 2 2 1 1
  10 10 10 10 2 2 2 1 1 1 1
  10 10 10 10 2 2 1 1 1 1 1 1
  10 10 10 10 2 1 1 1 1 1 1 1 1
  10 10 10 10 1 1 1 1 1 1 1 1 1 1
  10 10 10 5 5 5 5
  10 10 10 5 5 5 2 2 1
  10 10 10 5 5 5 2 1 1 1
  10 10 10 5 5 5 1 1 1 1 1
  10 10 10 5 5 2 2 2 2 2
  10 10 10 5 5 2 2 2 2 1 1
  10 10 10 5 5 2 2 2 1 1 1 1
  10 10 10 5 5 2 2 1 1 1 1 1 1
  10 10 10 5 5 2 1 1 1 1 1 1 1 1
  10 10 10 5 5 1 1 1 1 1 1 1 1 1 1
  10 10 10 5 2 2 2 2 2 2 2 1
  10 10 10 5 2 2 2 2 2 2 1 1 1
  10 10 10 5 2 2 2 2 2 1 1 1 1 1
  10 10 10 5 2 2 2 2 1 1 1 1 1 1 1
  10 10 10 5 2 2 2 1 1 1 1 1 1 1 1 1
  10 10 10 5 2 2 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 2 2 2 2 2 2 2 2 2 2
  10 10 10 2 2 2 2 2 2 2 2 2 1 1
  10 10 10 2 2 2 2 2 2 2 2 1 1 1 1
  10 10 10 2 2 2 2 2 2 2 1 1 1 1 1 1
  10 10 10 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  10 10 10 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  10 10 10 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 5 5 5 5
  10 10 5 5 5 5 5 2 2 1
  10 10 5 5 5 5 5 2 1 1 1
  10 10 5 5 5 5 5 1 1 1 1 1
  10 10 5 5 5 5 2 2 2 2 2
  10 10 5 5 5 5 2 2 2 2 1 1
  10 10 5 5 5 5 2 2 2 1 1 1 1
  10 10 5 5 5 5 2 2 1 1 1 1 1 1
  10 10 5 5 5 5 2 1 1 1 1 1 1 1 1
  10 10 5 5 5 5 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 5 2 2 2 2 2 2 2 1
  10 10 5 5 5 2 2 2 2 2 2 1 1 1
  10 10 5 5 5 2 2 2 2 2 1 1 1 1 1
  10 10 5 5 5 2 2 2 2 1 1 1 1 1 1 1
  10 10 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1
  10 10 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 2 2 2 2 2 2 2 2 2 2
  10 10 5 5 2 2 2 2 2 2 2 2 2 1 1
  10 10 5 5 2 2 2 2 2 2 2 2 1 1 1 1
  10 10 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1
  10 10 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  10 10 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 2 2 2 2 2 2 2 2 2 2 1
  10 10 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  10 10 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  10 10 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  10 10 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  10 10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  10 10 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  10 10 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 5 5 5 5
  10 5 5 5 5 5 5 5 2 2 1
  10 5 5 5 5 5 5 5 2 1 1 1
  10 5 5 5 5 5 5 5 1 1 1 1 1
  10 5 5 5 5 5 5 2 2 2 2 2
  10 5 5 5 5 5 5 2 2 2 2 1 1
  10 5 5 5 5 5 5 2 2 2 1 1 1 1
  10 5 5 5 5 5 5 2 2 1 1 1 1 1 1
  10 5 5 5 5 5 5 2 1 1 1 1 1 1 1 1
  10 5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 5 2 2 2 2 2 2 2 1
  10 5 5 5 5 5 2 2 2 2 2 2 1 1 1
  10 5 5 5 5 5 2 2 2 2 2 1 1 1 1 1
  10 5 5 5 5 5 2 2 2 2 1 1 1 1 1 1 1
  10 5 5 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 2 2 2 2 2 2 2 2 2 2
  10 5 5 5 5 2 2 2 2 2 2 2 2 2 1 1
  10 5 5 5 5 2 2 2 2 2 2 2 2 1 1 1 1
  10 5 5 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1
  10 5 5 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  10 5 5 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 1
  10 5 5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  10 5 5 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  10 5 5 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  10 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  10 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 5 5 5
  5 5 5 5 5 5 5 5 5 2 2 1
  5 5 5 5 5 5 5 5 5 2 1 1 1
  5 5 5 5 5 5 5 5 5 1 1 1 1 1
  5 5 5 5 5 5 5 5 2 2 2 2 2
  5 5 5 5 5 5 5 5 2 2 2 2 1 1
  5 5 5 5 5 5 5 5 2 2 2 1 1 1 1
  5 5 5 5 5 5 5 5 2 2 1 1 1 1 1 1
  5 5 5 5 5 5 5 5 2 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 2 2 2 2 2 2 2 1
  5 5 5 5 5 5 5 2 2 2 2 2 2 1 1 1
  5 5 5 5 5 5 5 2 2 2 2 2 1 1 1 1 1
  5 5 5 5 5 5 5 2 2 2 2 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 2
  5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 1 1
  5 5 5 5 5 5 2 2 2 2 2 2 2 2 1 1 1 1
  5 5 5 5 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1
  5 5 5 5 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 1
  5 5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  5 5 5 5 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

ans =


   451

2 comments:

  1. One of our American readers tweeted to say that they were worried there was no 25p coin. Of course, the program works for American coins too!

    It's quite interesting that there are significantly fewer ways to make 50c out of American coins- mostly as there is no 2c piece. There turn out to be 50 ways to make 50 cents, as opposed to 451 to make 50 pence.



    There are 50 combinations to make this amount. These are:
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 5 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 10 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 5 5 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 5 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 10 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 25
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 10 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 5 5 5 5
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 5 5 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 10 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 25
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 10 10 10
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 25
    1 1 1 1 1 1 1 1 1 1 5 5 5 5 5 5 5 5
    1 1 1 1 1 1 1 1 1 1 5 5 5 5 5 5 10
    1 1 1 1 1 1 1 1 1 1 5 5 5 5 10 10
    1 1 1 1 1 1 1 1 1 1 5 5 5 25
    1 1 1 1 1 1 1 1 1 1 5 5 10 10 10
    1 1 1 1 1 1 1 1 1 1 5 10 25
    1 1 1 1 1 1 1 1 1 1 10 10 10 10
    1 1 1 1 1 5 5 5 5 5 5 5 5 5
    1 1 1 1 1 5 5 5 5 5 5 5 10
    1 1 1 1 1 5 5 5 5 5 10 10
    1 1 1 1 1 5 5 5 5 25
    1 1 1 1 1 5 5 5 10 10 10
    1 1 1 1 1 5 5 10 25
    1 1 1 1 1 5 10 10 10 10
    1 1 1 1 1 10 10 25
    5 5 5 5 5 5 5 5 5 5
    5 5 5 5 5 5 5 5 10
    5 5 5 5 5 5 10 10
    5 5 5 5 5 25
    5 5 5 5 10 10 10
    5 5 5 10 25
    5 5 10 10 10 10
    5 10 10 25
    10 10 10 10 10
    25 25
    50

    ReplyDelete
  2. Generating functions are the way to go for doing these sorts of calculations. CoCalc.com notebook (using SageMath) is available at https://cocalc.com/projects/4f3ef6fd-b13b-447c-bf2e-434b03be3a3c/files/Coin%20Combinations.sagews

    If you login to your CoCalc account and then click the blue i in the top left of my notebook, you can make a copy of it to edit and run for your own calculations.

    ReplyDelete

Who are we?

Contact Form

Name

Email *

Message *