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

[Traum]

Làm giống như bạn Mashimaru ở post phía trên, ta cần phải chứng minh bất đẳng thức:

$\sum\limits_{k=1}^{n}k(a_k+b_k)\le \frac{n(n+1)(8n+1)}{6} $ với $1\le a_1<a_2<\dots<a_n\le 2n $, $1\le b_1<b_2<\dots<b_n\le 2n $ và $a_1,a_2,...,a_n,b_1,...,b_n $ là một hoán vị của $1,2,...,2n $.

Với cách sắp xếp thứ tự trên thì ta có các điều kiện của bất đẳng thức Karamata được thỏa mãn:

$a_n + b_n \le 2n + 2n-1; $
$a_n + b_n + a_{n-1} + b_{n-1}\le 2n + 2n-1 + 2n-2 + 2n-3; $

$\sum\limits_{k=i}^{n}(a_k+b_k)\le \sum\limits_{k=i}^{n}(2k+2k-1) $ với mọi $i = 1,2,...,n $ và với $i = 1 $ thì ta có đẳng thức.

Áp dụng bất đẳng thức Karamata (hoặc có thể chứng minh bằng khai triển tổng Abel (2 dòng)):

$\sum\limits_{k=1}^{n}k(a_k+b_k)\le \sum\limits_{k=1}^nk(4k-1) = \frac{n(n+1)(8n+1)}{6} $. ĐPCM.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[nghiepdu-socap]

Nguyên văn bởi shido_soichua

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à

Ý mình đây là điều kiện để tổng số kẹo đạt max
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[mathstarofvn]

Ý tưởng của mình là đầu tiên cm để nhận số kẹo nhiều nhất thì 2 bạn đứng đầu phải khác giới tính. Sau đó quy nạp nếu xếp các bạn từ 1 đến i mà xen kẽ nam nữ thì xếp bạn i+1 khác giới tính với bạn vị trí thứ i sẽ cho ta số kẹo ko ít hơn số kẹo khi mà i+1 cùng giới tính vs i. Cứ thế thì sẽ suy ra là xen kẽ sẽ đạt max
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[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] 

[let]

Tôi chứng minh qua 3 bước: đầu tiên nếu nam ở cuối, nữ cuối ở vị trí $k <2n-1 $ thì đổi vị trí nữ cuối với nam ở vị trí $2n-1 $, vị trí mới này nhiều kẹo hơn. Sau đó chỉ ra nếu cuối cùng là nam nữ hay nữ nam đều như nhau. Cuối cùng chỉ ra xen kẽ là một trường hợp thoả mãn. Tất cả các trường hợp thoả mãn là vị trí thứ $2k-1 $ và $2k $ là nam nữ hoặc nữ nam với mọi $k $ từ $1 $ đến $n $. Bài này dễ bị nhầm dấu bằng dẫn đến định hướng giải nhầm.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[n.t.tuan]

Thằng này chữ nghĩa sao như các cháu teen thế này? Không gõ tử tế được à?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[let]

Hic, lúc sáng em post bài từ di động, được thế là may lắm rồi!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Traum]

Bài toán luyện tập:

Trên một đường tròn có $2n $ điểm, $n $ điểm xanh và $n $ điểm đỏ. Một điểm là tốt nếu nó là giao của hai dây cung: một cung có hai đầu mút xanh và dây cung còn lại có hai đầu mút đỏ. Hãy tính số lớn nhất và nhỏ nhất các điểm tốt có thể.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[kien10a1]

Em giải theo hướng này, có vẻ đơn giản.
Giả sử n bạn nam theo thứ tự từ trái qua phải là $A_{1},A_2...A_n $ và bên trái $A_i $có $b_i $ bạn nữ,$ b_i $ tự nhiên, có thể là 0, không vượt quá n.
Số kẹo $A_i $ nhận là $b_i(n-b_i) $
Dễ thấy $b_1,b_2,...b_n $ là dãy tăng ( không nhất thiết nghiêm ngặt)
Giữa $A_i,A_{i+1} $ có $ b_{i+1}-b_i $ bạn nữ, mỗi bạn này nhận $i(n-i) $ kẹo( có thể không có bạn nữ nào)
Tổng số kẹo các bạn nữ nhận là:
S= $\sum_{1}^{n}( b_{i+1}-b_i)i(n-i) $
Số lần xuất hiện của $b_i $ trong S là $(i-1)(n-i+1)-i(n-i)=2i-1-n $, do vậy S= $\sum_{1}^{n}b_i(2i-1-n) $
Suy ra tổng số kẹo 2n bạn nhận là T=$\sum_{1}^{n}b_i(2i-1-b_i) $
Ta có $(b_i-i)(b_i-(i-1))\geq0 $ do $b_i $ nguyên, suy ra $i(i-1) \geq b_i(2i-1-b_i) $
Do vậy T không vượt quá $0.1+1.2+...+(n-1)n=\frac{n(n^2-1)}{3} $, có đpcm
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[ThangToan]

