Diễn Đàn MathScope - Xem bài viết đơn - Tìm và trình bày một lời giải như thế nào?

truongln88 · 14-05-2010, 04:17 AM

Tiếp tục với bài 2 USAMO.
Đầu tiên là sửa đề toán lại là xét trên đường tròn. Bây giờ ta phải đếm số lần đổi chỗ lớn nhất. Ta thấy hành động đổi chỗ là liên quan đến hai người đứng kề nhau, như vậy để đếm số lần đổi chỗ ta có thể đếm theo hai cách:
+ Cách 1: đếm số lần đổi của từng người, cộng tất cả lại, sau đó chia đôi.
+ Cách 2: xem mỗi lần đổi chỗ chỉ là hành động của một trong hai người, như thế ta phải đếm mỗi người có bao nhiêu hành động rồi cộng lại.
Hai cách trên chỉ là cảm tính khi đọc đề, làm thử thì hiển nhiên thấy cách đếm thứ hai là đơn giản và hiệu quả hơn. Dựa vào đó ta có thể xem mỗi lần đổi chỗ chỉ là hành động của người đứng trước hoặc người đứng sau, hoặc là người đứng trước nhảy ra sau lưng người đứng sau hoặc là người đứng sau nhảy ra trước mặt người đứng trước. Nói chung thì chúng ta ai cũng muốn tiến lên, vậy mình chọn cách là: "xem như mỗi lần đổi chỗ là người đứng sau nhảy lên trước mặt người đứng trước, còn người đứng trước không thực hiện hành động gì!".
Ý tưởng đầu tiên mình nghĩ đến là quy nạp. Bây giờ phải nghĩ xem là quy nạp như thế nào. Mất khoảng 30 phút suy nghĩ quy nạp theo $n $. Cuối cùng vẫn mù tịt, không rút ra được kết quả gì. Cái khó là đứng trên vòng tròn, nên rất khó để tìm được một đánh giá giữa cái khác của $n+1 $ người và $n $ người. Sau đây mình định thử xem có cố định được hai đỉnh kề nhau nào đó, hoặc là bằng cách nào đó đưa về đường thẳng không, cũng vô phương. Tóm lại là sao gần 1 tiếng vẫn vô phương (ở trong phòng thi chắc cũng hoảng rồi^^).
Từ bỏ quy nạp theo $n $. Bây giờ mình thấy là người $k $ chỉ có thể nhảy qua những người $k-2,k-3,k-4,... $, như vậy $k $ càng lớn thì khả năng số lần nhảy của người này cũng càng lớn. Vậy thử quy nạp theo $k $ (người thứ $k $).
Bây giờ, gọi số lần nhảy của người $k $ là $n_k $. Theo ý tưởng quy nạp thì ta sẽ đánh giá $n_k $ theo $n_{k-1},n_{k-2},... $. Trong những người này, chỉ có người $k-1 $ là người $k $ không thể nhảy qua. Như vậy người $k $ chỉ có thể nhảy qua những người đứng trước người $k $ và đứng sau người $k-1 $, hoặc là nhảy qua tiếp những người mà người $k-1 $ nhảy qua để lại ở phía sau. Ban đầu ở giữa người $k $ và người $k-1 $ chỉ có thể có $k-2 $ người là người $k $ có khả năng nhảy qua là $1,2,...,k-2 $, còn số người người $k-1 $ nhảy qua để lại phía sau để người $k $ có thể nhảy qua tiếp là $s_{k-1} $ (theo định nghĩa). Như vậy, người $k $ có thể nhảy nhiều nhất là $s_{k-1}+k-2 $ lần (phù, cuối cùng cũng tìm được một công thức truy hồi).
Rõ ràng người $1,2 $ không nhảy qua được ai cả. Suy ra $s_1=s_2=0 $. Từ đó suy ra $s_k\leq \frac{(k-2)(k-1)}{2} $ với mọi $k\geq 3 $. Từ đó suy ra:
$\sum\limits_{k=1}^{n}{s_k}\leq \sum\limits_{k=3}^{n}{\frac{(k-2)(k-1)}{2}}=\frac{1}{2}\sum\limits_{k=3}^{n}{(k^2-3k+2)}=\frac{1}{2}\left ( \sum\limits_{k=3}^{n}{k^2}-3\sum\limits_{k=3}^{n}{k}+\sum\limits_{k=3}^{n}{2} \right ) $
$=\frac{1}{2}\left ( \frac{n(n+1)(2n+1)}{6} - 1^2 - 2^2 - 3\left (\frac{n(n+1)}{2} - 1 - 2\right ) + 2(n-2)\right ) $
$=\frac{n(n-1)(n-2)}{6}=C_{n}^{3} $
(đpcm)

