(cách trên trừu tượng và khó hiểu quá!)
Ta sẽ chứng minh kết quả mạnh hơn: Các số nguyên dương phân biệt $2\leq a_1<...<a_k\leq n$ được sắp xếp trên hàng có $n$ ô và đổi chỗ như trên nếu ô đầu tiên là số, ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó (bài trên coi $1$ là ô trống). Ta quy nạp mạnh theo $n$:
$n=1$: trên hàng là ô trống (đúng)
Giả sử với mọi $m<n$ đúng, xét bảng có $n$ ô như trên:
Nếu $a_k< n$ thì $a_k$ ô đầu tiên có ít nhất một ô trống và cách đổi chỗ như trên chỉ ảnh hưởng đến $a_k$ ô đầu tiên. Vì $a_k$ đúng, ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó nên $n$ đúng
Nếu $a_k=n$, ta coi $n$ là ô trống. Khi đó lập luận tương tự như trên ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó. Nếu ô trống đó không phải là $n$ thì $n$ đúng. Nếu ô trống đó là $n$, cách đổi chỗ sẽ đưa $n$ xuống cuối. Cách đổi chỗ như trên sau đó chỉ ảnh hưởng đến $n-1$ ô đầu tiên và $n-1$ ô đầu tiên có ô trống. Vì $n-1$ đúng, ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó nên $n$ đúng.
(Q.E.D)
Bài viết đã được chỉnh sửa nội dung bởi redfox: 24-09-2017 - 19:36