Bài 5
Hai chú sóc, Bushy và Jumpy, đã thu thập được hạt óc chó cho mùa đông. Jumpy đánh số các hạt từ đến và đào cái hố nhỏ xếp thành vòng tròn quanh cây yêu thích của chúng. Sáng hôm sau, Jumpy nhận thấy Bushy đã đặt mỗi hố một hạt, nhưng không để ý đến thứ tự đánh số. Không hài lòng, Jumpy quyết định sắp xếp lại các hạt bằng cách thực hiện một dãy lượt đổi chỗ. Ở lượt thứ , Jumpy đổi chỗ hai hạt kề với hạt số . Chứng minh rằng tồn tại một giá trị sao cho, ở lượt thứ , Jumpy đổi chỗ hai hạt và với .
Bước 1 trên 5: Giả sử không lượt nào từng bao quanh số của chính nó
Phân tích chi tiết
Giả sử phản chứng rằng với mọi , hai hạt được đổi chỗ ở lượt thỏa hoặc , tức là không bao giờ có .