uniolympiads English

IMC 2016, Ημέρα 2, Θέμα 9

Let kk be a positive integer. For each nonnegative integer nn, let f(n)f(n) be the number of solutions (x1,…,xk)∈Zk(x_1, \dots, x_k) \in \mathbb{Z}^k of the inequality ∣x1∣+⋯+∣xk∣≤n|x_1| + \dots + |x_k| \le n. Prove that for every n≥1n \ge 1, we have f(n−1)f(n+1)≤f(n)2f(n-1)f(n+1) \le f(n)^2.

Πρωτότυπο από το επίσημο PDFLet k be a positive integer. For each nonnegative integer n , let f (n) be the Problem 9. number of solutions (x 1 , . . . , x k ) ∈ Z k of the inequality |x 1 | + ... + |x k | ≤ n . Prove that for every n ≥ 1 , we have f (n − 1)f (n + 1) ≤ f (n) 2 .

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

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

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

Επίσημη λύση

(Proposed by Esteban Arreaga, Renan Finder and José Madrid, IMPA, Rio de Janeiro)

Solution 1. We prove by induction on kk. If k=1k = 1 then we have f(n)=2n+1f(n) = 2n+1 and the statement immediately follows from the AM-GM inequality.

Assume that k≥2k\ge 2 and the statement is true for k−1k-1. Let g(m)g(m) be the number of integer solutions of ∣x1∣+…+∣xk−1∣≤m|x_1| + \ldots + |x_{k-1}| \le m; by the induction hypothesis g(m−1)g(m+1)≤g(m)2g(m-1)g(m+1)\le g(m)^2 holds; this can be transformed to

g(0)g(1)≤g(1)g(2)≤g(2)g(3)≤….\frac{g(0)}{g(1)} \le \frac{g(1)}{g(2)} \le \frac{g(2)}{g(3)} \le \ldots.

For any integer constant cc, the inequality ∣x1∣+…+∣xk−1∣+∣c∣≤n|x_1| + \ldots + |x_{k-1}| + |c| \le n has g(n−∣c∣)g\big(n - |c|\big) integer solutions. Therefore, we have the recurrence relation

f(n)=∑c=−nng(n−∣c∣)=g(n)+2g(n−1)+…+2g(0).f(n) = \sum_{c=-n}^n g\big(n - |c|\big) = g(n) + 2g(n-1) + \ldots + 2g(0).
It follows that
f(n−1)f(n)=g(n−1)+2g(n−2)+…+2g(0)g(n)+2g(n−1)+…+2g(1)+2g(0)≤≤g(n)+g(n−1)+(g(n−1)+…+2g(0)+2⋅0)g(n+1)+g(n)+(g(n)+…+2g(1)+2g(0))=f(n)f(n+1)\begin{aligned} \frac{f(n-1)}{f(n)} &= \frac{g(n-1) + 2g(n-2) + \ldots + 2g(0)}{g(n) + 2g(n-1) + \ldots + 2g(1) + 2g(0)} \le \\ &\le \frac{g(n) + g(n-1) + \big(g(n-1) + \ldots + 2g(0) + 2\cdot 0\big)}{g(n+1) + g(n) + \big(g(n) + \ldots + 2g(1) + 2g(0)\big)} = \frac{f(n)}{f(n+1)} \end{aligned}
as required.

Solution 2. We first compute the generating function for f(n)f(n):

∑n=0∞f(n)qn=∑(x1,x2,…,xk)∈Zk∑c=0∞q∣x1∣+∣x2∣+⋯+∣xk∣+c=(∑x∈Zq∣x∣)k11−q=(1+q)k(1−q)k+1.\sum_{n=0}^\infty f(n)q^n = \sum_{(x_1,x_2,\ldots,x_k)\in\mathbb{Z}^k} \sum_{c=0}^\infty q^{|x_1| + |x_2| + \cdots + |x_k| + c} = \left( \sum_{x\in\mathbb{Z}} q^{|x|} \right)^k \frac{1}{1-q} = \frac{(1+q)^k}{(1-q)^{k+1}}.
For each a=0,1,…a = 0,1,\ldots denote by ga(n)g_a(n) (n=0,1,2,…)(n = 0,1,2,\ldots) the coefficients in the following expansion:
(1+q)a(1−q)k+1=∑n=0∞ga(n)qn.\frac{(1+q)^a}{(1-q)^{k+1}} = \sum_{n=0}^\infty g_a(n)q^n.
So it is clear that ga+1(n)=ga(n)+ga(n−1)g_{a+1}(n) = g_a(n) + g_a(n-1) (n≥1)(n\ge 1), ga(0)=1g_a(0) = 1. Call a sequence of positive numbers g(0)g(0), g(1)g(1), g(2)g(2), …\ldots good if g(n−1)g(n)\frac{g(n-1)}{g(n)} (n=1,2,…)(n = 1,2,\ldots) is an increasing sequence. It is straightforward to check that g0g_0 is good:
g0(n)=(k+nk),g0(n−1)g0(n)=nk+n.g_0(n) = \binom{k+n}{k}, \quad \frac{g_0(n-1)}{g_0(n)} = \frac{n}{k+n}.
If gg is a good sequence then a new sequence g′g' defined by g′(0)=g(0)g'(0) = g(0), g′(n)=g(n)+g(n−1)g'(n) = g(n) + g(n-1) (n≥1)(n\ge 1) is also good:
g′(n−1)g′(n)=g(n−1)+g(n−2)g(n)+g(n−1)=1+g(n−2)g(n−1)1+g(n)g(n−1),\frac{g'(n-1)}{g'(n)} = \frac{g(n-1) + g(n-2)}{g(n) + g(n-1)} = \frac{1 + \frac{g(n-2)}{g(n-1)}}{1 + \frac{g(n)}{g(n-1)}},
where define g(−1)=0g(-1) = 0. Thus we see that each of the sequences g1g_1, g2g_2, …\ldots, gk=fg_k = f are good. So the desired inequality holds.

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

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

Πώς πήγε;