Maths Olympiad Prep

Library / Balkan Shortlist /10 of 10

Balkan Shortlist, 2012

Algebra Difficulty 8.8 Shortlist Prove it Balkan Mathematical Olympiad

Let NN be a nonnegative integer and let f,g:Z→[0,∞)f, g: \mathbb{Z} \to [0, \infty) be functions such that f(n)=g(n)=0f(n) = g(n) = 0 for all ∣n∣≥N|n| \geq N where Z\mathbb{Z} is the set of all integers. Define h:Z→[0,∞)h: \mathbb{Z} \to [0, \infty) by
h(n)=max⁡{f(k)g(n−k):k∈Z} h(n) = \max \{f(k)g(n-k) : k \in \mathbb{Z}\}
for all n∈Zn \in \mathbb{Z}. Prove that
∑n∈Zh(n)≥(∑n∈Z(f(n))p)1/p(∑n∈Z(g(n))q)1/q \sum_{n \in \mathbb{Z}} h(n) \geq \left( \sum_{n \in \mathbb{Z}} (f(n))^p \right)^{1/p} \left( \sum_{n \in \mathbb{Z}} (g(n))^q \right)^{1/q}
for all positive real numbers pp and qq satisfying 1/p+1/q=11/p + 1/q = 1.

Solutions — 2

Solution 1

Let m0m_0 be an integer at which ff achieves its maximum. Then h(n)≥f(m0)g(n−m0)h(n) \geq f(m_0)g(n - m_0) for all n∈Zn \in \mathbb{Z} and
∑n∈Zh(n)≥f(m0)∑n∈Zg(n−m0)=f(m0)∑n∈Zg(n). \sum_{n \in \mathbb{Z}} h(n) \geq f(m_0) \sum_{n \in \mathbb{Z}} g(n - m_0) = f(m_0) \sum_{n \in \mathbb{Z}} g(n).
Similarly, if n0n_0 is an integer at which gg achieves its maximum, then
∑n∈Zh(n)≥g(n0)∑n∈Zf(n−n0)=g(n0)∑n∈Zf(n). \sum_{n \in \mathbb{Z}} h(n) \geq g(n_0) \sum_{n \in \mathbb{Z}} f(n - n_0) = g(n_0) \sum_{n \in \mathbb{Z}} f(n).
Combining these yields
∑n∈Zh(n)≥(f(m0))1/q(∑n∈Zg(n))1/q(g(n0))1/p(∑n∈Zf(n))1/p. \sum_{n \in \mathbb{Z}} h(n) \geq (f(m_0))^{1/q} \left(\sum_{n \in \mathbb{Z}} g(n)\right)^{1/q} (g(n_0))^{1/p} \left(\sum_{n \in \mathbb{Z}} f(n)\right)^{1/p}.
Since
(f(m0))1/q(∑n∈Zf(n))1/p=((f(m0))p−1∑n∈Zf(n))1/p≥(∑n∈Z(f(n))p)1/p, (f(m_0))^{1/q} \left(\sum_{n \in \mathbb{Z}} f(n)\right)^{1/p} = \left( (f(m_0))^{p-1} \sum_{n \in \mathbb{Z}} f(n) \right)^{1/p} \geq \left( \sum_{n \in \mathbb{Z}} (f(n))^p \right)^{1/p},
and
(g(n0))1/p(∑n∈Zg(n))1/q≥(∑n∈Z(g(n))q)1/q, (g(n_0))^{1/p} \left(\sum_{n \in \mathbb{Z}} g(n)\right)^{1/q} \geq \left( \sum_{n \in \mathbb{Z}} (g(n))^q \right)^{1/q},
the conclusion follows.

Solution 2

We apply H\"older's inequality to obtain
(∑k∈Z(f(k))q(p−1))1/q(∑k∈Z(g(n−k))p(q−1))1/p≥∑k∈Z(f(k))p−1(g(n−k))q−1. \left(\sum_{k \in \mathbb{Z}} (f(k))^{q(p-1)}\right)^{1/q} \left(\sum_{k \in \mathbb{Z}} (g(n-k))^{p(q-1)}\right)^{1/p} \geq \sum_{k \in \mathbb{Z}} (f(k))^{p-1} (g(n-k))^{q-1}.
Hence
h(n)(∑k∈Z(f(k))p)1−1/p(∑k∈Z(g(k))q)1−1/q≥∑k∈Z(f(k))p(g(n−k))q. h(n) \left(\sum_{k \in \mathbb{Z}} (f(k))^p\right)^{1-1/p} \left(\sum_{k \in \mathbb{Z}} (g(k))^q\right)^{1-1/q} \geq \sum_{k \in \mathbb{Z}} (f(k))^p (g(n-k))^q.
Summing over nn gives
(∑n∈Zh(n))(∑k∈Z(f(k))p)1−1/p(∑k∈Z(g(k))q)1−1/q≥(∑k′∈Z(f(k′))p)(∑k′∈Z(g(k′))q). \left(\sum_{n \in \mathbb{Z}} h(n)\right) \left(\sum_{k \in \mathbb{Z}} (f(k))^p\right)^{1-1/p} \left(\sum_{k \in \mathbb{Z}} (g(k))^q\right)^{1-1/q} \geq \left(\sum_{k' \in \mathbb{Z}} (f(k'))^p\right) \left(\sum_{k' \in \mathbb{Z}} (g(k'))^q\right).
The conclusion follows.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.