| medium | discrete |
Assume 100 zombies are walking on a straight line, all moving with the same speed. Some are moving towards left, and some towards right. If a collision occurs between two zombies, they both reverse their direction. Initially all zombies are standing at 1 unit intervals. For every zombie, you can see whether it moves left or right, can you predict the number of collisions?
On every collision, assume that the two zombies don't reverse direction but simply cross each other.
Since we can assume that zombies can pass through each other, for a zombie moving right, count the number of zombies to its right moving left. Add this number for every right moving zombie. That is the number of collisions.