Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Problem 1092. Decimation

Created by James

When dealing to the Roman Army, the term decimate meant that the entire unit would be broken up into groups of ten soldiers, and lots would be drawn. The person who was unlucky enough to draw the short straw would be executed by the other nine members of his group.

The bloodthirsty Roman Centurion Carnage Maximus decided to apply this to his prisoners, with a few gruesome differences. Rather than kill every tenth prisoner and allow the rest to live, he is going to leave only one prisoner alive and kill all of the others. Instead of killing every tenth prisoner, he chooses a number (kill_every). If kill_every=3, he kills every third prisoner. If kill_every=5, he kills every fifth prisoner. He always chooses a number between 2 and the number of prisoners he has, and this process will be repeated until there is only one prisoner left. For example, if there are 10 prisoners, and kill_every=3

First iteration: 1 2 3 4 5 6 7 8 9 10

1-2-3 4-5-6 7-8-9 10

Prisoners 3, 6 and 9 will be killed.

Second iteration: 1 2 4 5 7 8 10

Because Prisoner 10 was counted during the first iteration, the executions will proceed as such: 10-1-2 4-5-7 8-10, so prisoners 2 and 7 will be killed

Third iteration: 1 4 5 8 10 8-10-1 4-5-8 10, so prisoners 1 and 8 executed.

Fourth Iteration: 10-4-5 10 Prisoner 5 is executed.

Fifth iteration: 10-4 10 Prisoner 10 is executed

Since the sole survivor is prisoner 4, he is released.

You are an unlucky prisoner caught by Carnage Maximum. Prior to lining up the pirsoners, he reveals the number of prisoners he has and his value of kill_every for the day. Your job is to figure out which prisoner you need to be in order to survive. Write a MATLAB script that takes the values of num_prisoners and kill_every. The output will be survivor, which is the position of the person who survives. If you write your script quickly enough, that person will be you.

Good luck!

Problem Group

Solution Statistics

33 correct solutions 16 incorrect solutions
Last solution submitted on Jun 30, 2014

Problem Comments

Solution Comments