100 Prisoners Problem

From Wikipedia:

“The 100 prisoners problem is a mathematical problem in probability theory and combinatorics. In this problem, 100 numbered prisoners must find their own numbers in one of 100 drawers in order to survive. The rules state that each prisoner may open only 50 drawers and cannot communicate with other prisoners after the first prisoner enters to look in the drawers. At first glance, the situation appears hopeless, but a clever strategy offers the prisoners a realistic chance of survival.

Anna Gál and Peter Bro Miltersen first proposed the problem in 2003.”

In maths club we tried this problem with just 10 prisoners. You can read about the strategy here.

We analysed the percentage chance of winning by looking at the different possible cycles for 10 prisoners.

Daisy chain

We found this activity on Nrich and it was originally in one of Brian Bolt’s books and developed by MEDIAN in their collection of interesting number resources.

This Daisy is special because you can make every number from 1 to 25.
You are only allowed to add neighbours (numbers touching each other) and you can
only use each number once in a sum.

1 = 1
2 = 2
3 = 1 + 2
4 = 4
5 = 5
6 = 2 + 4
7 = 1 + 2 + 4
8 = 5 + 1 + 2
9 = 4 + 5
10 = 7 + 1 + 2
11 = 5 + 4 + 2
12 = 5 + 4 + 2 + 1
13 = 7 + 6
14 = 7 + 6 + 1
15 = 7 + 6 + 2
16 = 7 + 6 + 2 + 1
17 = 7 + 5 + 4 + 1
18 = 7 + 5 + 4 + 2
19 = 7 + 5 + 4 + 2 + 1
20 = 5 + 7 + 6 + 2
21 = 5 + 7 + 6 + 2 + 1
22 = 4 + 5 + 7 + 6
23 = 5 + 7 + 6 + 1 + 4
24 = 5 + 7 + 6 + 2 + 4
25 = 5 + 7 + 6 + 2 + 4 + 1

Can you do better than this with a different set of numbers?
The challenge is to find six numbers to go in the Daisy from which you can make all the numbers from 1 to a number bigger than 25.

You can check your ideas here:

Could you adapt the program above to search for a higher solution?

To write the program above we needed to find all the combinations from a general daisy like this:

For example you can have a+b or a+f but not a+d. Can you find all the combinations? There is a worksheet to fill in here (with the solution on the second page). An editable version is here.

Paper punching

Take an A4 piece of paper.

Fold it a few times.

Then punch a hole through the paper.

Before you unfold your paper, can you draw on a fresh piece of paper where you think the holes will be?

Then can you fold a piece of paper and punch it to make the holes look like this:

Then can you fold and cut a piece of paper to make it wider then it was originally? Can you cut in such a way that you can step through it?

Similar ideas can be found here. Solution to stepping through it here.

Coin problem – Frobenius numbers

Challenge 1
Imagine you have an endless supply of 5p and 7p coins. You could make exactly 20p with four 5p coins. Or you could make exactly 19p with two 7p coins and a 5p coin.

What is the biggest amount that you cannot make? Can you explain why you can make all amounts after this one?

Challenge 2
The biggest number you cannot make given coins of value x and y is called the Frobenius number.

Can you think of a pair of numbers that wouldn’t have a Frobenius number?

What must be true about the two numbers for them to have a Frobenius number?

Challenge 3
Can you come up with a formula for the Frobenius number, if it exists, for two numbers x and y?

Solutions here.

Kaprekar’s number on Python

Mr D. R. Kaprekar was an Indian school maths teacher who loved playing with numbers. See if you can follow these steps to find out what he discovered …

Choose a four digit number where the digits are not all the same (that is not 1111, 2222,…).

Rearrange the digits to get the largest and smallest numbers these digits can make.

Finally, subtract the smallest number from the largest to get a new number, and carry on repeating the operation for each new number.

What do you notice?

Does something similar happen for 3 digit numbers? Can you prove it?

Here are pdfs of the problem in English and French.

Try it out here