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

[ThangToan]

Nguyên văn bởi n.v.thanh

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

Tôi trình bày lại lời giải bài toán này một cách chi tiết như sau:
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, ..., 2n $. 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)} $
$=\sum\limits_{k = 1}^n {n{i_k}} - n\sum\limits_{k = 1}^n k - \sum\limits_{k = 1}^n {{{\left( {{i_k} - k} \right)}^2}} + n\sum\limits_{k = 1}^{n - 1} {k\left( {{i_{k + 1}} - {i_k}} \right)} - \sum\limits_{k = 1}^{n - 1} {{k^2}\left( {{i_{k + 1}} - {i_k}} \right)} - \sum\limits_{k = 1}^{n - 1} {k\left( {n - k} \right)} $
$=\sum\limits_{k = 1}^n {n{i_k}} - \frac{{{n^2}\left( {n + 1} \right)}}{2} - \sum\limits_{k = 1}^n {{{\left( {{i_k} - k} \right)}^2}} - n\sum\limits_{k = 1}^{n - 1} {{i_{k + 1}}} + n\sum\limits_{k = 1}^{n - 1} {\left( {\left( {k + 1} \right){i_{k + 1}} - k{i_k}} \right)} + \sum\limits_{k = 1}^{n - 1} {\left( {2k + 1} \right){i_{k + 1}}} - \sum\limits_{k = 1}^{n - 1} {\left( {{{\left( {k + 1} \right)}^2}{i_{k + 1}} - {k^2}{i_k}} \right)} - \frac{{n\left( {{n^2} - 1} \right)}}{6} $
$= - \sum\limits_{k = 1}^n {{{\left( {{i_k} - k} \right)}^2}} + \sum\limits_{k = 1}^{n } {\left( {2k - 1} \right){i_{k }}} $
$=\frac{{ - \sum\limits_{k = 1}^n {{{\left( {{i_k} - 2k} \right)}^2}} - \sum\limits_{k = 1}^n {{{\left( {{i_k} - 2k + 1} \right)}^2}} + \sum\limits_{k = 1}^n {{k^2}} + \sum\limits_{k = 1}^n {{{\left( {k - 1} \right)}^2}} }}{2} $
$= - \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.
Dấu bằng chẳng hạn $i_k=2k, k=1, 2, ..., n $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[anhdunghmd]

Không biết đánh Latex khổ thật. Chắc phải học thôi. Bài 4, mọi người Check dùm nhé.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hungmat]

Nguyên văn bởi ThangToan

Tôi trình bày lại lời giải bài toán này một cách chi tiết như sau:
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, ..., 2n $. 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)} $
$=\sum\limits_{k = 1}^n {n{i_k}} - n\sum\limits_{k = 1}^n k - \sum\limits_{k = 1}^n {{{\left( {{i_k} - k} \right)}^2}} + n\sum\limits_{k = 1}^{n - 1} {k\left( {{i_{k + 1}} - {i_k}} \right)} - \sum\limits_{k = 1}^{n - 1} {{k^2}\left( {{i_{k + 1}} - {i_k}} \right)} - \sum\limits_{k = 1}^{n - 1} {k\left( {n - k} \right)} $
$=\sum\limits_{k = 1}^n {n{i_k}} - \frac{{{n^2}\left( {n + 1} \right)}}{2} - \sum\limits_{k = 1}^n {{{\left( {{i_k} - k} \right)}^2}} - n\sum\limits_{k = 1}^{n - 1} {{i_{k + 1}}} + n\sum\limits_{k = 1}^{n - 1} {\left( {\left( {k + 1} \right){i_{k + 1}} - k{i_k}} \right)} + \sum\limits_{k = 1}^{n - 1} {\left( {2k + 1} \right){i_{k + 1}}} - \sum\limits_{k = 1}^{n - 1} {\left( {{{\left( {k + 1} \right)}^2}{i_{k + 1}} - {k^2}{i_k}} \right)} - \frac{{n\left( {{n^2} - 1} \right)}}{6} $
$= - \sum\limits_{k = 1}^n {{{\left( {{i_k} - k} \right)}^2}} + \sum\limits_{k = 1}^{n } {\left( {2k - 1} \right){i_{k }}} $
$=\frac{{ - \sum\limits_{k = 1}^n {{{\left( {{i_k} - 2k} \right)}^2}} - \sum\limits_{k = 1}^n {{{\left( {{i_k} - 2k + 1} \right)}^2}} + \sum\limits_{k = 1}^n {{k^2}} + \sum\limits_{k = 1}^n {{{\left( {k - 1} \right)}^2}} }}{2} $
$= - \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.
Dấu bằng chẳng hạn $i_k=2k, k=1, 2, ..., n $

Cách làm của bạn rất hay tuy nhiên đoạn cuối bị nhầm 1 tý, phải là tổng của ${\left( {{i_k} - 2k} \right)^2} + {\left( {{i_k} - 2k} \right)} $ >=0 với chạy từ 1 đến n, đặt a = ${\left( {{i_k} - 2k} \right)} $ là số nguyên nên phương trình ${\left( {a} \right)^2} + {\left( {a} \right)} $ luôn không âm, dấu = xảy ra khi a = 0 hoặc a = -1
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[ThangToan]

Nguyên văn bởi hungmat

Cách làm của bạn rất hay tuy nhiên đoạn cuối bị nhầm 1 tý, phải là tổng của ${\left( {{i_k} - 2k} \right)^2} + {\left( {{i_k} - 2k} \right)} $ >=0 với chạy từ 1 đến n, đặt a = ${\left( {{i_k} - 2k} \right)} $ là số nguyên nên phương trình ${\left( {a} \right)^2} + {\left( {a} \right)} $ luôn không âm, dấu = xảy ra khi a = 0 hoặc a = -1

Không biến đổi nhầm đâu bạn: chú ý $\[\sum\limits_{k = 1}^n {\left( {2k - 1} \right){i_k}} = \frac{{\sum\limits_{k = 1}^n {\left( {2k{i_k}} \right)} + \sum\limits_{k = 1}^n {\left( {\left( {2k - 2} \right){i_k}} \right)} }}{2}\] $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]