[tuandaisu]

Sau đây tôi xin trình bày cách giải (theo phương pháp quy nạp), chân thành mong các bạn góp ý nếu có sai sót gì.
Gọi S(n) là số kẹo dùng nhiều nhất cho bài toán có kích thước n.
Thấy n = 2 thì bài toán đúng.
Giả sử bài toán đúng với n. Ta sẽ chứng minh nó đúng với n + 1.
Bước 1: Giả sử có $k \geq 2 $ bạn nam đứng ở ngoài cùng bên phải. Ta tiến hành đổi chỗ bạn nam thứ 2 từ ngoài cùng bên phải với bạn nữ đứng cạnh k bạn nam trên. Sau khi đổi chỗ thì số kẹo của các bạn nam nữ khác k + 1 bạn đang xét không đổi. Số kẹo của k bạn nam này tăng lên là $(k-1)n $, số kẹo bạn nữ đang từ $(n+1-k)k $ thành n.
Vậy số kẹo sau khi chuyển đổi thay đổi: (k-1)n+n-(n+1-k)k=k(k-1)>0.
Như vậy sau khi thực hiện thao tác trên thì ta thu được số kẹo là tốt hơn thực sự.
Xét trường hợp sắp xếp sao cho hai bạn ngoài cùng bên phải khác giới nhau. Giả sử hai bạn đó sắp xếp: X....XNuNam
Bước 2: Loại bỏ hai bạn này đi thì số kẹo sẽ thay đổi như sau:
Bạn Nữ loại sẽ mất n kẹo.
Các bạn nam và bạn nữ còn lại mất số kẹo bằng số các bạn khác giới đứng bên trái mình. Và ta sẽ chứng minh tổng số kẹo này bằng $n^2 $.
Xét các tuyến nối bạn X bất kỳ thuộc hàng với bạn khác giới bên trái của mình. Như vậy tổng số các tuyến là $n^2 $ và ta thấy số tuyến có đầu phải từ X chính bằng số các bạn khác giới với X nằm ở bên trái X. Như vậy số kẹo mất đúng bằng $n^2+n $. 2n bạn còn lại thì sau khi "trả lại kẹo" thì số kẹo không vượt quá $S(n) $
Từ đó số kẹo cho 2n+2 bạn tối ưu là: $S(n+1)=S(n)+n^2+n=\frac {(n+1)[(n+1)^2-1]}{3} $

Qua cách chứng minh này ta có thể khẳng định là dấu bằng xảy ra khi và chỉ khi trong các khối dạng (2k-1;2k) có 1 bạn nam và 1 bạn nữ
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]