Nguyên văn bởi kien10a1

Em giải theo hướng này, có vẻ đơn giản.
Giả sử n bạn nam theo thứ tự từ trái qua phải là $A_{1},A_2...A_n $ và bên trái $A_i $có $b_i $ bạn nữ,$ b_i $ tự nhiên, có thể là 0, không vượt quá n.
Số kẹo $A_i $ nhận là $b_i(n-b_i) $
Dễ thấy $b_1,b_2,...b_n $ là dãy tăng ( không nhất thiết nghiêm ngặt)
Giữa $A_i,A_{i+1} $ có $ b_{i+1}-b_i $ bạn nữ, mỗi bạn này nhận $i(n-i) $ kẹo( có thể không có bạn nữ nào)
Tổng số kẹo các bạn nữ nhận là:
S= $\sum_{1}^{n}( b_{i+1}-b_i)i(n-i) $
Số lần xuất hiện của $b_i $ trong S là $(i-1)(n-i+1)-i(n-i)=2i-1-n $, do vậy S= $\sum_{1}^{n}b_i(2i-1-n) $
Suy ra tổng số kẹo 2n bạn nhận là T=$\sum_{1}^{n}b_i(2i-1-b_i) $
Ta có $(b_i-i)(b_i-(i-1))\geq0 $ do $b_i $ nguyên, suy ra $i(i-1) \geq b_i(2i-1-b_i) $
Do vậy T không vượt quá $0.1+1.2+...+(n-1)n=\frac{n(n^2-1)}{3} $, có đpcm

Ta phải có S= $\sum_{i=1}^{n-1}( b_{i+1}-b_i)i(n-i) $
Ta biến tổng S như sau:
$S = n\sum\limits_{i = 1}^{n - 1} {\left( {\left( {i + 1} \right){b_{i + 1}} - i{b_i}} \right)} - n\sum\limits_{i = 1}^{n - 1} {{b_{i + 1}}} - \sum\limits_{i = 1}^{n - 1} {\left( {{{\left( {i + 1} \right)}^2}{b_{i + 1}} - {i^2}{b_i}} \right)} + \sum\limits_{i = 1}^{n - 1} {\left( {2i + 1} \right){b_{i + 1}}} $
$={n^2}{b_n} - n{b_1} - n\sum\limits_{i = 1}^{n - 1} {{b_{i + 1}}} - {n^2}{b_n} + {b_1} + \sum\limits_{i = 1}^{n - 1} {\left( {2i + 1} \right){b_{i + 1}}} $
$= - n\sum\limits_{i = 1}^n {{b_i}} + \sum\limits_{i = 1}^n {\left( {2i - 1} \right){b_i}} = \sum\limits_{i = 1}^n {{b_i}\left( {2i - 1 - n} \right)} $

Sau khi tính được tổng S như trên thì cách chứng minh tương tự lời giải của em.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[beyondinfinity]

Đại số nhiều hơn tổ hợp?
0 là nữ, 1 là nam.
Gọi $s_i $ là số số 0 ở trước số 1 thứ $i $.
Như vậy ta tính được:
Số kẹo trao cho những số 0 sẽ bằng các bộ 101 mà như thế thì ta sẽ có:
Với số 0 nằm giữa số 1 vị trí $i-1 $ và $i $ sẽ nhận:
$(i-1)(n-i+1) $
Tổng số kẹo này là:
$\sum_{i=1}^{n}{(s_i-s_{i-1})(i-1)(n-i+1)} $
Số kẹo trao cho những số 1 sẽ bằng các bộ 010 mà như thế thì ta sẽ có:
$s_i(n-s_i) $
Tổng số kẹo này là:
$\sum_{i=1}^n s_i(n-s_i) $
Vậy tất cả số kẹo là:
$\sum_{i=1}^{n}{(s_i-s_{i-1})(i-1)(n-i+1)}+\sum_{i=1}^n s_i(n-s_i) $
với $s_0=0 $.
Biến đổi tương đương:
$\sum_{i=1}^n s_i(2i-1-s_i)\leq \sum_{i=1}^n i(i-1)=\frac{n(n-1)(n+1)}{3} $.

Đẳng thức không chỉ xảy ra khi 0 và 1 xen kẽ nhau!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[MathForLife]

Anh P làm tắt kinh khủng ... anh ghi rõ hơn được ko anh?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]