For a permutation σ=(i1,i2,…,in) of (1,2,…,n) define D(σ)=∑k=1n∣ik−k∣. Let Q(n,d) be the number of permutations σ of (1,2,…,n) with d=D(σ). Prove that Q(n,d) is even for d≥2n.
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution. Consider the n×n determinant
Δ(x)=1x⋮xn−1x1⋮xn−2……⋱…xn−1xn−2⋮1
where the ij-th entry is x∣i−j∣. From the definition of the determinant we get
where Sn is the set of all permutations of (1,2,...,n) and inv(i1,...,in) denotes the number of inversions in the sequence (i1,...,in). So Q(n,d) has the same parity as the coefficient of xd in Δ(x).
It remains to evaluate Δ(x). In order to eliminate the entries below the diagonal, subtract the (n−1)-th row, multiplied by x, from the n-th row. Then subtract the (n−2)-th row, multiplied by x, from the (n−1)-th and so on. Finally, subtract the first row, multiplied by x, from the second row.
For d≥2n, the coefficient of xd is 0 so Q(n,d) is even.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.