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

nghiepdu-socap · 11-01-2012, 05:15 PM

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

shido_soichua · 11-01-2012, 07:21 PM

Trích:

Nguyên văn bởi nghiepdu-socap

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à

nghiepdu-socap · 11-01-2012, 07:58 PM

Trích:

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

**Traum** · 11-01-2012, 07:24 PM

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.

Chém Gió · 16-01-2012, 10:01 PM

Trích:

Nguyên văn bởi 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.

Bất đằng thức cuối mà bạn nhắc đến không phải là Karamata, mà là một sự làm mạnh của bất đẳng thức Chebyshev. Để biết rõ thêm, mời các bạn xem phần cuối về bất đẳng thức Chebyshev trong cuốn "Sáng tạo Bất đẳng thức" của Phạm Kim Hùng.

11-01-2012, 07:24 PM	#4
Traum Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts	VMO P4 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. __________________ Traum is giấc mơ. thay đổi nội dung bởi: Traum, 11-01-2012 lúc 07:33 PM

11-01-2012, 05:15 PM	#1
nghiepdu-socap +Thành Viên+ Tham gia ngày: Apr 2010 Bài gởi: 193 Thanks: 195 Thanked 129 Times in 72 Posts	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