Unofficial archive — problems, solutions & results © IMC, reproduced with permission.

IMC / 1999 / Problems / Day 1, P2

IMC 1999 · Day 1 · P2

medium

Does there exist a bijective map π:NN\pi : \mathbb{N} \to \mathbb{N} such that n=1π(n)n2<?\sum_{n=1}^{\infty} \frac{\pi(n)}{n^2} < \infty?

Solution 1 of 2 (official)

No. For, let π\pi be a permutation of N\mathbb{N} and let NNN \in \mathbb{N}. We shall argue that n=N+13Nπ(n)n2>19.\sum_{n=N+1}^{3N} \frac{\pi(n)}{n^2} > \frac{1}{9}. 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)n21(3N)2n=N+13Nπ(n)>19N2NN=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 = \frac{1}{9}.

Solution 2 of 2 (official)

Let π\pi be a permutation of N\mathbb{N}. For any nNn \in \mathbb{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) + \dots + \pi(n) \ge 1 + \dots + n = \frac{n(n+1)}{2}. By this inequality, n=1π(n)n2=n=1(π(1)++π(n))(1n21(n+1)2)n=1n(n+1)22n+1n2(n+1)2=n=12n+12n(n+1)n=11n+1=.\begin{align*} \sum_{n=1}^{\infty} \frac{\pi(n)}{n^2} &= \sum_{n=1}^{\infty} \bigl( \pi(1) + \dots + \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{align*}

How the field did

contestants scored
87
average (of 20)
10.74
solved (≥ 80%)
47.1%
near-0 (≤ 10%)
39.1%
discrimination
0.64

Score distribution (field cohort)

Computed on contestants with a meaningful total (field cohort); discrimination is the corrected item–total correlation.

Similar problems

IMC 2002 · Day 1 · P3mediumavg 4.4/10 · solved 41% · near-0 49% · disc 0.41
IMC 2010 · Day 2 · P6mediumavg 7.4/10 · solved 47% · near-0 3% · disc 0.49
IMC 2000 · Day 2 · P7mediumavg 6.8/10 · solved 47% · near-0 11% · disc 0.61
IMC 1999 · Day 1 · P5mediumavg 5.5/10 · solved 48% · near-0 33% · disc 0.58