## IPSC 2007

## Solution to Problem P – Paradox With Averages

After we remove a number from a set of numbers, the average of the set
will increase if and only if the removed number was smaller than the
original average.

Mathematically, if S was the sum of the original set, N the count of
its elements, and x the element we removed, we get the inequality:

S/N < (S-x)/(N-1)

Solving for x we get x ≤ S/N, which is exactly what we claimed.

Similarly, the average will increase after adding a new element
if and only if the added element exceeds the original average.

Thus all we need to do is to compute both averages and then count
the numbers that fall between them. This can be done using a linear
search and some simple integer arithmetics.