Nhờ mọi người giải hộ bài toán.

[MRAQ2000]

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 ..."

[ThanhLongBin]

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é!