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

[Hoanglong2011]

Nguyên văn bởi shido_soichua

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

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 (do ko có time).
Hy vọng đc 4 đ bài này
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Brandnewworld]

Nguyên văn bởi Hoanglong2011

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 (do ko có time).
Hy vọng đc 4 đ bài này

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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]