# Travelling Light

I'm off hiking and I need to buy a bus ticket to the mountains. The ticket costs £4.25 and I have the following coins in my pocket:

2 x £2, 4 x £1, 50p, 3 x 20p, 2 x 5p, 2p, 7 x 1p

Weight is everything when you're climbing big mountains so I want to make sure I'm carrying as little as possible when I set off. Luckily I had the foresight to check the Royal Mint's website and look up exactly how much each coin weighs.

£2 - 12.0 grams

£1 - 9.5 grams

50p - 8 grams

20p - 5 grams

10p - 6.5 grams

5p - 3.25 grams

2p - 7.12 grams

1p - 3.56 grams

It's around this time that I consider that moving to the US and using notes for much lower denominations would really benefit me! Perhaps for my next trip!

Buses in the UK are often expect exact change, what coins should I give the bus driver so that I'm left with the smallest possible weight to carry on my hike and how much will that be?

Edit: For whatever little its worth 100p = £1

• BTW, my Dictionary of Number extension says: 50p - 8 grams [≈ Coins of one Euro and one U.S. dollar]
– JNF
Nov 12, 2014 at 10:59
• Sounds like the knapsack problem.
– kai
Nov 12, 2014 at 11:46
• Do you need to be able to pay exactly 4.25 on the way back aswell? Nov 12, 2014 at 12:26
• @TimCouwelier interesting expansion but let's assume it's a return ticket Nov 12, 2014 at 12:41
• @Liath, okay, fair enough. In that case it still doesn't make much sense for the amount to be an odd number, but I guess I'll just go with it. Nov 12, 2014 at 14:11

We can first ammend the list with grams per penny, because we want to spend the most grams per penny possible, so money with a higher g/p should be spent first:

2 £2  - 0.06  g/p
4 £1  - 0.095 g/p
1 50p - 0.16  g/p
3 20p - 0.25  g/p
2  5p - 0.65  g/p
1  2p - 3.56  g/p
7  1p - 3.56  g/p


As expected there are no exceptions to smaller coins = more grams, so we simply try to get as much small coins as possible to combine to £4.25

all coins below £1 together are 129p togehter with 3x£1 we are at 4.29 and have to shave off 4p, so we have to leave 4 single pennies or the 2p and 2x 1p. Since we don't have any smaller change left, it won't bring any benefit to switch things araound, since the overall gram per penny ratio will only drop.

So overall:

5x1p 2x5p 3x20p 1x50p 3x£1

This would be more interesting, if there were some valuable coin with more weight...

You've got £9.29 in your pocket, so give him all but 4p (either in pennies or with the 2p in there) and ask for a fiver in the change. According to this, a five pound note weighs 0.812 grams. So that plus the remaining pennies (14.24 grams) would be 15.052g to lug up and down the mountains.

• I do like this thinking outside the box but the question does say you have to pay with exact change (believe me, bus drivers don't like handing out change!) Nov 12, 2014 at 12:17
• Oh I know, but this way, the bus driver gets more change and is better able to offer change to passengers who get on after you do. Perhaps not precisely within the bounds of the question, but it'd probably go down OK IRL. Nov 12, 2014 at 12:23
• I think this should be the accepted solution.
– SQB
Nov 12, 2014 at 12:38
• @SQB it's certainly what I'd do! Nov 12, 2014 at 12:40
• The buses in my town don't allow for the driver to give change. You drop your money into a transparent cylinder, the driver looks at it to make sure it looks correct, then the driver presses a lever to release the trap door at the bottom of the cylinder and deposit the money into the piggybank.
– rob
Nov 12, 2014 at 18:17

3 x £1
1 x 50p
3 x 20p
2 x 5p
5 x 1p

That would leave you with 47.74 grams from the original 123.54 grams

• You are correct, i bruteforced the solution.
– kai
Nov 12, 2014 at 12:46

Buses in the UK are often expect exact change, what coins should I give the bus driver so that I'm left with the smallest possible weight to carry on my hike and how much will that be?

Here's my answer to the original question as stated above:

Just because the driver expects exact change doesn't necessarily mean the driver can only accept exact change for the listed bus fare. The driver can also accept more than the listed fare. You don't need any money for the return trip (as clarified in the question comments), so you give the driver all your change, leaving you with 0g to carry on your hike.

• I like this. A hiker doesn't want to be carrying any loose change up and down a mountain. Nov 13, 2014 at 1:31

Let's look at these coins and calculate their "density". In general, you want to use the coins with the highest density.

Worth (£) Weight (g) Density (g/£)
2.00 12.00 6.00
1.00 9.50 9.50
0.50 8.00 16.00
0.20 5.00 25.00
0.10 6.50 65.00
0.05 3.25 65.00
0.02 7.12 356.00
0.01 3.56 356.00

We see that it doesn't matter if you use 1 x 2p, or 2 x 1p, and neither does it matter whether you use 1 x 10p, or 2 x 5p.

Since the total value of all coins under 5p comes to 9p, we're stuck with 4p no matter what unless we tip the driver.
The £2 coins are least dense, followed by the £1 coins, so we try to keep as many of those as possible.
So first we spend our 50p, 2 x 20p, 1 x 5p, 1 x 2p, and 3 x 1p for our first pound. After that, we have to spend 3 x £1 to make up the rest, since the remaining smaller coins do not reach up to another pound. We're still 25p short, we pay this by using 1 x 20p and 1 x 5p.

So we've spent 3 x £1, 1 x 50p, 3 x 20p, 2 x 5p, 1 x 2p, and 3 x 1p, for a total weight loss of 75.80 grams, which leaves us with 2 x £2, 1 x £1, and 4 x 1p for a total of £5.04 at a weight of 47.74 grams.