[VMO 2012] Bài 4 - Tổ Hợp
 

Bài 4 (5 điểm) .
Cho số nguyên dương $n $. Có $n $ học sinh nam và $n $ học sinh nữ xếp thành một hàng ngang, theo thứ tự tùy ý. Mỗi học sinh (trong số $2n $ học sinh vừa nêu) được cho một số kẹo bằng đúng số cách chọn ra hai học sinh khác giới với X và đứng ở hai phía của $X $. Chứng minh rằng tổng số kẹo mà tất cả $2n $ học sinh nhận được không vượt quá $\frac{1}{3}n(n^2-1) $.

Có ai làm bài này ko ?
Nếu các học sinh xếp xen kẽ thì số keeoj đúng bằng $\frac{1}{3}n(n^2-1) $
Nếu các học sinh không xếp xen kẽ xét 1 nhóm học sinh nam cạnh cùng với 2 học sinh nữ ở 2 đấu nhóm này.
Gọi k là số nữ ở bên trái nhóm nam
p là số nam ở bên trái bạn nữ đầu tiên bên trái nhóm nam này
p là số nam ở bên trái bạn nữ đầu tiên bên phải nhom nam này.
Khi đó ta đổi chô 2 bạn nam trên với 2 bạn nữ ở cạnh. Gọi $S_m $ là số kẹo sau m lần chuyển đổi. Khi đó ta có:
$S_{m+1}=S_m+2q-2p-4 $ mặt khác $q>p+2 $ do có ít nhất 2 nam ở giữa nên $S_{m+1}>S_m $
Do số kẹo nhận đc có giới hạn nên sau 1 số lần chuyển đổi quá trình trên dừng lại khi đó không còn 2 bạn nam đứng cạnh nhau. Ta có ĐPCM

Với nam nữ xen kẽ ta có số kẹo đúng bằng $\frac13 n(n^2-1) $.
Xét 1 cách xếp mà nam nữ không xen kẽ, gọi i là vị trí nhỏ nhất sao cho từ 1,..,i-1 xếp xen kẽ, học sinh thứ i khác giới với học sinh thứ i-1 và cùng giới với i+1, giả sử có m bạn nữ xếp kề nhau $(m \ge 2) $, phía trước có x nam và y nữ, do xếp xen kẽ nên $y \le x \le y+1 $.
Tính được tổng số kẹo.
Đổi bạn nam vào vị trí i+1 ta cũng tính được số kẹo.
Xét hiệu tổng 2 - tổng 1 thì ta được >=0.

Mình làm tương tự vậy.
Quan trọng là 2 bước:
1. CM cách xếp xen kẽ thì số kẹo đúng bằng $\frac{n(n^2-1)}{3} $
2. CM với số HS là 2n, cách xếp trên có số kẹo lớn nhất. (bằng cách sử dụng đơn biến)

Nhưng mà cái bước 1 CM hơi ẩu T_T (do ko có time).
Hy vọng đc 4 đ bài này X_X

Bạn này có ý tưởng giống mình:
_B1: CM "thuật toán tối ưu" khi nam,nữ xếp xen kẽ nhau.
_B2: CM số kẹo vừa đúng bằng $1/3n(n^2-1) $

Nhưng tiếc là B1 mình làm ẩu hết 2 chỗ, không biết được mấy điểm nữa

