uniolympiads English

IMC 1999, Ημέρα 1, Θέμα 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?
Πρωτότυπο από το επίσημο PDF2. Does there exist a bijective map π : N → N such that ∞ X π(n) n=1 n 2 < ∞? (20 points)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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}

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;