0
$\begingroup$

$4$ people, designated Black, White, Red, and Yellow, are playing a game. Each of them has unlimited number of balls, all of that person’s designated color. They work together to build a line of balls. Each player can either add one colored ball or throw away the last ball in line and add two colored balls. The game begins with a single green ball.

Find $a_n$ (recursion) if the players plays in a fixed rotation. Then find another $a_n$ that the players can play in any order, provided that no player ever makes two moves in a row.

I'm struggling finding the first $a_n$, anyone has any suggestions?

I thought about the situation if the turns are $B\to W\to R\to Y$. For $B$ we will have two options, and both of them will end with $2$ balls in the line, which means we can finish with $a_{n-2}$ possibilities. With White we will have $3$ balls or $1$ ball in line. With Red we will have $4$ balls or $2$ balls in line if it was $3$ balls after White played, and if we had one ball after White played, we will have $3$ balls or $2$ balls. And there will be $8$ options after Yellow plays. And then we sum all the possibilities into a huge, possibly wrong, equation.

$\endgroup$
  • 3
    $\begingroup$ May I suggest not saying "colored people"? It might be misinterpreted. Also, I don't think the rules are clear. If player $X's$ moves are "add $1$" or "subtract $1$ and add $2$" then in all cases the length of the chain goes up by $1$. $\endgroup$ – lulu Feb 26 '16 at 13:23
  • $\begingroup$ @lulu I see. So it always grow by one. Which means, $a_n = a_{n-2} + a_{n-3} + a_{n-4} + a_{n-5}$ opinions? $\endgroup$ – Ilan Aizelman WS Feb 26 '16 at 13:30
  • $\begingroup$ You did not define $a_n$. If it refers to the length then it is just $n$ (or $n+1$ depending on what you call the first move). If it means the number of possible strings then $a_n=2^n$ (again depending on what you mean by $n$) as each possible path gives rise to two new ones on each turn. $\endgroup$ – lulu Feb 26 '16 at 13:33
  • $\begingroup$ @Ilan: I assume that $a_n$ is either the number of distinct lines that can result after $n$ moves or the number of possible lines of length $n$. Your comment about ‘$a_{n-2}$ possibilities’ makes me think that you mean the number of possible lines of length $n$, but it really isn’t clear; exactly what is $a_n$? $\endgroup$ – Brian M. Scott Feb 26 '16 at 22:36
  • $\begingroup$ @Ilan: Also, I don’t see how you can possibly get $1$ ball in line after White’s first move in the last paragraph: no matter which option a player chooses, he always ends up increasing the length of the line by one ball. $\endgroup$ – Brian M. Scott Feb 26 '16 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.