Tuesday, December 09, 2008

Math Olympiad Problem

Last week, I worked on one of the problems from this year's Mexican Math Olympiad (a math competition for really bright high school students in Mexico). In the actual competition, you get 9 hours to complete six problems (broken up over two 4-1/2 hour days). The problem I worked on was probably one of the easier ones, but I really don't know.

In any case, it took me a number of hours working on it in pieces before I came up with a solution. My solution was actually quite inelegant, but it was verified to be correct. So, I'm pleased with that. I haven't really tried any of the other problems, but I'm guessing that I couldn't solve most of them anyway (they're quite tough).

So, for those of you that enjoy a mathematical challenge from time to time, here's the problem.

There are N knights seated at a round table. Call the knights K_1, K_2, K_3, ..., K_N. The king decides to play a game to reward one of his knights. Beginning with K_1 and going clockwise, the knights will say the numbers 1, 2, 3, 1, 2, 3, 1, 2, 3, and so on. Note that each knight says only one number, before moving on to the next knight who will say the next number.

If a knight says 2 or 3 on his turn, then he immediately gets up and leaves the table. This little game continues until there is only one knight left at the table, and that knight is declared the winner.

For example, if N=7, then knights will say 1, 2, 3, 1, 2, 3, 1 in the first round. This leaves behind only K_1, K_4, K_7 for the second round. At this point, K_1 will say 2 (since, that's where we left off after Round 1), K_4 will say 3, and the winner will be K_7, as all the other knights are gone.

Now, here's the actual question: Find all the values of N such that the winner will be K_2008.


Lisa Mani-Chang said...

WTF....I feel like I'm reading the blogger of that kid in Good Will Hunting. Haha...only you would do a math problem for fun.

Brute Force said...

Hey man, don't knock it till you try it :).

It's pretty satisfying when you spend a long time and finally finish a problem. It's probably a similar feeling as finishing up a crossword puzzle or something.