
	Advertisement

How to avoid being turned into soup! (Monster’s revenge)

A few weeks ago, I wrote an article about How to escape a monster (using calculus). You successfully escaped the monster! Congratulations. The monster, however, wants his revenge.

He still wants to eat you.

He captures you, ties you up, and tells you he is going to make a giant bowl of vegetable and person soup.

In addition to you, he has many, many bags of fresh vegetables to put into the soup. He starts a fire, puts on a big cauldron of water to boil, and arranges his ‘ingredients’ in a giant circle around the fire. Then he then explains his devious plan …

How a monster makes soup

The monster tells you he is going to place all the ingredients (but one) into the soup, one-by-one. But rather than work in order he’s going to walk his way around the ingredients skipping every other ingredient as he goes.

“Skip, Into the pot, Skip, Into the pot, Skip, Into the pot …”

He says he will tell you which ingredient he’s going to start with (we’ll call this position #1), then he’ll continue going around and around, alternately skipping and throwing in ingredients.

Obviously, being a hungry monster, he’s not going to finish throwing in ingredients after one circuit, he’s going to carry on going.

Of course, now, there are less ingredients outside, but this does not stop him. He’s going to carry on with the “skip one”, “toss one” strategy until there is just one ingredient left.

In the diagram on the left, the red arrows show the progress in the first circuit (starting from the top), the green arrow shows what will start to happen on the next circuit.

On each loop around the circuit there will be fewer and fewer ingredients.

The monster makes you a deal: If you are the last ingredient left, you are free to go. He also tells you that you are free to stand anywhere in the circle you choose. You quickly count and determine there are 99 other ingredients in the soup (making 100 including you). Where should you stand to avoid being turned into a monster’s lunch?

Where should you stand to avoid being turned into a monster’s lunch?

Let’s start simply …

Before working on the solution to the 100 ingredient puzzle (and hopefully a generic solution), let's take a step back and look at the first few simple monster soup recipes and see what we can learn from these.

Here are the recipes for 2,3,4 ingredients:

2 ingredients
** Start **
Skip: #1
Push: #2
** Finished **
Survivor: #1

3 ingredients
** Start **
Skip: #1
Push: #2
Skip: #3
Push: #1
** Finished **
Survivor: #3

4 ingredients
** Start **
Skip: #1
Push: #2
Skip: #3
Push: #4
Skip: #1
Push: #3
** Finished **
Survivor: #1

Here are the next four recipes:

5 ingredients
** Start **
Skip: #1
Push: #2
Skip: #3
Push: #4
Skip: #5
Push: #1
Skip: #3
Push: #5
** Finished **
Survivor: #3

6 ingredients
** Start **
Skip: #1
Push: #2
Skip: #3
Push: #4
Skip: #5
Push: #6
Skip: #1
Push: #3
Skip: #5
Push: #1
** Finished **
Survivor: #5

7 ingredients
** Start **
Skip: #1
Push: #2
Skip: #3
Push: #4
Skip: #5
Push: #6
Skip: #7
Push: #1
Skip: #3
Push: #5
Skip: #7
Push: #3
** Finished **
Survivor: #7

8 ingredients
** Start **
Skip: #1
Push: #2
Skip: #3
Push: #4
Skip: #5
Push: #6
Skip: #7
Push: #8
Skip: #1
Push: #3
Skip: #5
Push: #7
Skip: #1
Push: #5
** Finished **
Survivor: #1

Are you starting to see a pattern?

Each circuit around the circle removes half of the remaining ingredients (if there were an even number of ingredients, or one less if odd). The position to stand should never be an even number (or what will be an even number on the next round).

Here are details of the the surviving ingredient for a few more recipes:

# Ing	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
Safe	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	1

The top row is the number of ingredients. The bottom row is the number of the safe place to stand.

If you look closely, you will see that when the number of ingredients is a power of two (2ⁿ) the survivor is always in position #1. If you think about this for a second, this makes sense. Each cycle around the ring halves the number of ingredients left. If you start with 32 ingredients, then after one circuit there will be 16, then 8 … finally down to 2, and we know that for 2 ingredients, the survivor is #1. Through a process of induction, we know the solution to powers of two ingredients.

So, we have our answer for when there are 2ⁿ ingredients, but what happens if there are 2ⁿ+1 ingredients? Well, this is not much more complicated, because the monster pushes ingredient #2 into the pot, and now we are back to a 2ⁿ problem; the only thing that has changed is that the safe position has rotated around from ingredient #1 to ingredient #3 (Do you see that?)

After eliminating the extra ingredient, the problem returns to the 2ⁿ case!

We're almost there

With just a little thought we can continue this logic and show that if we have 2ⁿ + k ingredients (where k < 2ⁿ), once you have pushed in k ingredients, there are only 2ⁿ ingredients left, and the safe position is 2k+1.

# Ing	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
k	0	1	0	1	2	3	0	1	2	3	4	5	6	7	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	0
Safe	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	1

You can see this in the table above. The top row, as before, shows the number of ingredients. The middle row (k) shows the remainder after having subtracted the largest possible power of two possible. The last row shows the safe position, which as we can see is 2k+1

Mathematicians have a function called floor(x), which is the largest integer not greater than x. It can be represented with square braces missing the top part.

Using the function log₂ in combination with the floor function, we can determine the power of two that does not exceed the number of ingredients, and using a little algebra, we can generate a formula for the generic safe position (where n is the number of ingredients).

Answer for 100 ingredients

If we plug 100 into the equation above we find out that the correct position to stand is in position #73

I'm sorry Mr Monster. I hope you like vegetable soup!

Josephus Problem

This puzzle is not my invention. It is a classic computer science puzzle, and given the name The Joesphus Problem.

It's a great little puzzle to cut your teeth on because of the different ways it can be solved. It's simple enough that, for reasonable values of n, you can simply brute-force a solution by walking through the process. If you like, you can create an elegant recursive solution, and of course, we solved it by the process of induction.

Here's a graph of how the safe position ramps up every other position up to the next power of two.

Binary

There's a very geeky, curious, equivalent to our solution if we express the number of ingredients in binary.

Let's recall our solution:

Subtract from n the largest power of 2 less than n
Multiply by 2
Add 1

If we want to subtract the largest possible power of two from a binary number, this is equivalent to removing the leftmost digit "1" from the binary number.

e.g. for 100_DEC, which is 1100100, the result is 100100

Next, we need to multiply by two, and this is the equivalent of shifting the binary number one position to the left (padding a zero at the end). The result is 1001000

Finally, we need to add a 1, which is the same as changing the zero at the end of the number to a 1. The result is 1001001 (which we know is 73, the solution to the puzzle).

What this simplifies down to is that all we need to do is move the left most digit "1" of the binary to right hand side of the number, and we have our solution! How cool is that?

You can find a complete list of all the articles here. Click here to receive email alerts on new articles.