TAOCP 5.4 Exercise 4

We want to maximize the quadratic function \(f(P) = P(T-P)\) for integer \(P\) satisfying \(1 \le P < T\).

taocpmathematicsalgorithmsvolume-3hm-simple

Section 5.4: External Sorting

Exercise 4. [HM15] What value of $P$, for $1 \le P < T$, makes $P(T - P)$ a maximum?

Verified: no
Solve time: 1m02s

Solution

We want to maximize the quadratic function (f(P) = P(T-P)) for integer (P) satisfying (1 \le P < T).
Rewrite (f(P)) by completing the square:

[ f(P) = -P^2 + TP = -\left(P - \frac{T}{2}\right)^2 + \frac{T^2}{4}. ]

This is a downward‑opening parabola whose vertex (maximum over real numbers) is at (P = T/2).
Because the parabola is symmetric and strictly decreasing as we move away from (T/2), the maximum over the integers (1,2,\ldots,T-1) is attained at the integer(s) closest to (T/2).

  • If (T) is even, (T = 2k), the vertex (T/2 = k) is an integer, so the unique maximum is at (P = k = T/2).
  • If (T) is odd, (T = 2k+1), the two integers closest to (T/2) are (k) and (k+1). Both give the same value (f(k) = f(k+1) = k(k+1)).

In either case one of the maximizing values is (\lceil T/2 \rceil) (the other is (\lfloor T/2 \rfloor)).

\boxed{P = \lceil T/2 \rceil}
(Equivalently, (P = \lfloor T/2 \rfloor).)

This completes the proof. ∎