Qm
Brainteasers

A hundred walkers who turn around when they collide

invariantcountingrelative-motionants

A hundred robots stand on a long straight line, one metre apart, numbered 1 to 100 from left to right. Robots 1 to 50 start walking to the right and robots 51 to 100 start walking to the left, all at the same speed of one metre per second. Whenever two robots meet, both instantly reverse direction and keep walking at the same speed. The line is long enough that nobody ever falls off.

How many collisions occur in total?

Show a hint

When two identical robots bounce off each other, the picture looks exactly as if they had walked straight through each other. Use that.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Balls and Bins and the Birthday ProblemBinomial Coefficients and Pascal's TriangleBurnside's Lemma and Polya CountingCatalan NumbersCounting: Permutations and Combinations

Related questions

How often are the clock hands exactly opposite?How many times do the hands overlap in a working day?The crazy clock with hands going opposite waysSplitting a deck in the darkSplitting a team and scoring the products
All questions →