Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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

    Lính mới

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

Đã gửi 19-09-2017 - 21:45

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ới tính:Nam
  • Đến từ:Chuyên Toán Nguyễn Thượng Hiền
  • Sở thích:...

Đã gửi 19-09-2017 - 22:32

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
  • Giới tính:Nam
  • Đến từ:PTNK - ĐHQG TPHCM
  • Sở thích:wild animal, furry

Đã gửi 24-09-2017 - 19:35

(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