Binary Puzzles

binary

This week, we looked at three seemingly unrelated problems which all ended up being related to binary numbers.

The first is about Russian multiplication. Take, for instance 22 x 19.  Multiply the left side by 2 every time and divide the right side by 2, and do this until the right side is equal to 1. If, while you do this, you ever get a decimal number on the right side, round down to the next integer.

e.g.

 22 19
44 9
88 4
176 2
352 1

The next step is to get rid of all the lines with an even number on the right side, which leaves us with 22, 44 and 352 on the left side. Now we know that 22 x 19 = 418. What do you notice when you add 22, 44 and 352? Now try this with other multiplications. Does it still work? If it does, can you explain why it works?

Here is a website that explain this more fully:

https://www.basic-mathematics.com/russian-peasant-multiplication.html

The second problem we looked at today was all about magic cards or maths busking. Have a look at the following cards:

Magic cards

You can do the following trick with them. You ask someone to tell you which colour cards their birthdate appears on. You can straightaway say what their birthdate is. Can you guess how? It is not by learning all the numbers on the cards. One clue is to look at the first number in each card. Can you spot a pattern? Again, here is a website to help you:

http://www.mathmaniacs.org/lessons/01-binary/Magic_Trick/

Extension: If you add one more card, with how many more numbers can you do the trick with?

The final puzzle of today is about poisoned wine bottles. This is the story:

The King of a small country invites 1000 guests to his annual party.

Each guest brings the King a bottle of wine. Soon after, the Queen discovers that one of the guests is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which guest, nor which bottle of wine is poisoned.

Just a single drop of the poisoned wine would kill the King.

The King has 10 prisoners in his dungeon. He decides to use them as taste testers to determine which bottle of wine contains the poison.

The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies. The King needs to determine which bottle of wine is poisoned by tomorrow so that the festivities can continue as planned. Hence he only has time for one round of testing. How can the King administer the wine to the prisoners to ensure that 24 hours from now he is guaranteed to have found the poisoned wine bottle?

As we have seen with a lot of Maths Club problems, sometimes the first step is try with smaller numbers. For instance, instead of using 10 prisoners, we could say that there are 500 prisoners. So how could we test this now? Once you have figured this out, you could try with less and less prisoners. Now, we can solve the puzzle:

First, let’s line up our 10 prisoners and label them. Also label the wine bottles 0–999 so we can tell them apart.

prisoner line up

Label each bottle with both its decimal number and binary equivalent.

decimal=binary
0=0000000000
1=0000000001
2=0000000010
3=0000000011
4=0000000100
5=0000000101
6=0000000110
7=0000000111
8=0000001000
9=0000001001
10=0000001010

etc

Now each bottle serves as a code describing which prisoners are to drink from it. In this system, a one means the prisoner drinks from it, a zero means the prisoner doesn’t.

For example, only Prisoner J should drink from bottle one since its binary is 0000000001. Whereas, Prisoners I and G should drink from bottle ten whose binary is 0000001010 because it has 1’s in the columns that match up with prisoners I and G.

Continue this process until you have given out sips of wine from every bottle. After 24 hours, line up the prisoners in order and note which ones have been poisoned with ones and mark the rest with zeros. Convert this number back into decimal to reveal which bottle was poisoned.

Extension: If there were 2000 bottles, how many prisoners would you need?

If you would like to learn to learn more about binary, check out this website:

https://www.mathsisfun.com/binary-number-system.html

Counting Lattice Paths

counting lattices

This week’s problem is all about counting the number of paths from one point to another on a 4 by 4 grid.

You can only travel in these directions

directions lattice

Here is one acceptable path:

sample path

So how many such paths are there? First off, in which of these ranges do you think the answer lies:

< 20
20 – 40
40 – 60
60 – 80
80 – 100
>100

A first tip on how to solve this is to look at what is going on with smaller grids. Why don’t we start with a 1 by 1 grid? How many different paths are there between the starting point and the end point? Once we have done that, we can place the data on our larger grid.

After doing this a few times, does a pattern start to emerge?

Here is a website that shows all the solutions and an explanation of how the problem works, if you would like to learn more.

http://www.robertdickau.com/lattices.html

River crossing puzzles

wolf

You are on one side of a river, and with you, there is a wolf, a goat and a cabbage. You have one boat, and can only take one living thing at a time. The goat cannot be left alone with the cabbage and the wolf cannot be left alone with the goat. How many journeys must you do in minimum to get all the objects to the other side of the river? In how many different ways can you do it?

Here is a very interesting way to look at the problem which involves representing the problem in 3D wolf/goat/cabbage space.

wolf cube

The problem is then changed to getting from one vertex of the cube to another.

Finally, we looked at another river crossing puzzle, this time involving wildebeest and lions. This puzzle is fully explained and answered in this Ted-Ed talk.

Before looking at how they propose to solve the puzzle, how did you go about solving it?

Benford’s Law

benfordface-e1453738647851

The first task of today was if numbers were chosen at random, what would be the probability that numbers started with the digits 1 to 9. Of course the probability would be the same for each digit.

Ok, let’s see if this works. Go ahead and find any article, it can be a news article, a scientific article, etc. Now count the number of times that each digit 1 to 9 is at the start of a number. Does the distribution seem even?

Let’s see if this trend can be found in mathematical sequences too. Here’s an example: the Fibonacci sequence.

1,1,2,3,5,8, …

Let’s find the probability of numbers starting with digits 1 to 9 in the first 10,000 numbers of this sequence.

Quick tip: you can use excel to do this and then use the countif function to find the distribution of probabilities of numbers that start with each digit. Does the distribution seem even?

Excel first digit

Excel countif

This strange pattern of occurrence is called Benford’s law, and it is very counter-intuitive.

benford graph

If you would like to learn more, click on this link: https://brilliant.org/wiki/benfords-law/

So here is your final challenge: every single time you see a number today, write it down and you can then verify the law for yourself. How close did you get?

Mastermind problems

mastemind

Welcome back to Maths Club!

Today, we looked at a few logic problems based on the popular game, Mastermind. If you have never played it before, you can try online here.

We then answered these interesting questions  about what you can deduce from certain opening moves.

For the answers to these questions and some of the mind bending maths behind Mastermind, have a look at this paper by Tom Davis.

Voting systems

voting

Finding betting ways to vote

We looked at different ways to decide which candidate or choice won a vote. We realised that by using different methods, different candidates won the vote. This raises the troubling question about whether our way of voting is the best and the fairest. Here is a link to the activity we did and here is a link to an interactive website that discuss precisely this question. In the UK, the voting system is relative majority. However, it could be a good thing if we use absolute majority voting, because it would allow members of smaller parties to also get a voice. This could lead to a bigger number of parties rather than two or three major parties. However, there is no perfect voting system.

Gabriel’s problem

Gabriel box

Gabriel wrote the numbers 1-9 in a 3×3 grid.

He then multiplied together all the numbers in each row and wrote the resulting product next to that row.
He also multiplied the numbers in each
column together, and wrote the product
under that column.
He then rubbed out the numbers 1-9.

Can you work out where Gabriel placed the numbers 1-9?

Did you have more information than you needed?

This puzzle comes directly from this NRich page, with the pdf of the problem available here.