General Code

Consider an army with 10 generals. One wants a security system such that any three of them can determine the code to launch nuclear missiles, but no two of them can. It is possible to devise such a system by using a quadratic polynomial, such as a ax^2 + bx + c; to launch the missiles, one must input (a,b,c). One cannot just tell each general one of a, b, or c (as then it is possible that some subset of three generals won’t know a, b and c); however, if a general knows two of (a,b,c), then a set of two generals can launch the missiles! What information should be given to the generals so that any three can find (a,b,c) but no two can? What about the general situation with N generals and any M can launch (but no set of M-1) can?

First Thoughts

This seems like a difficult problem to tackle head on, so let’s first consider a simpler case. Let’s think of a way to create a similar missile system for the case where there are 3 generals and any 2 can launch the missiles. A first idea is to use a linear polynomial, ax + b. If we give each of our three generals one of the numbers a or b, we run into the same problem as in the original setup: a situation may arise where some subset of two generals can’t launch the missiles. Similarly, if we give everyone a and b, then each general can launch the missile.

This dilemma suggests that we think of another way to determine the equation of a line. Fortunately, we soon realize that given two points on a line, we can completely solve for the equation of that line. Therefore, if we give each of the generals a point on the line, any subset of two generals can determine the line.

 

Second Thoughts

We now wish to apply the reasoning to our original problem. Perhaps we can give each general a point and have the same result; any collection of three generals can solve for the equation of the parabola. Let’s explore this option. Take any subset of three generals with points (m, n), (r,s) and (u, v). Then we get the following system of equations:

am^2 + bm + c = n

ar^2 + br + c = s

au^2 + bu + c = v

We observe that this is a system of three equations in three unknowns, (a, b, c), since all of the other parameters are already known by the generals (that is, we know m, n, r, s, u, v). We don’t have to worry about there being no solution to this system because we have chosen three points on the parabola we are given, so we know there is at least one parabola through the three points. We must therefore be able to solve this system of equations for a unique (a, b, c).

 

The General Solution:

Following a similar line of reasoning, we see that in the general case with N generals where any M can launch the missiles, we need to give each of the generals a unique point on a degree M – 1 curve.