\(l\) players are playing a game of Chain Reaction on a \(m \times n\) grid. They start with an empty grid, and then when their turn comes they place on orb on the grid.

Here are two challenging problems:

1) What is the maximum number of moves the game can last?

2) What is the minimum number of moves the game can last?

Answer in terms of \(l, m, \) and \(n\).

Details and assumptions

I haven't solved it, so I don't know the solution. I don't even know if a (nice) solution exists, however it seems like an interesting problem to me and I hope you will like it too. Feel free to use any method(s) to get the answer - pen and paper, marker and whiteboard, programming, Wolfram|Alpha or anything else that you like!

Post below any ideas / strategies that come to your mind that could be used to maximize / minimize the number of moves.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestThe minimum number of moves depends heavily on the starting configuration. As an example, for \(l = 2, \min \{m,n\} \ge 2\), and Player 1 has only one orb on a corner, we can play the following:

However, the general approach is that; get cells of a player to almost reach critical mass (just to aid when they explode), and chain as many as possible together, so that they can be eliminated quickly.

The maximum number of moves is actually reached when all cells have one less than critical mass (so that they don't explode yet), and then one more move is played, triggering an infinite chain reaction.

Log in to reply

Nice observation! To get as many moves as possible, all cells must have one less than critical mass. But then the question arises for what condition on \(l, m, n \) can that state be reached? If that state can not be reached, that what is the next best option?

Note that the we are starting on an empty grid i.e. there is only one starting configuration. For \(l = 2\), the minimum number of moves is less than \(5\), it is in fact \(3\).

Log in to reply

I think maximum no of moves will be independent of no of players since we have to make all orbs reach Critical mass so I'm getting the answer: 3mn-2m-2n not calculated min moves till now.

PS: This will be true when no of players is a factor of total squares, otherwise it's very difficult

Log in to reply

Yes, you are correct; in order to have maximum moves, we must try to make all orbs reach critical mass. Can you prove that if no. of players \(l\) is a factor of total number of squares \(m \times n\), then it is always possible to make all orbs reach critical mass? Also is it true that if \(l\) is not a factor of \(m \times n\), then it is always impossible to make all orbs reach critical mass?

Log in to reply