A Thinking Ape - Circle of people

Solution for the described problem

Comment

Brief Description

This is a problem described by A Thinking Ape during VanHackaton. In this problem, there is a group of people in a circle, and someone goes around the circle removing each second person. The goal is to know which person will be the last one standing.

The problem is best described in this link.

Graphical Representation

Please see graphical_representation image
Assuming that we enumerate everyone from 1 to N clockwise, and follow the clockwise order when removing persons.

Solution

For a more elaborated answer, and how I got to it, please see further sections.

This problem follows the following pattern:

Circle of 2 - Winner is the 1st person;
Circle of 3 - Winner is the 3rd person;
Circle of 4 - Winner is the 1st person;
Circle of 5 - Winner is the 3rd person;
Circle of 6 - Winner is the 5th person;
Circle of 7 - Winner is the 7th person;
Circle of 8 - Winner is the 1st person;

As we can see, on each power of two, the winner is the 1st person (this will be referenced as a "reboot"). So if we "walk" through the numbers, everytime that we hit a number that is a power of two, we will have a reboot, and the winner will be the 1st person.

The winner on the following circles, will be incremented by 2, so in example:

Circle of 16 - Winner 1
Circle of 17 - Winner 3 (1+2)
CIrcle of 18 - Winner 5 (1+2+2) and so on.

From this, I noticed that the winner can be represented by the formula (please see final_formula image for easier representation):
1 + ( N - 2^(a) ) x 2
Where a is: floor(log2 N)

Something that is good to know is that, if you have a table with the powers of two numbers, the formula is way easier since you can switch 2^(a) with the power of two that predates N (represented by ANT on the formula), and resolve it with basic operations!!!

How I built it

I started this problem while outside of my home, and all I had was my cellphone, so I drew some sketches using it, which can be seen as images (sketches image).
When I got home, I used another tool, far more advanced: Pen and paper (workflow_0, workflow_1, workflow_2).

In order to know which person will be the last one standing, in a group of 'N' persons, this is how to proceed:

  • In a circle of 2 persons, the last one standing (refered as winner from now on) will be the 1st person, since the 2nd was removed on the first 'iteration'.
  • In a circle of 3 persons, the winner is the 3rd person, since we removed the 2nd person on the first iteration, and the 1st person on the second iteration. Something interesting that happens on this case is that, once we remove the 2nd person, this problem falls back to the problem with 2 persons in the circle. Therefore, in this "new" setup, the 1st person (that is actually the 3rd) should be the winner, according to the previous analysis, and that is exactly what happens.
  • In a circle of 4 persons, the winner is again the 1st person. This is something that happens on all circles with a number of people equal to a power of 2 (2, 4, 8, 16, etc...). This is what I call a reboot in the sequence. From this sequence onwards, I noticed that every winner will be incremented by 2, until we hit another reboot, so in example:
    Circle of N people Winner Observation
    2 (2^1) 1 =(1+2x0)
    3 3 =(1+2x1)
    4 (2^2) 1 =(1+2x0)
    5 3 =(1+2x1)
    6 5 =(1+2x2)
    7 7 =(1+2x3)
    8 (2^3) 1 =(1+2x0)

After noticing the increments to the answers (the observations column), I thought that there could me something to be extracted from it, as a mathematical formula, since the sum of multiples of two was following a pattern. My first guess was the first_guess image (please see image).
However, I thought that it was a bit too hard and noticed that I was going from the higher numbers down to smaller ones (16-15-14-...). I then started going the other way, and found out the second_guess (ANT in the formula refers to the power of two number that predates N), but for that I had to had the Powers of two table, which contains "all" numbers that are a power of two, in order to acquire ANT.
After some more analysis, I noticed that ANT (from the second_guess) was actually something described in the first_guess (with a few alterations), and finally came up with the final_formula.

Share this project:

Updates