uniolympiads English

IMC 2008, Ημέρα 1, Θέμα 6

For a permutation σ=(i1,i2,…,in)\sigma = (i_1, i_2, \dots, i_n) of (1,2,…,n)(1, 2, \dots, n) define D(σ)=∑k=1n∣ik−k∣D(\sigma) = \sum_{k=1}^{n} |i_k - k|. Let Q(n,d)Q(n, d) be the number of permutations σ\sigma of (1,2,…,n)(1, 2, \dots, n) with d=D(σ)d = D(\sigma). Prove that Q(n,d)Q(n, d) is even for d≥2nd \ge 2n.

Πρωτότυπο από το επίσημο PDFFor a permutation σ = (i 1 , i 2 , ..., i n ) of (1, 2, ..., n) define D(σ) = n P |i k − k|. Let Q(n, d) be k=1 the number of permutations σ of (1, 2, ..., n) with d = D(σ). Prove that Q(n, d) is even for d ≥ 2n.

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

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

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

Επίσημη λύση

Solution. Consider the n×nn\times n determinant

Δ(x)=∣1x…xn−1x1…xn−2⋮⋮⋱⋮xn−1xn−2…1∣\Delta(x) = \begin{vmatrix} 1 & x & \ldots & x^{n-1} \\ x & 1 & \ldots & x^{n-2} \\ \vdots & \vdots & \ddots & \vdots \\ x^{n-1} & x^{n-2} & \ldots & 1 \end{vmatrix}
where the ijij-th entry is x∣i−j∣x^{|i-j|}. From the definition of the determinant we get
Δ(x)=∑(i1,…,in)∈Sn(−1)inv(i1,…,in)xD(i1,…,in)\Delta(x) = \sum_{(i_1,\ldots,i_n)\in S_n} (-1)^{\mathrm{inv}(i_1,\ldots,i_n)} x^{D(i_1,\ldots,i_n)}
where SnS_n is the set of all permutations of (1,2,...,n)(1,2,...,n) and inv(i1,...,in)\mathrm{inv}(i_1,...,i_n) denotes the number of inversions in the sequence (i1,...,in)(i_1,...,i_n). So Q(n,d)Q(n,d) has the same parity as the coefficient of xdx^d in Δ(x)\Delta(x).

It remains to evaluate Δ(x)\Delta(x). In order to eliminate the entries below the diagonal, subtract the (n−1)(n-1)-th row, multiplied by xx, from the nn-th row. Then subtract the (n−2)(n-2)-th row, multiplied by xx, from the (n−1)(n-1)-th and so on. Finally, subtract the first row, multiplied by xx, from the second row.

Δ(x)=∣1x…xn−2xn−1x1…xn−3xn−2⋮⋮⋱⋮⋮xn−2xn−3…1xxn−1xn−2…x1∣=…=∣1x…xn−2xn−101−x2…xn−3−xn−1xn−2−xn⋮⋮⋱⋮⋮00…1−x2x−x300…01−x2∣=(1−x2)n−1.\Delta(x) = \begin{vmatrix} 1 & x & \ldots & x^{n-2} & x^{n-1} \\ x & 1 & \ldots & x^{n-3} & x^{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x^{n-2} & x^{n-3} & \ldots & 1 & x \\ x^{n-1} & x^{n-2} & \ldots & x & 1 \end{vmatrix} = \ldots = \begin{vmatrix} 1 & x & \ldots & x^{n-2} & x^{n-1} \\ 0 & 1-x^2 & \ldots & x^{n-3}-x^{n-1} & x^{n-2}-x^n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 1-x^2 & x-x^3 \\ 0 & 0 & \ldots & 0 & 1-x^2 \end{vmatrix} = (1-x^2)^{n-1}.
For d≥2nd \ge 2n, the coefficient of xdx^d is 00 so Q(n,d)Q(n,d) is even.

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

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

Πώς πήγε;