Chủ đề này có 2 trả lời

[Zz Isaac Newton Zz]

Cho $n$ là số nguyên dương, xét tập hợp $S=\left \{ 1,2...,4n^{2} \right \}.$ Phân hoạch tập $S$ thành $2n^{2}$ nhóm $\left \{ a,b \right \}$ sao cho: $\left | a-b \right |\in \left \{ 1,2n \right \}.$ Với mỗi cách phân hoạch trên ta xét tổng các tích $ab.$ Hãy tìm phân hoạch có tổng trên lớn nhất.

[Hr MiSu]

Ta chuyển về mô hình bảng

Cho bảng $2n\times 2n$, viết trong hàng đầu tiên từ trái qua phải theo thứ tự $(1,2,...,2n)$,hàng thứ 2 từ trái qua phải viết $2n+1,...,4n)$

Cứ như trên. Dùng quân đô-min-nô lấp đầy bảng, với mỗi quân đô-min-nô ta tính tích của chúng, cộng các tích lại. Tìm cách xếp sao cho tích nhận được lớn nhất.

Giải: Gọi $a_i,b_i$ là số ghi trên đô-min-nô thứ $i$, ta có: $S=\sum_{i=1}^{2n^2}a_ib_i=\sum_{i=1}^{2n^2}(\frac{a_i^2+b_i^2}{2}-\frac{(a_i-b_i)^2}{2})$, mặt khác: $a_i,b_i$ khác nhau từ tập hợp $S$, $(a_i-b_i)^2\geq 1$ nên $S\leq \frac{1}{2}(\sum_{i=1}^{4n^2}i^2-2n^2)$, dấu bằng xảy ra khi đô-min-nô được đặt ngang hết

Bài viết đã được chỉnh sửa nội dung bởi Hr MiSu: 06-09-2018 - 22:07

[Duy Thai2002]

Cách khác:

Gọi $a_{i},b_{i}$ là hai phần tử của nhóm thứ $i$ ,$1\leq i\leq 2n$

Ta có: $(\left | a_{i}-b_{i} \right |-1)^{2}\geq 0$

$=>a_{i}^{2}-2a_{i}b_{i}+b_{i}^{2}-2\left | a_{i}-b-{i} \right |+1\geq 0$

$=> a_{i}b_{i}\leq \frac{1}{2}(a_{i}^{2}+b_{i}^{2}-2\left | a_{i}-b_{i} \right |+1)\leq \frac{1}{2}(a_{i}^{2}+b_{i}^{2}-2+1)=\frac{1}{2}(a_{i}^{2}+b^{2}_{i}-1)$

$=> \sum_{i=1}^{2n}a_{i}b_{i}\leq \sum_{i=1}^{2n}\frac{1}{2}(a_{i}^{2}+b_{i}^{2}-1)=\frac{1}{2}\sum_{i=1}^{4n^{2}}(x^{2})-n$

ĐTXR $<=>$ phân thành các  tập  $(n,n+1)$