Problem Statement
King Arthur set up chairs around a table, starting with 1 and continuing around the table until he had enough chairs for each knight. Once all the knights were sitting down, King Arthur went behind chair #1 and said, "You're In" then went to chair #2 and said, "You're Out" so that knight has to leave his seat and watch the game at the side of the room. If the seat was empty, the king simply skipped it and went on to the other knight. The king went around the table with the same manner until there was only one more knight left which was of course, the winner.
The amount of knights varied day to day due to some of them being sick, chasing dragons, or doing the king's work. Some days, there were only a handful and some days, there were hundreds!
Our task was simple but challenging, develop a general rule, find a formula or a procedure that would find out the winning seat no matter how many knights there were in the room.
The amount of knights varied day to day due to some of them being sick, chasing dragons, or doing the king's work. Some days, there were only a handful and some days, there were hundreds!
Our task was simple but challenging, develop a general rule, find a formula or a procedure that would find out the winning seat no matter how many knights there were in the room.
Process
To start things off, my group decided to write out a table of sorts to see who would win with a certain amount of knights at the table, and then we put our information on a proper table (top image). We counted the numbers and their solutions all the way up to the number 10 and that is when we noticed that a pattern popped up. We saw that an even number could never win the game because the reset would never have an even (Image 2).
Next on the table we notice the winner would always be plus two from the last number(ex. 1,3,5,7,9, and so forth). Me and my group saw a few patterns but we really couldn't explain our findings. In those situations like that we would call for help and then based on those trends we were able to test more numbers and see how far they really went. We also found connections to base 2 numbers (2^x). With most of the information we gathered , from our groups and outside groups, we were able to create four rules.
Next on the table we notice the winner would always be plus two from the last number(ex. 1,3,5,7,9, and so forth). Me and my group saw a few patterns but we really couldn't explain our findings. In those situations like that we would call for help and then based on those trends we were able to test more numbers and see how far they really went. We also found connections to base 2 numbers (2^x). With most of the information we gathered , from our groups and outside groups, we were able to create four rules.
- The winning seat will always bean odd number.
- The winning seat went up by two each time you raised the number of knights by one.
- The winning seat would reset to 1 after each base two exponent.
- The equation would have to reset hence only one knight can win.
Solution
With the patterns my group and I found, we began to see if we could make a formula or an equation. Our final equation ended up being that you take the number of knights and subtract it by the nearest greatest integer of a base two exponent. With that you have to multiply it by two and added one to get the winning seat. We created an initial formula and tried it out on several numbers from our table. If the equation didn't work we would just try other numbers. In order for our equation to work we had to try it on large and small numbers. In the end we created this equation, ws = 2(k - 2^p) + 1. WS being the winning seat and K being the number of knights at the table. 2^p is the previous greatest integer of a base two exponent. To put 2^p into words, basically if your number was 30, the closest base 2 number would be 16 and you would subtract those two numbers. In the end, it worked for every number plugged in, so it became our final answer.
Evaluation
Even though I wasn't with my group for two days, I caught up very good and I understood the problem statement in about 3 minutes thanks to my group. I was very interested in the problem as soon as I understood it because I could connect to it to the General's Lock problem. With this previous knowledge, I knew I'd have to implement some kind of logarithm into this equation but I struggled mainly due to the fact that I forgot a lot about the problem. I felt very confident diving into the problem when I first read it and I felt even more confident when it came to asking for help. Especially during the group test, there were questions flying around and they were all successfully answered. With this, I think that my group deserves an A+ for the group test and for effort even though we didn't find a solution to the problem.
UPDATE:
I was still curious about how to apply the logarithm into this problem and I found out an equation that would work for any number. Here it is!
2 (x - 2 [[log^2(x-1)]])
UPDATE:
I was still curious about how to apply the logarithm into this problem and I found out an equation that would work for any number. Here it is!
2 (x - 2 [[log^2(x-1)]])
