Xin chào tất cả các thành viên trên diễn đàn, mình là bachhammer. Mình lập topic này để cùng các bạn thảo luận về các bài toán xung quanh các phép toán, thuật toán và các trò chơi, vốn là một trong các dạng toán gần với thực tế, thường xuất hiện trong các đề thi khu vực , quốc gia (VMO), thậm chí là quốc tế (IMO). Các dạng toán này thường là những thuật toán, phép toán biến đổi, hay là những trò chơi mang tính logic cao. Hy vọng rằng với topic này sẽ đáp ứng được nhu cầu trao đổi của những bạn đã biết, sẽ biết và chưa biết. Thường ko có một phương pháp chung nhất định cho dạng này. Vì thế đỏi hỏi sự tư duy năng nỗ của người làm toán để đi đến đích. Xin đưa ra một ví dụ nhỏ thôi:
"Cho 2013 đồ vật được đánh số thứ tự từ 1 đến 2013, và các đồ vật ấy được bố trí thành vòng tròn theo thứ tự 1-2-3-...-2013-1 (tức là một chu trình khép kín), theo chiều quay của kim đồng hồ. Xét phép biến đổi sau: bắt đầu từ một vật nào đó mang số k, ta sẽ hoán đổi với vật mang số k+1 (nếu k = 2013 thì k+1 trùng với 1). Gỉa sử bắt đầu từ đồ vật mang số a, một người ngồi tại vị trí đồ vật mang số b, muốn lấy. Liệu dựa trên phép biển đổi này, người đó có thể lấy được đồ vật mang số a hay ko? Và cần tối thiểu bao nhiu bước để lấy được? (người này cũng hơi rãnh, ko tự lấy món đồ ...)".
Lời giải:
Không mất tính tổng quát ta giả sử a = 1 và b = 1 + k ($0\leq k\leq 2012$, quy ước 1 - 1 = 2013, 2013+1=1). Nếu như k = 0 thì người này ko cần đợi (vì nó nằm ở trước mặt).
Xét k khác 0 thì ta sẽ thấy như sau: Gọi tương ứng vị trí đồ vật thứ k là số k. Sau một lần biến đổi thì vị trí k sẽ có đồ vật mang số k + 1 (được tăng lên 1 đơn vị). Như vậy sau một lần biến đổi, đồ vật số m sẽ nằm ở vị trí m - 1. Như vậy sau một số bước biến đổi nó sẽ đến đúng vị trí mong muốn. Còn chuyện bao nhiu bước thì các bạn có thể tự tính... .
Qua ví dụ trên có thể thấy được cái hay của các bài toán dạng này. Mong được trao đổi cùng các bạn (nhớ ủng hộ nhé...)
Các bạn cũng có thể chia sẻ các bài toán dạng này trên topic này cũng được. Nguyên tắc là đảm bảo đề bài phải ghi số thứ tự (các bài tốt nhất là đừng trùng nhau, dễ nhầm). Và đề bài ko có sự lặp lại... Nhiu đó thôi.
Dĩ nhiên mình có hai bài trước:
Bài 1: Xét một số nguyên dương bất kì n và đặt $a_{1} = n$. Ta xem hai thuật toán sau:
a) $\left\{\begin{matrix} a_{n}=\frac{a_{n-1}+1}{2}(1)\\a_{n}=\frac{a_{n-1}}{2}(2) \end{matrix}\right.$
b) $\left\{\begin{matrix} a_{n}=\frac{a_{n-1}-1}{2}(1)\\a_{n}=\frac{a_{n-1}}{2}(2) \end{matrix}\right.$.
Trong đó (1) xảy ra khi $a_{n-1}$ lẻ, (2) xảy ra khi $a_{n-1}$ chẵn.
Hỏi số nào trong dãy $(a_{n})$ xuất hiện nhiều nhất nếu áp dụng liên tiếp thuật toán (1)? Cũng hỏi tương tự đối với thuật toán hai?
Bài 2: Cho một hình vuông 4 x 4 và 15 miếng ghép hình vuông nhỏ kích thước 1 x 1 có đánh số thứ tự từ 1 đến 15. Gắn các hình vuông theo thứ tự 1, 2, 3, 4, 5,...,15, từ trái qua và từ trên xuống. Xét phép biến đổi đẩy qua, đẩy lại, đẩy lên, đẩy xuống mà ko tháo các miếng hình vuông ra. Hỏi các biển đổi sau có tồn tại hay ko?