Bài này có thể làm như sau:
Trước hết ta đánh số $2n $ học sinh có vị trí là $1, 2, ..., n $. Giả sử học sinh nam ở các vị trí $i_1, i_2, ..., i_n $. Khi đó với học sinh nam ở vị trí thứ $i_k $ thì số kẹo nhận được là: $\[\left( {{i_k} - k} \right)\left( {n + k - {i_k}} \right)\] $. Do đó tổng số kẹo n học sinh nam nhận được là:
$\[\sum\limits_{k = 1}^n {\left( {{i_k} - k} \right)\left( {n + k - {i_k}} \right)} \] $.
Tiếp theo ta tính số kẹo của học sinh nữ.
Số kẹo mà các học sinh nữ ở vị trí $<i_1 $ bằng 0. Số kẹo mà các học sinh nữ ở bị trí $>i_n $ bằng 0.
số kẹo mà các học sinh nữ ở vị trí h sao cho $i_k<h<i_{k+1}; k=1,...,n-1 $ bằng $\[k\left( {n - k} \right)\left( {{i_{k + 1}} - {i_k} - 1} \right)\] $ suy ra tổng số kẹo mà n học sinh nữ nhận được là:
$\[\sum\limits_{k = 1}^{n - 1} {k\left( {n - k} \right)\left( {{i_{k + 1}} - {i_k} - 1} \right)} $
Do đó tổng số kẹo các học sinh nhận được bằng:
$\sum\limits_{k = 1}^n {\left( {{i_k} - k} \right)\left( {n + k - {i_k}} \right)} +\sum\limits_{k = 1}^{n - 1} {k\left( {n - k} \right)\left( {{i_{k + 1}} - {i_k} - 1} \right)} $
Sau đó chứng minh
$\sum\limits_{k = 1}^n {\left( {{i_k} - k} \right)\left( {n + k - {i_k}} \right)} +\sum\limits_{k = 1}^{n - 1} {k\left( {n - k} \right)\left( {{i_{k + 1}} - {i_k} - 1} \right)}\le \frac{1}{3}n(n^2-1) $
Thật vậy, $\sum\limits_{k = 1}^n {\left( {{i_k} - k} \right)\left( {n + k - {i_k}} \right)} +\sum\limits_{k = 1}^{n - 1} {k\left( {n - k} \right)\left( {{i_{k + 1}} - {i_k} - 1} \right)} $
$= - \frac{{\sum\limits_{k = 1}^n {{{\left( {{i_k} - 2k} \right)}^2}} + \sum\limits_{k = 1}^n {{{\left( {{i_k} - 2k + 1} \right)}^2}} + n}}{2} + \frac{{n\left( {{n^2} - 1} \right)}}{3} $ (1)
Với chú ý ${\left( {{i_k} - 2k} \right)^2} + {\left( {{i_k} - 2k + 1} \right)^2} \ge 1, \forall k, 1\le k\le n $ nên từ (1) ta có đpcm.

Bài này mình chỉ làm đc bước tính số kẹo khi xếp xen kẽ còn b2 cm khá vớ vẩn gọi là nêu ra hướng giải là chính, không biết đc mấy điểm

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 $.

Ng­ược lại với mình. B1 làm hơi bị ẩu T_T.

Còn B2 thì sử dụng đơn biến: xét cách xếp 2n HS khác sao cho tồn tại 2 vị trí kề nhau cùng giới (giả sử là nam). Khi đó tồn tại 2 vị trí kề nhau khác cùng là nữ. Thay 2 bạn cùng giới kề nhau bằng 1 bạn cùng giới, thế thì số HS giảm đi 2. Nếu vẫn còn tồn tại 2 vị trí kề nhau như thế thì tiếp tục quy trình trên. Vì số n là hữu hạn suy ra sau 1 số hữu hạn bước, quá trình trên phải dừng, và thu được 1 dãy gồm 2m bạn xếp xen kẽ nhau, với 2m<2n. Rõ ràng số kẹo phát cho 2m bạn nhỏ hơn số kẹo phát cho 2n bạn, suy ra dpcm. =p~

Thay như vậy thì số học sinh chỉ giảm đi 1 thôi chứ bạn ?

Số kẹo phát cho 2m bạn sau hiển nhiên ít hơn số kẹo phát cho 2n bạn đầu tiên, vậy làm thế nào bạn có đpcm?

Theo mình thì nếu xếp xen kẽ số kẹo là nhiều nhất nhưng mà để nhiều nhất phải xếp xen kẽ là sai. thử xét cách xếp là nữ nam nam nữ nữa nam.... phần sau xen kẽ, nó vẫn cho ra giá trị lớn nhất, nên bạn cm là lớn nhất phải xen kẽ chưa đúng lắm và theo cách trên 2 bạn nam có thể cạnh nhau mà vẫn lớn nhất đấy thôi

Uh chỗ này sau cùng tồn tại nhiều nhất 2 nữ cạnh nhau. sau đó từ 1 trong 2 nữa này mình thực hiện đổi chỗ nam nữ theo cặp thì không làm thay đổi tổng số kẹo cuối cùng sẽ ra xen kẽ. Tuy nhiên trong bài đã quên chỗ này huhu. Hi vọng đc 4 điểm bài này

Mình làm dựa vào 3 nhận xét
NX1:số nam, số nữ từ vị trí 1 đến vị trí i bất kì chênh lệch không quá 1
NX2:không có 3 nam, 3 nữ đứng cạnh nhau
NX3:có thể đổi chỗ nam nữ khi thoả mãn 2 điều trên để đưa về xen kẽ
Mình làm hơi dài dòng nên không tiện ghi lại, mọi người thông cảm

Bạn giải thích cho mình cái nhận xét 1 cái. Mình ko hiểu lắm. Nam nữ sắp xếp bất kì mà