Here are 3 puzzles that were chosen by Tom to be included in “The House” – the print magazine of the UK parliament – to accompany an article by Baroness Garden on the importance of maths education in the UK. You can read the article here.
Puzzle 1 (Easy):
I want to send a care package to my friend in Australia which consists of several items each weighing between 100-200g. The total weight is 4.1kg. At the post office, I’m informed of the following postage costs per parcel:
0-1kg = £5.00
1-2 kg = £8.00
2-4kg = £10.00
>4kg = £30.00
I notice that it would better to break my package up into smaller pieces to reduce the postage cost, but what breakdown would result in the lowest charge?
Answer at the bottom of the page.
Puzzle 2 (Medium):
I’m moving house, but am only allowed to take one van full of books with me as I try to save space in my new home. I’ve divided the books up into subjects where each box has to travel as a whole, but I’m not bothered as to which ones do and don’t make it. My goal is to take as many books as possible in a van of size 150, without going over the limit. Given the box sizes listed below, what is the maximum amount that I can take with me?
Detective = 52
Horror = 59
Maths = 95
Spy = 37
Fantasy = 27
Science = 16
Politics = 65
Sport = 42
As an example, I could take the ‘Detective’ and ‘Maths’ cases for a total of 52 + 95 = 147, which fits into the van since it is less than 150. But, is it possible to take 148, 149, or even 150?
Answer at the bottom of the page.
Puzzle 3 (Hard):
There are 100 lockers in a row which are all closed. The first person to walk past opens all of the lockers. The second person then closes every 2nd locker they walk past. The third person changes the state of every 3rd locker (so if it is open they close it, and if it is closed they open it). The fourth person changes the state for every 4th locker. The fifth person changes the state of every 5th locker. And so on and so forth.
Once 100 people have walked past the lockers, how many of them remain open?
Scroll down for the answers to all 3 puzzles.
Removing one small item (which we know has a weight of at least 100g) would mean the remainder of the large package would weigh between 2-4kg and so could be sent for £10. The last item could then be sent as an individual parcel for an additional £5, giving a total cost of £15.
I can make exactly 150 as follows: Science (16) + Fantasy (27) + Sport (42) + Politics (65) = 150. So, unfortunately it looks like my maths books are being left behind!
There isn’t actually a specific method to find this solution beyond trial and error. The problem is part of a larger class of problems called NP problems, which are the subject of a million-dollar question which asks whether or not a quicker method of solution exists in general.
First note that a locker will be open only if it has had its state changed an odd number of times (since they all start closed). Due to the rules in which they are opened/closed, this means the number of the locker must have an odd number of factors. Therefore, the number that remain open is just the number of integers from 1 to 100 that have an odd number of factors. So, the question is which ones are they?
Take a simple example of the number 6. It can be made by 6 x 1, and 2 x 3, so in total it has 4 different factors. What about a prime number such as 5? Well this is 5 x 1 and nothing else, so it has 2 factors.
Now, in both of these cases we have an even number of divisors, and in fact this will almost always be true because they come in pairs. If you have one number as a factor, then it must be multiplied by something else to give the starting value. So, if the factors of any number come in pairs, how can we end up with an odd number?
We can have a repeated factor. For example, 3 x 3 = 9. In this instance we have a further two factors from 9 x 1, but overall the number nine has 3 factors – an odd number!
So, to answer our original question, we just need to know which numbers have a repeated factor (like 3 in the example above). If we call this repeated factor k, then we need all numbers that are equal to k2 for some number k, in other words the square numbers!
These are relatively straightforward to list for the first 100 numbers: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 – which means we have exactly 10 square numbers, and so 10 numbers with an odd number of factors, and therefore 10 lockers that will be open at the end.