I hope this doesn't fall under the "not interesting to mathemeticians" category.
I'm attempting to solve one of the facebook engineering puzzles. Essentially, the idea is that two dancers do a dance-off with a predefined number of moves. For every turn, the dancer has to begin with the last move the other dancer used. Every time a combination of moves is used, both that combination and its reverse are excluded. For instance, if you do (1, 2), then neither dancer can do (1, 2) or (2, 1). Dancers may repeat moves. The dancers will dance optimally, and the battle is over when there are no more moves left.
My first thought when trying to solve this went like this: the dancers are essentially building a B(n, 2) de Bruijn sequence. The length of the sequence should be n^2. I figured that if the number of turns is odd, then you win. If the number of turns is even, then they win. Thus since n^2 will be odd if n is odd, and n^2 will be even if n is even, all I did was check to see if it was odd or even to determine the winner. This wasn't the correct answer.
So here's my current way of thinking: the dancers are going through a de Bruijn graph. For every turn, two vertices are considered visited unless it is a duplicate (like (1, 1) or (2,2)). Therefore, the number of turns available would be 2^n - n. But this just seems like a more complex way to do the same thing as I was doing above. After all 2^n will always yield a positive, so this will yield an even if n is even and an odd if n is odd.
I don't really want to ask anyone to solve this for me (I want to solve it on my own). But can someone at least tell me if I'm on the right path, or is there something fundamental I'm missing?
