For each positive integer n, find the largest real number Cn with the following property. Given any n real-valued functions f1(x),f2(x),…,fn(x) defined on the closed interval 0≤x≤1, one can find numbers x1,x2,…,xn, such that 0≤xi≤1, satisfying ∣f1(x1)+f2(x2)+⋯+fn(xn)−x1x2…xn∣≥Cn.
Solution
First we will prove that Cn≥2nn−1, i.e. that for any n functions f1,f2,…,fn:[0,1]→R, there exist numbers x1,x2,…,xn in [0,1] such that ∣f1(x1)+f2(x2)+⋯+fn(xn)−x1x2…xn∣≥2nn−1. For n=1 this is trivial. For n≥2 suppose, contrariwise, that for all x1,x2,…,xn in [0,1] we have ∣f1(x1)+f2(x2)+⋯+fn(xn)−x1x2…xn∣<2nn−1. Plugging in xi=1 for 1≤i≤n, we get ∣∑i=1nfi(1)−1∣<2nn−1. Plugging in xi=0 for 1≤i≤n, we get ∣∑i=1nfi(0)∣<2nn−1. Plugging in (for every 1≤i≤n) xi=0 and xj=1 for all j=i, we get fi(0)+j=i∑fj(1)<2nn−1. Since (n−1)i=1∑nfi(1)=i=1∑nfi(0)+j=i∑fj(1)−i=1∑nfi(0), by the triangle inequality we have (n−1)i=1∑nfi(1)<(n+1)2nn−1. On the other hand, by again the triangle inequality we have 1≤i=1∑nfi(1)+i=1∑nfi(1)−1<2nn+1+2nn−1=1, which is a contradiction.
To prove that Cn=2nn−1 is the largest constant, it will be sufficient to prove that for the n (equal) functions fi(x)=f(x):=nxn−2n2n−1,1≤i≤n, and any n numbers x1,x2,…,xn in [0,1], we have ∣f(x1)+f(x2)+⋯+f(xn)−x1x2⋯xn∣≤2nn−1, equivalent to −2nn−1≤n1i=1∑nxin−i=1∏nxi−2nn−1≤2nn−1. The LHS inequality follows from the AM-GM inequality.
The RHS inequality is equivalent to F(x)=F(x1,x2,…,xn):=n1i=1∑nxin−i=1∏nxi≤nn−1 at all points x=(x1,x2,…,xn) of the hypercube [0,1]n. Since F is convex in every variable, its maximum is reached at some vertex v of the hypercube (point with xi=0 or xi=1, for all 1≤i≤n). It is easy to see that for all such points we have F(v)≤nn−1, which completes the proof.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement and solution reproduced as published; topic and difficulty added by this site.