Nhờ mọi người giải hộ bài toán. - Trang 38
Close
Login to Your Account
Trang 38 của 38 Đầu tiênĐầu tiên ... 28363738
Kết quả 371 đến 376 của 376
  1. #371
    Ngày tham gia
    Feb 2011
    Bài viết
    65
    Post Thanks / Like

    Mặc định

    Chào các bạn.

    Mình có 1 hướng giải cho trường hợp tổng quát n=2*k.
    Trước hết gọi mc(k) là số chim lớn nhất trên 1 bụi cây, ta dễ chứng minh được mc(k)+2 >= mc(k+1)
    Giờ dùng phép qui nạp
    - Dễ thấy bài toán đúng với k=1 (n=2)
    - Giả sử bài toán đung với k, tức là mc(k) < 2*k => mc(k+1) < 2*(k+1) => bài toán đúng với k+1.
    Vậy bài toán đúng với mọi trường hợp.

  2. Thích trung_cadan, ThanhLongBin đã thích bài viết này
  3. #372
    Ngày tham gia
    Jan 2013
    Bài viết
    82
    Post Thanks / Like

    Mặc định

    Lúc đầu tôi cũng nghĩ có thể dùng quy nạp, nhưng sau thấy ko có cách nào lồng 1 vòng tròn 2*n cây vào trong 1 vòng tròn 2*n+2 cây (vì các cây đòi hỏi phải liên tiếp) nên nghĩ là khó vận dụng. Như bác Thanhlong đã viết, với số cây chẵn lời giải cần phải sử dụng chi tiết "nhảy ngược chiều và nhảy cùng chiều", sau đây là một đề xuất lời giải.
    Đánh số các cây theo chiều kim đồng hồ theo thứ tự 0,1,2,…,n,-n+1,-n+2,…,-2,-1. Trục 0 và n giống như trục 12h-6h trên đồng hồ.
    Giả sử lúc đầu mỗi con chim chỉ có 1 chân. Giả sử nếu nhảy theo chiều kim đồng hồ số chân giảm đi 1, nếu nhảy ngược chiều kim đồng hồ số chân tăng lên 1.
    Mỗi 1 lần nhảy có 1 con chim tăng lên 1 chân, 1 con chim giảm đi 1 chân nên tổng số chân chim không đổi là 2*n.
    Không mất tính tổng quát giả sử sẽ có lúc tất cả các con chim gặp nhau ở cây 0.
    Con chim ở cây i, khi hội tụ ở 0 sẽ có số chân là 1+ i + h*2*n, với h là hệ số có thể âm có thể dương, tùy theo con chim nhảy về 0 rồi lại nhảy thêm vài vòng tròn xuôi ngược.

    Như vậy khi tính tổng số chân chim tại vị trí 0 thì nó sẽ là 2*n + n + x*2*n. Sở dĩ +n đó là vì các cặp (1, -1), (2, -2),… triệt tiêu cho nhau, và con dư một con ở cây n vị trí 6h. Nói tóm lại tổng số chân chim là n + bội số của 2*n. Nhưng số này lại bằng 2*n ko đổi. Điều này ko thể xảy ra vì n không chia hết cho 2*n.

  4. Thích trung_cadan, ThanhLongBin đã thích bài viết này
  5. #373
    Ngày tham gia
    Oct 2013
    Bài viết
    75
    Post Thanks / Like

    Mặc định

    Trích dẫn Gửi bởi MRAQ2000 Xem bài viết
    Chào các bạn.

    Mình có 1 hướng giải cho trường hợp tổng quát n=2*k.
    Trước hết gọi mc(k) là số chim lớn nhất trên 1 bụi cây, ta dễ chứng minh được mc(k)+2 >= mc(k+1)
    Giờ dùng phép qui nạp
    - Dễ thấy bài toán đúng với k=1 (n=2)
    - Giả sử bài toán đung với k, tức là mc(k) < 2*k => mc(k+1) < 2*(k+1) => bài toán đúng với k+1.
    Vậy bài toán đúng với mọi trường hợp.
    Chào bạn MRAQ2000,
    Phương pháp Quy nạp của bạn là một lựa chọn rất tự nhiên. Tuy vậy, khâu quan trọng nhất là phải CMR:
    mc(k+1) < mc(k)+2
    thì bạn lại chỉ suy diễn, coi đó là hiển nhiên!
    Bạn thử chứng minh điều đó một cách chặt chẽ hơn nhé!

  6. Thích trung_cadan đã thích bài viết này
  7. #374
    Ngày tham gia
    Oct 2013
    Bài viết
    75
    Post Thanks / Like

    Mặc định

    Trích dẫn Gửi bởi nghiepdu Xem bài viết
    Lúc đầu tôi cũng nghĩ có thể dùng quy nạp, nhưng sau thấy ko có cách nào lồng 1 vòng tròn 2*n cây vào trong 1 vòng tròn 2*n+2 cây (vì các cây đòi hỏi phải liên tiếp) nên nghĩ là khó vận dụng. Như bác Thanhlong đã viết, với số cây chẵn lời giải cần phải sử dụng chi tiết "nhảy ngược chiều và nhảy cùng chiều", sau đây là một đề xuất lời giải.
    Đánh số các cây theo chiều kim đồng hồ theo thứ tự 0,1,2,…,n,-n+1,-n+2,…,-2,-1. Trục 0 và n giống như trục 12h-6h trên đồng hồ.
    Giả sử lúc đầu mỗi con chim chỉ có 1 chân. Giả sử nếu nhảy theo chiều kim đồng hồ số chân giảm đi 1, nếu nhảy ngược chiều kim đồng hồ số chân tăng lên 1.
    Mỗi 1 lần nhảy có 1 con chim tăng lên 1 chân, 1 con chim giảm đi 1 chân nên tổng số chân chim không đổi là 2*n.
    Không mất tính tổng quát giả sử sẽ có lúc tất cả các con chim gặp nhau ở cây 0.
    Con chim ở cây i, khi hội tụ ở 0 sẽ có số chân là 1+ i + h*2*n, với h là hệ số có thể âm có thể dương, tùy theo con chim nhảy về 0 rồi lại nhảy thêm vài vòng tròn xuôi ngược.

    Như vậy khi tính tổng số chân chim tại vị trí 0 thì nó sẽ là 2*n + n + x*2*n. Sở dĩ +n đó là vì các cặp (1, -1), (2, -2),… triệt tiêu cho nhau, và con dư một con ở cây n vị trí 6h. Nói tóm lại tổng số chân chim là n + bội số của 2*n. Nhưng số này lại bằng 2*n ko đổi. Điều này ko thể xảy ra vì n không chia hết cho 2*n.
    Hoan hô bạn nghiepdu !
    Bạn có rất nhiều sáng kiến kết hợp Toán học với Sinh học! Ở lần trước, bạn có kế hoạch "chuyển đổi giới tính" rất táo bạo cho các chú chim vui tính. Còn lần này, bạn chỉ định "cưa chân, vặt cánh" chúng mà thôi!
    Với phương án mới này, có vẻ như bạn đã rất gần với lời giải rồi đấy!
    Tuy vậy, trong lập luận của bạn còn vài điểm chưa phù hợp với yêu cầu của Bài toán:
    1. Cách đánh số của bạn chưa rõ ràng: " 0,1,2,…,n,-n+1,-n+2,…,-2,-1.". Hình như số các bụi cây sẽ không bằng 2n đâu!!!!
    2. Lập luận về số chân của lũ chim: "tổng số chân chim tại vị trí 0 thì nó sẽ là 2*n + n + x*2*n". Điều này chưa đúng!
    Bạn sắp đến đích rùi, cố lên!!!
    Lần sửa cuối bởi ThanhLongBin, ngày 12-05-2014 lúc 08:53 AM.

  8. Thích trung_cadan đã thích bài viết này
  9. #375
    Ngày tham gia
    Feb 2011
    Bài viết
    65
    Post Thanks / Like

    Mặc định

    Tôi đã chứng minh được mc(k) = 2k-1 với 1 sự thỏa mái hơn nhiều: mối lần (phải có) 2 con chim bay đến 2 bụi cây khác với chiều bay cũng thỏa mái luôn. Như bạn Nghiepdu nói khó dùng phép quy nạp (trong trường hợp bài toán gốc) thì ta sẽ cởi bỏ những ràng buộc đó và được kết quả mạnh hơn nhiều. Bài toán cũng có thể mở rộng với 3, 4 , ... con chim bay với số bụi cây là 3k, 4k, ...
    Bạn Nghiepdu có cách giải với n=46 rất thú vị làm tôi nhớ đến bài toán "Vừa gà vừa chó, bó lại cho tròn ..."
    Lần sửa cuối bởi MRAQ2000, ngày 11-05-2014 lúc 11:55 PM. Lý do: Sửa chính tả

  10. Thích trung_cadan, ThanhLongBin đã thích bài viết này
  11. #376
    Ngày tham gia
    Oct 2013
    Bài viết
    75
    Post Thanks / Like

    Mặc định

    Trích dẫn Gửi bởi MRAQ2000 Xem bài viết
    Tôi đã chứng minh được mc(k) = 2k-1 với 1 sự thỏa mái hơn nhiều: mối lần (phải có) 2 con chim bay đến 2 bụi cây khác với chiều bay cũng thỏa mái luôn. Như bạn Nghiepdu nói khó dùng phép quy nạp (trong trường hợp bài toán gốc) thì ta sẽ cởi bỏ những ràng buộc đó và được kết quả mạnh hơn nhiều. Bài toán cũng có thể mở rộng với 3, 4 , ... con chim bay với số bụi cây là 3k, 4k, ...
    Bạn Nghiepdu có cách giải với n=46 rất thú vị làm tôi nhớ đến bài toán "Vừa gà vừa chó, bó lại cho tròn ..."
    Lập luận của bạn khi quy nạp chưa chắc chắn ở chỗ này đây:
    1. Bạn giả thiết rằng mc(k)=2k-1. Tức là với 2k con chim, không bao giờ có quá 2k-1 con trên cùng 1 bụi cây. Như vậy hoàn toàn có thể xảy ra trường hợp có đúng 2k-2 con trên 1 bụi, 2 con còn lại ở bụi cây khác cạnh đấy!
    2. Với n=2(k+1), lại có thêm 2 con nữa đang ở bụi cây "khác thứ 2". Như vậy, trên 3 bụi cây liền nhau, số chim hoàn toàn có thể là: 2, 2(k-1), 2. Tình huống này không mâu thuẫn với giả thiết mc(k)=2k-1.
    3. Sau 2 nhịp thổi còi tiếp theo, 4 con lẻ kia dễ dàng bay về bụi cây ở giữa, và số chim đậu ở đó là 2(k+1)!!!!


    Đề xuất tổng quát hóa bài toán với 3,4,.. con chim bay đồng thời với 3k,4k,.... bụi cây của bạn e rằng hơi "thoải mái" quá, nhất là khi đó chiều bay cũng "thoải mái" luôn!
    Ví dụ, với 3 con trên 3 bụi cây
    1. Nhịp thứ 1: 1,1,1
    2. Nhịp thứ 2: 0,2,1
    3. Nhịp thứ 3: 3,0,0

    Mời bạn phân tích tiếp nhé!
    Lần sửa cuối bởi ThanhLongBin, ngày 12-05-2014 lúc 07:49 AM.

  12. Thích trung_cadan đã thích bài viết này
Nhờ mọi người giải hộ bài toán.
Trang 38 của 38 Đầu tiênĐầu tiên ... 28363738

Đánh dấu

Đánh dấu

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
.::Thăng Long Kỳ Đạo::.