|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
11-01-2012, 11:43 AM | #1 |
Moderator Tham gia ngày: Nov 2009 Bài gởi: 2,849 Thanks: 2,980 Thanked 2,537 Times in 1,008 Posts | [VMO 2012] Bài 4 - Tổ Hợp 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) $. |
The Following 4 Users Say Thank You to n.v.thanh For This Useful Post: |
11-01-2012, 11:52 AM | #2 | |
Maths is my life | Trích:
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 __________________ http://luongvantuy.org/forum.php | |
11-01-2012, 12:01 PM | #3 | |
+Thành Viên+ Tham gia ngày: Dec 2009 Bài gởi: 231 Thanks: 103 Thanked 118 Times in 68 Posts | Trích:
Xét 1 cách xếp mà nam nữ không xen kẽ, gọi i là vị trí nhỏ nhất sao cho từ 1,..,i-1 xếp xen kẽ, học sinh thứ i khác giới với học sinh thứ i-1 và cùng giới với i+1, giả sử có m bạn nữ xếp kề nhau $(m \ge 2) $, phía trước có x nam và y nữ, do xếp xen kẽ nên $y \le x \le y+1 $. Tính được tổng số kẹo. Đổi bạn nam vào vị trí i+1 ta cũng tính được số kẹo. Xét hiệu tổng 2 - tổng 1 thì ta được >=0. __________________ thay đổi nội dung bởi: duynhan, 11-01-2012 lúc 12:05 PM | |
The Following User Says Thank You to duynhan For This Useful Post: | dzitxiem (12-01-2012) |
11-01-2012, 12:13 PM | #4 | |
+Thành Viên+ Tham gia ngày: Sep 2011 Bài gởi: 7 Thanks: 3 Thanked 0 Times in 0 Posts | Trích:
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 thay đổi nội dung bởi: Hoanglong2011, 11-01-2012 lúc 01:38 PM | |
11-01-2012, 01:48 PM | #5 | |
+Thành Viên+ Tham gia ngày: Dec 2009 Bài gởi: 25 Thanks: 10 Thanked 8 Times in 4 Posts | Trích:
_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 | |
11-01-2012, 01:59 PM | #6 | |
+Thành Viên+ Tham gia ngày: Nov 2010 Đến từ: THPT chuyên Vĩnh Phúc Bài gởi: 570 Thanks: 24 Thanked 537 Times in 263 Posts | Trích:
Trước hết ta đánh số $2n $ học sinh có vị trí là $1, 2, ..., n $. 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)} $ $= - \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. thay đổi nội dung bởi: ThangToan, 12-01-2012 lúc 04:47 AM | |
11-01-2012, 02:16 PM | #7 |
+Thành Viên+ Tham gia ngày: Apr 2011 Đến từ: http://m.facebook.com/story.php?story_fbid=488454984546725&id=165605226827592&refid=17&ref=stream Bài gởi: 13 Thanks: 1 Thanked 0 Times in 0 Posts | Bài này mình chỉ làm đc bước tính số kẹo khi xếp xen kẽ còn b2 cm khá vớ vẩn gọi là nêu ra hướng giải là chính, không biết đc mấy điểm |
11-01-2012, 02:46 PM | #8 |
+Thành Viên+ Tham gia ngày: Mar 2008 Bài gởi: 89 Thanks: 19 Thanked 70 Times in 28 Posts | Gọi $a_1, a_2, ..., a_n $ và $b_1, b_2, ..., b_n $ là vị trí của $n $ nam và $n $ nữ trên hàng. Xét nam tại vị trí $a_i $, ta thấy bên trái anh ta có $a_i - 1 $ vị trí, trong đó có $i - 1 $ vị trí là nam, vậy nên bên trái anh ta có $a_i - i $ nữ. Tương tự, bên phải anh ta có $n - (a_i - i) $ nữ. Vậy nam tại $a_i $ được cho $(a_i - i)(n - (a_i - i)) $ kẹo. Tương tự, nữ tại vị trí $b_i $ được cho $(b_i - i)(n - (b_i - i)) $ kẹo. Tính tổng số kẹo được cho, chú ý $\{a_1, a_2, ..., a_n, b_1, b_2, ..., b_n\} = \{1, 2, ..., 2n\} $, ta đưa yêu cầu của bài toán thành việc chứng minh bất đẳng thức $S = \sum_{i = 1}^{n} i (a_i + b_i) \leq \frac{n(n + 1)(8n + 1)}{6} $. Để ý rằng dấu bằng trong bất đẳng thức trên đạt được nếu $a_i = 2i - 1 $ và $b_i = 2i $, với mọi $i = 1, ..., n $ (hoặc ngược lại). Vậy ta sẽ xét cấu hình có $a_i = 2i - 1 $ và $b_i = 2i $, với mọi $i $, cùng với giả sử $a_1 < b_1 $. Từ cấu hình này, để có được một cấu hình bất kỳ với người đứng đầu hàng là nam (tức là $a_1 = 1 $), ta có thể thực hiện liên tiếp các phép đổi vị trí hai người liên tiếp trên hàng. Ta sẽ chứng minh phép đổi này không làm tăng tổng $S $. Thật vậy, có hai khả năng: 1. Nếu ta đổi vị trí 2 nam hoặc 2 nữ liên tiếp thì dễ thấy tổng số kẹo không đổi. 2. Nếu ta đổi chỗ nam ở vị trí $a_i $ với nữ ở vị trí $b_j $ (chú ý rằng muốn làm được như vậy thì ta phải có $|a_i - b_j| $ = 1). Không mất tính tổng quát, giả sử $a_i < b_j $ thì $b_j = a_i + 1 $, sau khi đổi xong, ta được $a_i $ và $b_j + 1 $. Lúc này, tổng S nói chung không đổi, trừ phần $i(a_i + b_i) + j(a_j + a_i + 1) $ trở thành $i (a_i + 1) + j(a_j + a_i) $, do đó tổng GIẢM một lượng bằng $i - j $ (ta quy ước nếu $i < j $ thì tổng sẽ tăng). Tuy nhiên vì $a_i $ ở liền trước $b_j $, nên trước $a_i $ phải có ít nhất $j - 1 $ số, dẫn đến $i \geq j - 1 $, đồng thời $i = j - 1 $ chỉ khi ta có cấu hình $b_k = k $ với mọi $k < j $, đồng thời $i = 1 $, $a_1 = j $ và $b_j = j + 1 $. Điều này không xảy ra vì ta đã giả sử $a_1 < b_1 $. thay đổi nội dung bởi: Mashimaru, 11-01-2012 lúc 03:17 PM |
11-01-2012, 03:09 PM | #9 | |
+Thành Viên+ Tham gia ngày: Sep 2011 Bài gởi: 7 Thanks: 3 Thanked 0 Times in 0 Posts | Trích:
Còn B2 thì sử dụng đơn biến: xét cách xếp 2n HS khác sao cho tồn tại 2 vị trí kề nhau cùng giới (giả sử là nam). Khi đó tồn tại 2 vị trí kề nhau khác cùng là nữ. Thay 2 bạn cùng giới kề nhau bằng 1 bạn cùng giới, thế thì số HS giảm đi 2. Nếu vẫn còn tồn tại 2 vị trí kề nhau như thế thì tiếp tục quy trình trên. Vì số n là hữu hạn suy ra sau 1 số hữu hạn bước, quá trình trên phải dừng, và thu được 1 dãy gồm 2m bạn xếp xen kẽ nhau, với 2m<2n. Rõ ràng số kẹo phát cho 2m bạn nhỏ hơn số kẹo phát cho 2n bạn, suy ra dpcm. thay đổi nội dung bởi: Hoanglong2011, 11-01-2012 lúc 03:17 PM | |
11-01-2012, 03:12 PM | #10 | |
Maths is my life | Trích:
__________________ http://luongvantuy.org/forum.php | |
11-01-2012, 03:56 PM | #11 | |
+Thành Viên+ Tham gia ngày: Mar 2010 Đến từ: 12 Toán - Bến Tre Bài gởi: 221 Thanks: 798 Thanked 128 Times in 64 Posts | Trích:
| |
11-01-2012, 04:37 PM | #12 | |
+Thành Viên+ Tham gia ngày: Nov 2009 Đến từ: A1 LQĐ_ĐN Bài gởi: 60 Thanks: 4 Thanked 19 Times in 13 Posts | Trích:
| |
11-01-2012, 05:00 PM | #13 | |
Maths is my life | Trích:
__________________ http://luongvantuy.org/forum.php | |
11-01-2012, 05:15 PM | #14 |
+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 |
11-01-2012, 07:21 PM | #15 | |
Maths is my life | Trích:
__________________ http://luongvantuy.org/forum.php | |
Bookmarks |
|
|