Circle Challenge - A Thinking Ape

Question

"Imagine you have a circle of people and you go around the circle removing every second person until one person is left. If you have 3 people in the circle, then the 3rd person will be the last one remaining. If you have 4 people then the 1st person will be the last one remaining. If you have 11 people then the 7th person will be the one remaining. If you have N people in the circle, who will be the last one remaining? Please formulate your answer as a general solution and not as an algorithm that simulates the problem."

Answer

After some hours thinking and testing, we got a solution for the challenge. We will use this nomenclature to declare our math: N = Number of persons in circle; U = Last person in circle; M = Biggest multiple of 2 which is lower then N; E = Number of persons between N and M;

After many calcules, we catch some things:

The last person always will be a odd number.

that always a number of persons is a multiple of 2, the last persons will be 1. e.g.: f(2) = 1; f(4) = 1; f(8) = 1; f(16) = 1; f(32) = 1;

In intervals of multiples of 2, the last person always be added by 2 for each number of persons in circle. e.g: f(4) = 1; f(5) = 3; f(6) = 5; f(7) = 7; f(8) = 1

If f(N) is a multiple of 2 (2, 4, 8, 16, 32, 64, etc), so E always be 0, because U will be value 1. So we have the follow information:

N = M + E; E = N - M; M = 2x multiple of 2 there are more closer of N; U = 2.E + 1;

Samples: N = 21

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

N = 21 U = 11 M = 16 E = 5

N = 32

1 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 = 32 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 = 16 1 5 9 13 17 21 25 29 = 8 1 9 17 25 = 4 1 17 = 2 1 = 1

N = 32 U = 1 M = 32 E = 0

Built With

• logic
• math