Điều chỉnh địa phương - Trường Đông Vinh 2020

2021/03/18 07:56

#tổ hợp #cực trị

Một bài toán liên quan tới đề thi VMO năm 201?.

Bài toán. (Trường Đông Vinh 2020) Cho nn là số nguyên dương. Có nn học sinh nam, nn học sinh nữ xếp thành một hàng ngang. Với mỗi học sinh XX, cô giáo sẽ phát kẹo cho XX bằng với số cặp học sinh khác giới với X và đứng về hai phía của XX. Tìm giá trị lớn nhất của tổng số kẹo mà cô phát.

– Con Heo’s solution –

Lời giải.

Kí hiệu nam là BB, nữ là GGT(δ)T(\delta) là tổng số kẹo cô phát ứng với cách xếp $ \delta $.

Giả sử ta đã có cách xếp các bạn học sinh δ\delta để tổng số kẹo mà cô phát là lớn nhất.

Xét hai bạn học sinh khác giới liền kề nhau là G1G_{1}, B1B_{1}.

Giả sử G1G_{1} ở bên phải B1B_{1}. Gọi gg là số học sinh nam bên trái G1G_{1}, bb là số học sinh nữ bên trái B1B_{1}. Nếu gb>1g-b >1 thì khi đổi chỗ G1G_{1} với B1B_{1} thì g=g1g' = g-1, b=b+1b'=b+1.

T(δ)T(δ)T(\delta')-T( \delta )

=[g(ng)+b(nb)][g(ng)+b(nb)]= [g'(n-g')+b'(n-b')]-[g(n-g)+b(n-b)]

=[(g1)(ng+1)+(b+1)(nb1)][g(ng)+b(nb)]=[(g-1)(n-g+1)+(b+1)(n-b-1)]-[g(n-g)+b(n-b)]

=2g+2b2=2(g+b1)>0=2g+2b-2=2(g+b-1)>0. (trái với cách chọn δ\delta là cách xếp để T(δ)T( \delta) lớn nhất)

Nghĩa là xét hai bạn khác giới ở cạnh nhau bất kì thì số bạn khác giới ở bên trái của bạn ở bên phải phải không lớn hơn số bạn khác giới ở bên trái của bạn ở bên trái quá 11 bạn. (1)(1)

Ta chứng minh ()(*). Đánh số các bạn học sinh từ trái qua phải các số từ 11 tới 2n2n thì cặp học sinh có số thứ tự (2i+1,2i+2),i=0,n1(2i+1,2i+2),i=\overline{0,n-1}(G,B)(G,B) hoặc (B,G)(B,G).

Không mất tính tổng quát, giả sử bạn học sinh số 2n2n là nam.

Gọi mm là số thứ tự của bạn học sinh cuối cùng là nữ.

Gọi bb là số bạn nam bên trái bạn nữ số mm.

Gọi gg là số bạn nữ bên trái bạn nam số m+1m+1.

Khi đó: b=nb=n, g=n(2nm)=mng=n-(2n-m) = m-n.

Theo (1)(1) ta có bg1    2nm1    m2n1b-g \leq 1 \iff 2n -m \leq 1 \iff m \geq 2n-1.

m2nm \neq 2n.

Nên m=2n1m=2n-1.

Suy ra cặp học sinh số thứ tự (2n1,2n)(2n-1,2n)(G,B)(G,B).

Bây giờ ta có thể bỏ qua cặp học sinh này. Bởi vì cặp học sinh trên có đúng 11 nam và 11 nữ và lập luận ở trên chỉ dùng đến số lượng các bạn khác giới ở bên trái của mỗi bạn nên việc bỏ đi cặp học sinh đứng ở ngoài cùng bên phải này không ảnh hưởng gì. Lập luận tương tự thì các cặp (2i+1,2i+2),i=0,n2(2i+1,2i+2),i=\overline{0,n-2} cũng là (G,B)(G,B) hoặc (B,G)(B,G).

Từ hai điều trên ta suy ra được ()(*) cũng đúng với n=kn=k.

Theo nguyên lý quy nạp, ()(*) đúng với mọi nNn \in \mathbb{N}.

Trở lại bài toán. Như vậy, một cách xếp để số kẹo phát ra là lớn nhất phải thoả mãn ()(*).

Xét QQ là tập các cách xếp bạn nam và nữ thoả mãn mệnh đề ()(*). Khi đó maxT(δ)=maxδQT(δ)maxT(\delta)=\underset{\delta \in Q}{max}T(\delta)

GBBGBGGBBGGB|BG|BG|GB|\cdots|BG

Dễ thấy T(δ)T(\delta) luôn không đổi với mọi δQ\delta \in Q

maxT(δ)=0.n+1(n1)+1(n1)+2(n2)+2(n2)+3(n3)+(n1)1+n.0maxT(\delta)=0.n+1(n-1)+1(n-1)+2(n-2)+2(n-2)+3(n-3)+\cdots (n-1)1+n.0

=2[1(n1)+2(n2)+3(n3)+(n1)1]=2[1(n-1)+2(n-2)+3(n-3)+\cdots (n-1)1]

=2[n(1+2+n1)(12+22+(n1)2)]=2[n(1+2+\cdots n-1) - (1^2 +2^2 + \cdots (n-1)^2)]

=2[n2(n1)2n(n1)(2n1)6]=2[\frac{n^2(n-1)}{2} - \frac{n(n-1)(2n-1)}{6}]

=n(n1)(n+1)3=\frac{n(n-1)(n+1)}{3}.

Vậy số kẹo lớn nhất mà cô giáo có thể phát ra là n(n1)(n+1)3\frac{n(n-1)(n+1)}{3} cái kẹo.

Quay trở về Blog