Đến nội dung

Hình ảnh

Chứng minh rằng sau một số lần thực hiện quy tắc thì số 1 xuất hiện ở vị trí đầu tiên

- - - - -

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
hoaian2014

hoaian2014

    Binh nhì

  • Thành viên
  • 12 Bài viết

Các số nguyên dương 1,2,3,...,2019 được sắp xếp trên một hàng theo một thứ tự nào đó. Ta thực hiện quy tắc đổi chỗ các số như sau: nếu số đầu tiên là  k thì ta đổi k số đầu tiên theo thứ tự ngược lại. Chứng minh rằng sau một số hữu hạn lần thực hiện quy tắc trên thì số 1 sẽ xuất hiện ở vị trí đầu tiên.


Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 19-09-2017 - 22:21


#2
dungxibo123

dungxibo123

    Sĩ quan

  • Thành viên
  • 330 Bài viết

giả sử $k$, $1\leq k \leq 2019$ là số lớn nhất xuất hiện ở vị trí đầu tiên trong quá trình đỗi chỗ giả sử số $k$ xuất hiện ở lần $h$.
Khi đó ở lần thực hiện sau lần thứ $h$ thì số $k$ giữ vị trí ban đầu. trong các số còn lại ta gọi $k_{1}$ là số lớn nhất và xuất hiện ở lần $h_{1}$ lập luận như trên...
cứ tiếp tục thì sau hữu hạn bước phải dừng lại.. tức số đầu tiên $= 1$
(Đây là bài toán mình khai thác từ một bài quen thuộc từng gặp không biết có chính xác hay không) 


myfb : www.facebook.com/votiendung.0805
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o0o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SỢ HÃI giúp ta tồn tại

NGHỊ LỰC giúp ta đứng vững

KHÁT VỌNG giúp ta tiến về phía trước

Võ Tiến Dũng  

:like  :like  :like  :like  :like 

 

 


#3
redfox

redfox

    Trung sĩ

  • Thành viên
  • 100 Bài viết

(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





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh