IOAI Training: Learn AI by solving problems

The problem in brief

A class of 30 students took a maths test: the mean score was 75, the median 78 and the standard deviation 5. Two latecomers then sit the test and both score 90. You must give the new class mean (two decimals), then answer a question about a "praise" rule: a student is praised when their score is above the median (still 78) by more than the new standard deviation. Darkhan scored exactly 78 and may retake the test once; what is the smallest integer score that earns him the praise?

The catch is that you never see the 30 individual scores. The whole problem is about what you can still compute from three summary numbers.

How you are scored

The answer is one line with two numbers: the new mean with two decimals, then an integer. It is an exact-answer task.

Our answer, derived below and checked with exact fractions in solution.py:

\boxed{\texttt{75.94 85}}

A word of warning: the answer key published with the statement in the community archive reads 76.00 83. We could not reproduce either number under any reasonable reading (see the last section): $2430/32$ is $75.9375$ , not $76$ , and every convention for the standard deviation gives a threshold above 83.98. We explain our derivation step by step so that you can judge for yourself.

The key idea

Means and variances can be updated without the raw data, because they only depend on two totals, the sum and the sum of squares:

S = \sum_i x_i, \qquad Q = \sum_i x_i^2, \qquad \bar{x} = \frac{S}{n}, \qquad \sigma^2 = \frac{Q}{n} - \bar{x}^2 .

The last identity ("mean of the squares minus square of the mean") follows from expanding $\frac{1}{n}\sum_i (x_i-\bar{x})^2 = \frac{1}{n}\sum_i x_i^2 - 2\bar{x}\cdot\frac{1}{n}\sum_i x_i + \bar{x}^2$ .

So from $(n, \bar{x}, \sigma)$ you recover $(n, S, Q)$ , add the new students to both totals, and convert back. Statisticians call $(n, S, Q)$ sufficient statistics; in machine learning the same trick computes means and variances over a dataset that does not fit in memory, in one streaming pass (this is how batch normalisation keeps its running statistics, and how StandardScaler.partial_fit works).

Question by question

1. The new mean

The 30 original scores sum to $S_{30} = 30 \times 75 = 2250$ . Adding the two 90s gives $S = 2250 + 180 = 2430$ over $N = 32$ students:

\bar{x}_{\text{new}} = \frac{2430}{32} = \frac{1215}{16} = 75.9375 \approx 75.94 .

Sanity check: two scores 15 points above the old mean, diluted among 32 students, should raise the mean by about $2 \times 15/32 \approx 0.94$ . They do.

Answer: 75.94.

2. The new standard deviation

With the population convention (divide by $n$ ), $\sigma^2 = Q/n - \bar{x}^2$ gives the original sum of squares:

Q_{30} = 30\,(5^2 + 75^2) = 30 \times 5650 = 169\,500 .

Add the two newcomers: $Q = 169\,500 + 2 \times 90^2 = 185\,700$ . Then

\sigma^2_{\text{new}} = \frac{185\,700}{32} - \left(\frac{1215}{16}\right)^2 = \frac{9375}{256} \approx 36.621, \qquad \sigma_{\text{new}} \approx 6.0515 .

A more intuitive route to the same number decomposes the squared deviations around the new mean $\mu = 75.9375$ :

