I found the following derivation using Lagrange multipliers for the solution of the Core Training problem in Code Jam this year. I liked this approach particularly because I don't get to use Lagrange multipliers very often in programming competitions.

Let denote the initial vector of success probabilities that we are given, and let be an arbitrary vector of success probabilities. Let denote the probability of exactly *i* cores succeeding given the success probabilities in . Then we are trying to maximise

subject to

By using the Lagrangian method, we get that an optimal solution must satisfy

or it must be on the boundary (but we'll get to that later).

#### Lemma

where is the vector of probabilities with *p*_{i} removed, i.e. (*p*_{1}, *p*_{2}, ..., *p*_{i - 1}, *p*_{i + 1}, ..., *p*_{n}). That is, the partial derivative of *f* with respect to *p*_{i} is the probability that exactly *K* - 1 of the cores succeed, not including core *i* itself.

#### Proof of Lemma

This is a somewhat well-known derivation, but I have included it for completeness. By expanding the terms,

which simplifies to

(End proof.)

In order to have , then the most obvious thing to do is to set all the *p*_{i} equal to each other. However this is not possible, since we cannot reduce *p*_{i} below *p*^{0}_{i}. By taking into account boundary conditions, this then gives us three choices for each core *i*:

- We leave
*p*_{i}at its initial value*p*^{0}_{i}. - We increase
*p*_{i}to 1. - We try to equalise
*p*_{i}with the some other {*p*_{j}} that are not on the boundary.

This observation is sufficient to restrict the solution space to the point where we can search over it. (Well, we still need to make some efficiency arguments, like "only increase *p*_{i} up to 1 if it is already big", and "only try to equalize *p*_{i}'s that are close to each other", etc..., but you get the idea.)