A Thinking Ape Circular Problem For Kids

Summary

I take the "formulate your answer as a general solution and not as an algorythm" paragraph very seriously in this challenge. In fact that line guided all my problem solving research. I was determined to deliver a solution in a simple and didactic way.

This solution i found for the Josephus problem became so simple that can be used by KIDS. It's really simple because it uses only the four basic math operations (sum, subtract, division, multiplication) and eliminate the "complexity" of the standard algorythm, that uses LOG and exponencial operations.

Hope you guys like it.

The Problem

This is a known problem, its called Josephus problem and it also have it's solution published in Wikipedia.

Knowing that lots of other participants must know the josephus problem, and might use it in their submissions and implementations, i thought i could try solve the problem with another perspective.

The Analysis

After reproducing in the paper lots of sequences i started noticing that each cycle in the number array follows a specific pattern to eliminate the numbers and started mapping the pattern with any other sign that might tell me what pattern should i use.

After another few rounds of cycling in the paper i noticed that the only relevant numbers for the pattern analysis were the first and the last in the array, and also how many numbers are left at the end of each cycle.

Preparing the Solution

Given a number N, lets consider an array from 1 to N.

You will need to draw a table with four columns: First, Last, Quantity and Increment, where First is the first number in the remaining array, Last is the last number, quantity is the size of the array, and increment is a control number that starts at 1 and doubles at each round. The idea is that at each round, a new line is filled in the table.

Increment

Its important not to forget to update the increment. It starts at 1 and doubles at each round. So it will always go like: 1, 2, 4, 8, 16, 32, 64...

First Round

To go from the first line to the second one, you will follow this rule:

• If Last is odd – Keep the last and divide quantity by 2 round up
• If Last is even – Subtract the last by 1 and divide quantity by 2

Next rounds

To find the next lines in the table look for:

• Look if the quantity is even or odd
• Look if the Last is equal to Last from previous line

With these answers follow the pattern steps to calculate the next line

Patterns

There are four patterns that we need to look at and for each one of them specific steps to be taken:

Quantity Even / Last number equals to previous line

• Increase first by the increment
• Divide Quantity by 2

Quantity Even / Last number different to previous line

• Decrease last by the increment
• Divide Quantity by 2

Quantity Odd / Last number equals to previous line

• Increase first by the increment
• Decrease last by the increment
• Divide Quantity by 2, round down

Quantity Odd / Last number different to previous line

• Divide Quantity by 2, round up

The Result

When Quantity reaches 1, the First and Last will be equal, and that is the answer for the problem. See the try it out for examples

Built With

• logic
• math