uniolympiads Ελληνικά

IMC 1999, Day 1, Problem 2

Does there exist a bijective map π ⁣:N→N\pi\colon \mathbb{N} \to \mathbb{N} such that

∑n=1∞π(n)n2<∞?\sum_{n=1}^{\infty} \frac{\pi(n)}{n^2} < \infty?
Original from the official PDF2. Does there exist a bijective map π : N → N such that ∞ X π(n) n=1 n 2 < ∞? (20 points)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution 1. No. For, let π\pi be a permutation of N\mathbf{N} and let N∈NN\in\mathbf{N}. We shall argue that

∑n=N+13Nπ(n)n2>19.\sum_{n=N+1}^{3N}\frac{\pi(n)}{n^2}>\frac19.
In fact, of the 2N2N numbers π(N+1),…,π(3N)\pi(N+1),\dots,\pi(3N) only NN can be ≤N\le N so that at least NN of them are >N>N. Hence
∑n=N+13Nπ(n)n2≥1(3N)2∑n=N+13Nπ(n)>19N2⋅N⋅N=19.\sum_{n=N+1}^{3N}\frac{\pi(n)}{n^2}\ge\frac{1}{(3N)^2}\sum_{n=N+1}^{3N}\pi(n)>\frac{1}{9N^2}\cdot N\cdot N=\frac19.

Solution 2. Let π\pi be a permutation of N\mathbf{N}. For any n∈Nn\in\mathbf{N}, the numbers π(1),…,π(n)\pi(1),\dots,\pi(n) are distinct positive integers, thus π(1)+…+π(n)≥1+…+n=n(n+1)2\pi(1)+\ldots+\pi(n)\ge1+\ldots+n=\frac{n(n+1)}{2}. By this inequality,

∑n=1∞π(n)n2=∑n=1∞(π(1)+…+π(n))(1n2−1(n+1)2)≥≥∑n=1∞n(n+1)2⋅2n+1n2(n+1)2=∑n=1∞2n+12n(n+1)≥∑n=1∞1n+1=∞.\begin{aligned}&\sum_{n=1}^{\infty}\frac{\pi(n)}{n^2}=\sum_{n=1}^{\infty}\bigl(\pi(1)+\ldots+\pi(n)\bigr)\left(\frac{1}{n^2}-\frac{1}{(n+1)^2}\right)\ge\\&\ge\sum_{n=1}^{\infty}\frac{n(n+1)}{2}\cdot\frac{2n+1}{n^2(n+1)^2}=\sum_{n=1}^{\infty}\frac{2n+1}{2n(n+1)}\ge\sum_{n=1}^{\infty}\frac{1}{n+1}=\infty.\end{aligned}

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?