Problem Statement
In the King Arthur Problem, King Arthur is playing a game with his knights at the table. All the knights are seated around the table, and King Arthur is standing up. To start, King Arthur selects one knights, that knight is "in". King Arthur then moves in one direction, selecting the next knight in the circle. That knight is "out". King Arthur continues moving around the table in this fashion, alternately selecting knights to be "in" and "out". "In" knights stay at the table, and "out" knights leave the table. The goal of the game is to be the last knight at the table.
Our job was to find a formula to quickly determine the winning seat for any given number of knights at the table.
In the King Arthur Problem, King Arthur is playing a game with his knights at the table. All the knights are seated around the table, and King Arthur is standing up. To start, King Arthur selects one knights, that knight is "in". King Arthur then moves in one direction, selecting the next knight in the circle. That knight is "out". King Arthur continues moving around the table in this fashion, alternately selecting knights to be "in" and "out". "In" knights stay at the table, and "out" knights leave the table. The goal of the game is to be the last knight at the table.
Our job was to find a formula to quickly determine the winning seat for any given number of knights at the table.
Process
My first attempts at solving the problem was to literally draw the circle table with the knights, and eliminate knights as King Arthur would have walked around the table. This helped me understand the game and visualize how each knight is eliminated until only one is remaining.
My first attempts at solving the problem was to literally draw the circle table with the knights, and eliminate knights as King Arthur would have walked around the table. This helped me understand the game and visualize how each knight is eliminated until only one is remaining.
After drawing the diagram of the table and the knights, my group and I started generating the winning seat number for each possible number of knights at the table, starting with one. We represented our data in a table, with "k" as the number of knights initially seated at the table, and "w" as the winning seat.
After the first sixteen-or-so knights, we discovered a pattern. For every value of k that is a power of two, (1, 2, 4, 8, 16...), the winning seat is one. We also noticed that, starting with each value of k equalling to a power of two, the winning seat increases by two. Starting with k=4, for example, the winning seat is 1, 3, 5, 7, and back to one at k=8, from there, the winning seat is 3, 5, 7, 9, 11, 13, 15, and back to one at k=16. We continued to calculate the wining seat all the way up to k=2^6 (64), and found the pattern continues.
However, we still needed to generate some sort of formula to quickly determine the winning seat. We found that by multiplying two times the difference between the number of knights and the last value of the number of knights equalling to a power of two, and then adding two, the winning seat can be determined. Written somewhat mathematically, this is what we came up with:
Solution
In the end, Mr. B showed us the correct formula or finding the winning seat, and out group was basically correct, it's just that we did not know the mathematical notation to represent "the last value of k equalling to a power of two". This is the correct notation:
In the end, Mr. B showed us the correct formula or finding the winning seat, and out group was basically correct, it's just that we did not know the mathematical notation to represent "the last value of k equalling to a power of two". This is the correct notation:
The only difference between our equation and the equation that Mr. B showed us was that instead of writing "the last value of k equalling to a power of two", we write "2^[(log2(k))]+1". When we raise 2 to the power of [(log2(k))], we are asking: "two to the power of (blank) equals k? If this number is a decimal, we round down to the nearest whole exponent. From there, we raise the base, two, by this exponent and solve.
To confirm that this formula is reliable, we tested it with various values of k and checking our answers using our table. Here is our work in plugging in k=12:
Evaluation/Reflection
"What pushed your thinking?"
The part of the problem that pushed my thinking the most was the part where we had to generate a formula to predict the winning seat given any value of k. Gabe was the one who showed our group the somewhat mathematical form of the equation, and I remember not understanding why is was k-, or why we had to add one at the end.
In what ways were you challenged?
I was challenged to understand the new notation that Mr. B taught us. At first
"What pushed your thinking?"
The part of the problem that pushed my thinking the most was the part where we had to generate a formula to predict the winning seat given any value of k. Gabe was the one who showed our group the somewhat mathematical form of the equation, and I remember not understanding why is was k-, or why we had to add one at the end.
In what ways were you challenged?
I was challenged to understand the new notation that Mr. B taught us. At first