14-05-2010, 04:17 AM	#26
truongln88 +Thành Viên+ Tham gia ngày: Mar 2010 Bài gởi: 19 Thanks: 0 Thanked 54 Times in 13 Posts	Tiếp tục với bài 2 USAMO. Đầu tiên là sửa đề toán lại là xét trên đường tròn. Bây giờ ta phải đếm số lần đổi chỗ lớn nhất. Ta thấy hành động đổi chỗ là liên quan đến hai người đứng kề nhau, như vậy để đếm số lần đổi chỗ ta có thể đếm theo hai cách: + Cách 1: đếm số lần đổi của từng người, cộng tất cả lại, sau đó chia đôi. + Cách 2: xem mỗi lần đổi chỗ chỉ là hành động của một trong hai người, như thế ta phải đếm mỗi người có bao nhiêu hành động rồi cộng lại. Hai cách trên chỉ là cảm tính khi đọc đề, làm thử thì hiển nhiên thấy cách đếm thứ hai là đơn giản và hiệu quả hơn. Dựa vào đó ta có thể xem mỗi lần đổi chỗ chỉ là hành động của người đứng trước hoặc người đứng sau, hoặc là người đứng trước nhảy ra sau lưng người đứng sau hoặc là người đứng sau nhảy ra trước mặt người đứng trước. Nói chung thì chúng ta ai cũng muốn tiến lên, vậy mình chọn cách là: "xem như mỗi lần đổi chỗ là người đứng sau nhảy lên trước mặt người đứng trước, còn người đứng trước không thực hiện hành động gì!". Ý tưởng đầu tiên mình nghĩ đến là quy nạp. Bây giờ phải nghĩ xem là quy nạp như thế nào. Mất khoảng 30 phút suy nghĩ quy nạp theo $n $. Cuối cùng vẫn mù tịt, không rút ra được kết quả gì. Cái khó là đứng trên vòng tròn, nên rất khó để tìm được một đánh giá giữa cái khác của $n+1 $ người và $n $ người. Sau đây mình định thử xem có cố định được hai đỉnh kề nhau nào đó, hoặc là bằng cách nào đó đưa về đường thẳng không, cũng vô phương. Tóm lại là sao gần 1 tiếng vẫn vô phương (ở trong phòng thi chắc cũng hoảng rồi^^). Từ bỏ quy nạp theo $n $. Bây giờ mình thấy là người $k $ chỉ có thể nhảy qua những người $k-2,k-3,k-4,... $, như vậy $k $ càng lớn thì khả năng số lần nhảy của người này cũng càng lớn. Vậy thử quy nạp theo $k $ (người thứ $k $). Bây giờ, gọi số lần nhảy của người $k $ là $n_k $. Theo ý tưởng quy nạp thì ta sẽ đánh giá $n_k $ theo $n_{k-1},n_{k-2},... $. Trong những người này, chỉ có người $k-1 $ là người $k $ không thể nhảy qua. Như vậy người $k $ chỉ có thể nhảy qua những người đứng trước người $k $ và đứng sau người $k-1 $, hoặc là nhảy qua tiếp những người mà người $k-1 $ nhảy qua để lại ở phía sau. Ban đầu ở giữa người $k $ và người $k-1 $ chỉ có thể có $k-2 $ người là người $k $ có khả năng nhảy qua là $1,2,...,k-2 $, còn số người người $k-1 $ nhảy qua để lại phía sau để người $k $ có thể nhảy qua tiếp là $s_{k-1} $ (theo định nghĩa). Như vậy, người $k $ có thể nhảy nhiều nhất là $s_{k-1}+k-2 $ lần (phù, cuối cùng cũng tìm được một công thức truy hồi). Rõ ràng người $1,2 $ không nhảy qua được ai cả. Suy ra $s_1=s_2=0 $. Từ đó suy ra $s_k\leq \frac{(k-2)(k-1)}{2} $ với mọi $k\geq 3 $. Từ đó suy ra: $\sum\limits_{k=1}^{n}{s_k}\leq \sum\limits_{k=3}^{n}{\frac{(k-2)(k-1)}{2}}=\frac{1}{2}\sum\limits_{k=3}^{n}{(k^2-3k+2)}=\frac{1}{2}\left ( \sum\limits_{k=3}^{n}{k^2}-3\sum\limits_{k=3}^{n}{k}+\sum\limits_{k=3}^{n}{2} \right ) $ $=\frac{1}{2}\left ( \frac{n(n+1)(2n+1)}{6} - 1^2 - 2^2 - 3\left (\frac{n(n+1)}{2} - 1 - 2\right ) + 2(n-2)\right ) $ $=\frac{n(n-1)(n-2)}{6}=C_{n}^{3} $ (đpcm)