uniolympiads English

IMC 2012, Ημέρα 1, Θέμα 1

For every positive integer nn, let p(n)p(n) denote the number of ways to express nn as a sum of positive integers. For instance, p(4)=5p(4) = 5 because

4=3+1=2+2=2+1+1=1+1+1+1.4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1.

Also define p(0)=1p(0) = 1.

Prove that p(n)−p(n−1)p(n) - p(n-1) is the number of ways to express nn as a sum of integers each of which is strictly greater than 11.

Πρωτότυπο από το επίσημο PDFFor every positive integer n, let p(n) denote the number of ways to express n as a sum of positive integers. For instance, p(4) = 5 because 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1. Also define p(0) = 1. Prove that p(n) − p(n − 1) is the number of ways to express n as a sum of integers each of which is strictly greater than 1.

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

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

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

Επίσημη λύση

(Proposed by Fedor Duzhin, Nanyang Technological University)

Solution 1. The statement is true for n=1n=1, because p(0)=p(1)=1p(0)=p(1)=1 and the only partition of 1 contains the term 1. In the rest of the solution we assume n≥2n\ge 2.

Let Pn={(a1,…,ak):k∈N, a1≥…≥ak, a1+…+ak=n}\mathcal{P}_n=\{(a_1,\ldots,a_k) : k\in\mathbb{N},\ a_1\ge\ldots\ge a_k,\ a_1+\ldots+a_k=n\} be the set of partitions of nn, and let Qn={(a1,…,ak)∈Pn:ak=1}\mathcal{Q}_n=\{(a_1,\ldots,a_k)\in\mathcal{P}_n : a_k=1\} the set of those partitions of nn that contain the term 1. The set of those partitions of nn that do not contain 1 as a term, is Pn∖Qn\mathcal{P}_n\setminus\mathcal{Q}_n. We have to prove that ∣Pn∖Qn∣=∣Pn∣−∣Pn−1∣|P_n\setminus\mathcal{Q}_n|=|\mathcal{P}_n|-|\mathcal{P}_{n-1}|.

Define the map φ ⁣:Pn−1→Qn\varphi\colon \mathcal{P}_{n-1}\to\mathcal{Q}_n as

φ(a1,…,ak)=(a1,…,ak,1).\varphi(a_1,\ldots,a_k)=(a_1,\ldots,a_k,1).
This is a partition of nn containing 1 as a term (so indeed φ(a1,…,ak)∈Qn\varphi(a_1,\ldots,a_k)\in\mathcal{Q}_n). Moreover, each partition (a1,…,ak,1)∈Qn(a_1,\ldots,a_k,1)\in\mathcal{Q}_n uniquely determines (a1,…,ak)(a_1,\ldots,a_k). Therefore the map φ\varphi is a bijection between the sets Pn−1\mathcal{P}_{n-1} and Qn\mathcal{Q}_n. Then ∣Pn−1∣=∣Qn∣|\mathcal{P}_{n-1}|=|\mathcal{Q}_n|. Since Qn⊂Pn\mathcal{Q}_n\subset\mathcal{P}_n,
∣Pn∖Qn∣=∣Pn∣−∣Qn∣=∣Pn∣−∣Pn−1∣=p(n)−p(n−1).|\mathcal{P}_n\setminus\mathcal{Q}_n|=|\mathcal{P}_n|-|\mathcal{Q}_n|=|\mathcal{P}_n|-|\mathcal{P}_{n-1}|=p(n)-p(n-1).

Solution 2 (outline). Denote by q(n)q(n) the number of partitions of nn not containing 1 as term (q(0)=1q(0)=1 as the only partition of 0 is the empty sum), and define the generating functions

F(x)=∑n=0∞p(n)xnandG(x)=∑n=0∞q(n)xn.F(x)=\sum_{n=0}^{\infty}p(n)x^n \quad\text{and}\quad G(x)=\sum_{n=0}^{\infty}q(n)x^n.
Since q(n)≤p(n)<2nq(n)\le p(n)<2^n, these series converge in some interval, say for ∣x∣<12|x|<\frac12, and the values uniquely determine the coefficients.

According to Euler's argument, we have

F(x)=∑n=0∞p(n)xn=∏k=1∞(1+xk+x2k+…)=∏k=1∞11−xkF(x)=\sum_{n=0}^{\infty}p(n)x^n=\prod_{k=1}^{\infty}(1+x^k+x^{2k}+\ldots)=\prod_{k=1}^{\infty}\frac{1}{1-x^k}
and
G(x)=∑n=0∞q(n)xn=∏k=2∞(1+xk+x2k+…)=∏k=2∞11−xk.G(x)=\sum_{n=0}^{\infty}q(n)x^n=\prod_{k=2}^{\infty}(1+x^k+x^{2k}+\ldots)=\prod_{k=2}^{\infty}\frac{1}{1-x^k}.
Then G(x)=(1−x)F(x)G(x)=(1-x)F(x). Comparing the coefficient of xnx^n in this identity we get q(n)=p(n)−p(n−1)q(n)=p(n)-p(n-1).

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

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

Πώς πήγε;