Hoán vị của 2n số nguyên dương đầu tiên

[psquang_pbc]

Cho số nguyên n\ge 1. Xét hoán vị (a_1,a_2,...,a_{2n}) của 2n số nguyên dương đầu tiên sao cho các số |a_{i+1}-a_i|,i=1,2,...,2n-1 đôi một khác nhau. Chứng minh rằng: a_1-a_{2n}=n khi và chỉ khi 1\le a_{2k}\le n,k=1,2,..,n

[Traum]

We have
\sum\limit_{i = 1}^{2n}|a_{i + 1} - a_{i}| + \sum\limit_{i = 1}^{2n}|a_{i + 1} + a_i| = 2\sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\}
Thus, \sum\limit_{i = 1}^{2n}|a_{i + 1} - a_i| = 2\sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\} - 2\sum\limit_{i = 1}^{2n}a_i. Hence, (\sum\limit_{i = 1}^{2n - 1}|a_{i + 1} - a_i|) + |a_1 - a_{2n}| = 2\sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\} - 2n(2n + 1). (*)

Because 2n - 1 numbers |a_{i + 1} - a_i| are distinct and |a_{i + 1} - a_i|\le 2n - 1. Then,
\sum\limit_{i = 1}^{2n - 1}|a_{i + 1} - a_i| = 1 + 2 + ... + 2n - 1 = n(2n - 1). (**)
From (*) and (**) we have |a_1 - a_{2n}| = 2\sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\} - 2n(2n + 1) - n(2n - 1).
= 2\sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\} - 4n^2 - n.

If, a_1 - a_{2n} = n we have \sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\} = 3n^2 + n. (1)

But, \sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\}\le 2(2n + 2n - 1 + ... + n + 1) = 2n(2n + 1) - n(n + 1) = 3n^2 + n (2)

From (1); (2) we have either \{a_1;a_3;...;a_{2n - 1}\} = \{1;2;..;n\} or \{a_2;...;a_{2n}\} = \{1;2;...;n\}.

But a_1 - a_{2n} = n hence, \{a_2;...;a_{2n}\} = \{1;2;...;n\}

If \{a_2;..;a_{2n}\} = \{1;2;...;n\} so, \sum\limit_{i = 1}^{2n}max\{a_{i + 1};a_i\} = 3n^2 + n.
Hence, |a_1 - a_{n}| = 2(3n^2 + n) - 4n^2 - n = n therefore, a_1 - a_{2n} = n

It looks easy

[psquang_pbc]

Dạ không khó tí nào cả, nó là 1 bài của zaizai post bên VMF, em lôi sang thôi :D.

Bác Quý xài tiếng Anh ghê quá:D

[Traum]

:)) cái này là bài post hồi cấp 3 trên ML ấy mà, giờ thì gà English lắm. Spam