×   Home   Blog   Newsletter   Privacy   Contact Us   About

Missile Command

A popular arcade game when I was growing up was Missile Command.
The game, developed by Atari, requires you to defend a collection of cities from a barrage of ballistic missiles. You do this by launching counter missiles from three batteries. It is one of few arcade games that uses a track ball. You use the trackball to position an aiming cursor, then press a button corresponding to the battery you wish to launch a missile from.
The early levels are pretty easy, but the game rapidly increases in complexity with the incoming missiles fragmenting into multiple entry warheads, and smart bombs start appearing. When I was younger, I seem to recall the skill curve was pretty steep, and the game rapidly got a lot harder. A tip I remember was that the middle missile battery fired quicker than the two outer ones.
In the classic movie Terminator 2: Judgment Day, the young John Connor is playing Missile Command in the arcade when the T-1000 is searching for him.
Advertisement:

Simplified: Three on Three

If, instead of warheads, the incoming objects were three simple non-fragmenting asteroids, and let’s say there was only one missile left in each of the three defense batteries. Three asteroids, and three missiles, no problem; one each (it’s implied that every launch is a perfect launch, and every shot is a kill shot).
This is fine assuming that there is an overall central command mechanism which coordinates which battery fires at which target, but what if that infrastructure was compromised?
If there are three objectives, and each battery, independently, selects a target at random, what is the probability that all three asteroids will be destroyed?
If each battery fires its missile at a random target, what is the probability that all the targets will be destroyed?
(There’s a canonical variant of this puzzle that I’ve seen and this is that n-people get into an elevator in an n-story building, and each wants to go to a random floor. What is the probability that every rider gets off at a different floor?)
Let’s look a simple case first:

One Asteroid

This is trivial. With one asteroid, and one missile battery, there is a 100% chance of success.

Two Asteroids

This is also trivial. The first battery will fire at an asteroid. There is a 50:50 chance that second battery will fire at the same asteroid, and a 50:50 chance that it will fire at the other. There is a 50% chance of success.

Three or more

Let’s look at the generic solution. If there are n asteroids then there are nn possible ways the missiles could be fired at targets (every missile gets to fire at every asteroid). For instance, with three asteroids, the targets could be {111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333}. This represents the denominator.
Now all we need to find out is the number of these (the numerator) where the three targets are distinct. If there are three missiles, there are three possible targets for the first missile, the second missile has two distinct targets, and the last one. Generically, if there are n missiles, there are n! ways these can hit distinct targets.
So, for n asteroids, with n missiles, the probability of success is n!/nn
For three asteroids, the probability of success is 3!/33 = 6/27 ≈ 22.22%
NN!N^N%
111100.000%
22450.000%
362722.222%
4242569.375%
51203,1253.840%
672046,6561.543%
75,040823,5430.612%
840,32016,777,2160.240%
9362,880387,420,4890.094%
103,628,80010,000,000,0000.036%
I guess a moral of this story is that coordination is good!