[Mashimaru]

Gọi $a_1, a_2, ..., a_n $ và $b_1, b_2, ..., b_n $ là vị trí của $n $ nam và $n $ nữ trên hàng. Xét nam tại vị trí $a_i $, ta thấy bên trái anh ta có $a_i - 1 $ vị trí, trong đó có $i - 1 $ vị trí là nam, vậy nên bên trái anh ta có $a_i - i $ nữ. Tương tự, bên phải anh ta có $n - (a_i - i) $ nữ. Vậy nam tại $a_i $ được cho $(a_i - i)(n - (a_i - i)) $ kẹo. Tương tự, nữ tại vị trí $b_i $ được cho $(b_i - i)(n - (b_i - i)) $ kẹo.

Tính tổng số kẹo được cho, chú ý $\{a_1, a_2, ..., a_n, b_1, b_2, ..., b_n\} = \{1, 2, ..., 2n\} $, ta đưa yêu cầu của bài toán thành việc chứng minh bất đẳng thức $S = \sum_{i = 1}^{n} i (a_i + b_i) \leq \frac{n(n + 1)(8n + 1)}{6} $.

Để ý rằng dấu bằng trong bất đẳng thức trên đạt được nếu $a_i = 2i - 1 $ và $b_i = 2i $, với mọi $i = 1, ..., n $ (hoặc ngược lại). Vậy ta sẽ xét cấu hình có $a_i = 2i - 1 $ và $b_i = 2i $, với mọi $i $, cùng với giả sử $a_1 < b_1 $. Từ cấu hình này, để có được một cấu hình bất kỳ với người đứng đầu hàng là nam (tức là $a_1 = 1 $), ta có thể thực hiện liên tiếp các phép đổi vị trí hai người liên tiếp trên hàng. Ta sẽ chứng minh phép đổi này không làm tăng tổng $S $.

Thật vậy, có hai khả năng:
1. Nếu ta đổi vị trí 2 nam hoặc 2 nữ liên tiếp thì dễ thấy tổng số kẹo không đổi.
2. Nếu ta đổi chỗ nam ở vị trí $a_i $ với nữ ở vị trí $b_j $ (chú ý rằng muốn làm được như vậy thì ta phải có $|a_i - b_j| $ = 1). Không mất tính tổng quát, giả sử $a_i < b_j $ thì $b_j = a_i + 1 $, sau khi đổi xong, ta được $a_i $ và $b_j + 1 $. Lúc này, tổng S nói chung không đổi, trừ phần $i(a_i + b_i) + j(a_j + a_i + 1) $ trở thành $i (a_i + 1) + j(a_j + a_i) $, do đó tổng GIẢM một lượng bằng $i - j $ (ta quy ước nếu $i < j $ thì tổng sẽ tăng). Tuy nhiên vì $a_i $ ở liền trước $b_j $, nên trước $a_i $ phải có ít nhất $j - 1 $ số, dẫn đến $i \geq j - 1 $, đồng thời $i = j - 1 $ chỉ khi ta có cấu hình $b_k = k $ với mọi $k < j $, đồng thời $i = 1 $, $a_1 = j $ và $b_j = j + 1 $. Điều này không xảy ra vì ta đã giả sử $a_1 < b_1 $.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]