\underbrace{30 \times 5^2}_{\text{spread inside the old group}} + \underbrace{30\,(75-\mu)^2}_{\text{old group's centre moved}} + \underbrace{2\,(90-\mu)^2}_{\text{the newcomers}} = 750 + 26.37 + 395.51 = 1171.875 ,

and $1171.875 / 32 = 36.621$ . The decomposition shows why the spread grew so much: the two 90s are far from the centre and their squared distance (about 198 each) dominates.

Note that the median plays no role in these computations: the median cannot be updated from summary numbers, which is exactly why the statement has to tell you that it stayed at 78.

3. Darkhan's minimum retake score

The praise rule asks for a score $x$ with

x - 78 > \sigma_{\text{new}} \approx 6.05 \quad\Longleftrightarrow\quad x > 84.05 .

The smallest integer above $84.05$ is 85. A score of 84 is a gain of only 6 points, short of 6.05.

Does the retake itself change the standard deviation? A careful contestant should worry: if Darkhan's 78 is replaced by $x$ , the class statistics move too. Redo the computation with $S(x) = 2430 - 78 + x$ and $Q(x) = 185\,700 - 78^2 + x^2$ . At $x = 85$ the standard deviation becomes $6.25$ , and the gain $7$ still beats it. At $x = 84$ the gain $6$ loses against both the frozen value (6.05) and the recomputed one (6.18). The answer is the same under both readings, which is reassuring.

$The gain x - 78 crosses both versions of the standard deviation between 84 and 85, so 85 is the smallest integer retake score that earns the praise.$

Answer: 85.

Is the answer robust to the conventions?

The statement does not say whether "standard deviation" divides by $n$ (population) or $n-1$ (sample). We recomputed every combination:

original sd 5 read as	new sd computed as	new sd	threshold $78+\sigma$	answer
population	population	6.0515	84.05	85
population	sample	6.1484	84.15	85
sample	sample	6.0824	84.08	85
sample	population	5.9866	83.99	84
any, retake recomputed	same convention	6.18 to 6.35	84.2 to 84.4	85

Only the inconsistent mix (sample before, population after) gives 84. The published key 76.00 83 corresponds to rounding the mean to 76 and then using the old deviation 5 with "at least" instead of "more than" ( $78 + 5 = 83$ ), which contradicts the statement twice ("new standard deviation", "exceeds"). We therefore keep 75.94 85.

Results

approach	mean	retake	verdict
totals $S$ , $Q$ updated, population sd, frozen threshold	75.94	85	our answer
same, standard deviation recomputed after the retake	75.94	85	same answer, more careful
sample sd ( $n-1$ ) throughout	75.94	85	same
forgets the newcomers in the sd (uses 5)	75.94	84	wrong: the rule says "new" sd
mean of the two group means $(75+90)/2$	82.50		wrong: groups have different sizes
published key	76.00	83	not reproducible from the statement

What to remember

Mean and variance only need $n$ , $\sum x$ and $\sum x^2$ . Recover these totals, update them, convert back: it is the streaming formula behind running statistics in ML.
A few far-away points inflate the standard deviation a lot, because deviations are squared: two scores 14 points from the centre raised it from 5 to 6.05.
The median cannot be updated from summaries, unlike the mean; this is one reason robust statistics are more expensive to maintain.
"Strictly more than" with an integer answer means the next integer after the threshold. Write the inequality before rounding.
When a statement is ambiguous, check whether the ambiguity matters (here: $n$ versus $n-1$ , threshold frozen or not). If all readings agree, you can answer with confidence.

"""FAIO 2024 (Kazakhstan), day 1, problem A "Math Test Results".

30 students: mean 75, median 78, standard deviation 5. Two students with 90
are added. (1) new mean, (2) smallest integer retake score for Darkhan (78)
that exceeds the median 78 by more than the new standard deviation.

We never need the 30 individual scores: the sum and the sum of squares are
enough ("sufficient statistics"). The script checks every reading of the
statement (population or sample standard deviation, threshold frozen or
recomputed after the retake) and draws the figure of the correction.
Run:  python solution.py
"""
from fractions import Fraction as F
from math import sqrt, floor
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

n, mean0, sd0, median = 30, 75, 5, 78
added = [90, 90]
N = n + len(added)

# ------------------------------------------------------------ 1. new mean
S = n * mean0 + sum(added)                    # total of all scores: 2430
mean1 = F(S, N)                               # exact: 1215/16
print("new mean =", mean1, "=", float(mean1), "->", f"{float(mean1):.2f}")

# ------------------------------------------- 2. sum of squares, new variance
# population convention: sd^2 = (1/n) sum x^2 - mean^2  =>  sum x^2 = n (sd^2 + mean^2)
Q = n * (sd0**2 + mean0**2) + sum(a * a for a in added)   # sum of squares: 185700
var1 = F(Q, N) - mean1**2
sd1 = sqrt(var1)
print("new variance =", var1, "=", float(var1), " new sd =", round(sd1, 4))

# same thing with the "decomposition of the sum of squared deviations"
SS = n * sd0**2 + n * (mean0 - mean1)**2 + sum((a - mean1)**2 for a in added)
assert SS / N == var1

def smallest_integer_above(t):
    """smallest integer strictly greater than t"""
    return floor(t) + 1

thr = median + sd1
x_frozen = smallest_integer_above(thr)
print(f"threshold 78 + {sd1:.4f} = {thr:.4f}  ->  minimum retake {x_frozen}")

# ----------------- 3. the retake changes the scores too: recompute sd(x)
def sd_after_retake(x, ddof=0):
    s = S - 78 + x
    q = Q - 78**2 + x**2
    m = F(s, N)
    return sqrt((q - N * m * m) / (N - ddof))

x_dyn = next(x for x in range(79, 101) if x > median + sd_after_retake(x))
print("with the sd recomputed after the retake: minimum", x_dyn,
      f"(sd becomes {sd_after_retake(x_dyn):.4f})")

# ----------------------------- 4. robustness to the sd convention (n vs n-1)
for given in ("population", "sample"):
    k = n if given == "population" else n - 1
    for new in ("population", "sample"):
        ss = k * sd0**2 + n * (mean0 - mean1)**2 + sum((a - mean1)**2 for a in added)
        sd = sqrt(ss / (N if new == "population" else N - 1))
        print(f"  sd 5 read as {given:10s}, new sd as {new:10s}: sd = {sd:.4f}, "
              f"answer {smallest_integer_above(median + sd)}")

print("ANSWER:", f"{float(mean1):.2f} {x_frozen}")      # 75.94 85

# ----------------------------------------------------------------- figure
plt.rcParams.update({"font.size": 13, "axes.spines.top": False, "axes.spines.right": False})
xs = list(range(78, 91))
fig, ax = plt.subplots(figsize=(8.5, 4.6), dpi=150)
ax.plot(xs, [x - median for x in xs], "o-", color="#2e86ab", lw=2.2,
        label="gain over the median: x - 78")
ax.plot(xs, [sd1] * len(xs), "--", color="#d1495b", lw=2.2,
        label=f"new sd, frozen ({sd1:.2f})")
ax.plot(xs, [sd_after_retake(x) for x in xs], ":", color="#8d5a97", lw=2.5,
        label="sd recomputed with the retake")
ax.axvspan(84.5, 90.5, color="#3a7d44", alpha=0.10)
ax.annotate("praise from x = 85", (85, 7), xytext=(86.0, 3.0), fontsize=12,
            arrowprops=dict(arrowstyle="->", color="#3a7d44"), color="#3a7d44")
ax.set_xlabel("Darkhan's retake score x"); ax.set_ylabel("points")
ax.set_title("Praise needs  x - 78 > standard deviation")
ax.set_xticks(xs); ax.legend(frameon=False, fontsize=11, loc="upper left")
fig.tight_layout(); fig.savefig("figures/threshold.png", facecolor="white")
print("figure written")

A. Math Test Results