Lời giải bài 8:
a/ Anne có thể gọi tên bài để đạt được mục đích: cô sẽ gọi $13$ lần, mỗi lần sẽ gọi lần lượt tên các lá bài từ Át đến K.Xét 1 lần gọi bất kì, không mất tính tổng quát, giả sử quân bài đầu tiên được di chuyển di chuyển theo chiều kim đồng hồ thì lúc đó quân bài thứ 2 được di chuyển là quân bài nằm cạnh ô trống và khác quân bài thứ nhất. Vì vậy quân bài đó sẽ di chuyển theo chiều kim đồng hồ, tương tự với lá bài thứ 3,4,.... Vì vậy mỗi quân bài được di chuyển sau mỗi lần đọc bài thì sẽ di chuyển theo 1 chiều nhất định. Xét sau lần đọc 1, xét 2 quân bài $a$,$b$ nằm cạnh ô trống. Nếu quân $b$ nằm bên phải, $a$ nằm bên trái ô trống thì nghĩa là trong lần đọc đầu, quân $a$ được di chuyển và quân $b$ không được di chuyển. Tất nhiên là quân $b$ được đọc trước $a$ vài nếu không thì nó sẽ nằm bên phải ô trống. Vì quân $b$ đọc trước $a$ nên trong lần đọc thứ 2 thì nó sẽ di chuyển về phía ô trống. Vì vậy sau mỗi lần đọc, có ít nhất $1$ quân không được di chuyển từ những lần trước được phép di chuyển theo chiều kim đồng hồ. Vì có $13$ lần đọc nên cả $13$ lá bài đều được di chuyển theo chiều kim đồng hồ ít nhất $1$ lần và vì trong mỗi lần, mỗi quân bài chỉ di chuyển tối đa 1 lần nên trong cả $13$ lần, $13$ quân bài di chuyển theo chiều kim đồng hồ nhiều nhất $13$ lần và ít nhất $1$ lần nên sau $13$ lần đọc thì các quân bài sẽ không còn ở vị trí cũ.
b/ Anne không thể đạt được mục đích nếu không có may mắn. Thât vậy nếu Alice sắp xếp bộ bài sao cho quân Át nằm cạnh ô trống, gọi đó là trạng thái 0 và Anne đưa Alice 1 tờ giấy ghi những lá bài mình sẽ gọi theo thứ tự nhất định từ trái sang phải cho đến khi dừng gọi. Alice sẽ ghi lại các quân bài đó trên bảng theo thứ tự ngược lại ( ví dụ như nếu Anne ghi $A,5,Q,K$ thì Alice sẽ ghi $K,Q,5,A$) và thực hiện các bước:
Gọi $n$ là số các lá bài được ghi trên giấy. Anne sẽ nhìn lên bảng và trong bước thứ $i$, xét quân bài thứ $i$ từ trái sang phải. Nếu lúc này quân bài đó nằm cạnh ô trống thì dịch chuyển quân bài đó về ô trống, còn nếu không thì không làm gì cả và chuyển qua bước $i+1$. Gọi trạng thái $i$ là cách sắp xếp bộ bài sau bước thứ $i$ thì cuối cùng sau $n$ bước thì bộ bài sẽ đạt trạng thái $n$. Ta chứng minh rằng nếu bộ bài được sắp xếp thế này và Anne đọc đúng hững quân bài được viết trên giấy theo đúng thứ tự thì cuối cùng, quân Át sẽ nằm cạnh ô trống. Ta sẽ chứng minh rằng sau lần đọc thứ $i$ thì bộ bài của $Anne$ sẽ trở về trạng thái $n-i$. Ta thấy trong lần đọc thứ $i$ thì Anne sẽ đọc quân bài thứ $n-i+1$. Ta thấy mệnh đề hiển nhiên đúng với $i=0$ vì Anne chưa đọc lá bài nào. Giả sử mệnh đề đúng với $i=k$, xét lần đọc thứ $k+1$. Trong lần này Anne sẽ đọc quân bài thứ $n-k$ trên bảng và bộ bài của Alice đang ở trạng thái $k$. Nếu quân bài Anne đang đọc không nằm cạnh ô trống trong trạng thái $n-k$ thì trong trạng thái $n-k-1$ nó cũng vậy, vì vậy nên Alice sẽ không làm gì và bộ bài sẽ trở về trạng thái $n-k-1$. Nếu quân bài đó nằm cạnh ô trống thì trong trạng thái $n-k-1$ nó cũng nằm cạnh ô trống nhưng ngược hướng so với trạng thái $n-k$, lúc đó Alice sẽ dịch chuyển quân bài đó về ô trống và bộ bài trở về trạng thái $n-k-1$. Chứng minh quy nạp hoàn tất. Vì vậy sau $n$ lần đọc thì bộ bài trở về trạng thái 0. Nhưng trong trạng thái này quân Át nằm cạnh ô trống nên Anne không thể đạt được mục đích. Vậy cho dù Anne có đọc thế nào thì cũng có 1 cách sắp xếp bộ bài sao cho cuối cùng quân Át cũng ở cạnh ô trống
Lời giải bài 11:
Với mỗi số $2\leq a\leq 21$ thì ta sẽ gọi $b$ là 1 số đối của $a$ nếu
-)$b<a$
-)Xét hộp $A$ chứa $a$ viên bi và hộp $B$ chứa $b$ viên bi. Sau một số bước chuyển bi giữa 2 hộp này thì hộp $A$ chứa $b$ viên bi và hộp $B$ có $a$ viên bi.
Nếu $a$ là số chẵn thì $a$ có 1 số đối là $\frac{a}{2}$
Nếu $a$ là số lẻ thì ta sẽ xây dừng cặp $(a;b)$ bới $b$ là số đối của $a$ như sau:
$(3;2),(5;4),(7;4),(9;8),(11;4);(13;4);(15;4);(17;16);(19;8);(21;4)$
Ta sẽ chứng minh bài toán tổng quát hơn: Với $(a_{1};a_{2};...;a_{n})$ là 1 hoán vị của $(1;2;...;n)$ với $n\leq 21$ thì ta có thể thực hiện chuyển đổi giữa các hộp sao cho hộp thứ $i$ từ trái sang phải chứa $a_i$ viên bi. Mệnh đề đúng với $n=1,2$, giả sử mệnh đề đúng với $n=k<21$, xét $n=k+1$. Giả sử lúc đầu hộp $x$ chứa $k+1$ viên bi và 1 hộp thứ $y$ với $y\leq 21$ bất kì. Khi đó với $k$ hộp còn lại, theo mệnh đề quy nạp thì ta có thể chuyển bi sao cho với $b$ là số đối của $k+1$ thì hộp $y$ chứa $b$ viên bi. Ta thực hiện chuyển đổi liên tiếp giữa 2 hộp này thì cuối cùng hộp $y$ chứa $k+1$ viên bi, hộp $x$ chứa $b$ viên bi. Cho $y$ chạy từ $1$ đến $k+1$ thì lúc đó ta có thể di chuyển bi sao cho tất cả mọi hộp đều có thể chứa $k+1$ viên bi, hoán vị $k$ hộp còn lại ta sẽ tạo ra được tất cả các hoán vị của $(1;2;...;k+1)$. Vậy mệnh đề đúng với $n=k+1$, vì vậy mệnh đề đúng với $n=21$. Vì $(1;2;...;21)$ là 1 hoán vị của $(1;2;...;21)$ nên ta có thể chuyển bi sao cho các hộp chứa số bi thoả mãn
Bài 12: (USAMO 2016)
Cho $n,k$ là hai số nguyên, $n\geq k\geq 2$. Bạn tham gia vào một trò chơi với một phù thuỷ
Phù thuỷ có $2n$ lá bài, với mỗi $i=1,2,...,n$ thì có đúng hai lá bài cùng được đánh số là $i$. Lúc đầu, phù thuỷ sắp úp tất cả lá bài trên một hàng, thứ tự bất kỳ.
Về phần bạn, bạn sẽ lặp lại các thao tác sau: chỉ vào $k$ lá bài bạn muốn chọn, phù thuỷ sẽ lật ngửa lên hộ bạn. Nếu lật lên, có hai tấm thẻ cùng được đánh 1 số, bạn thắng, game sẽ kết thúc. Nếu ngược lại, phù thuỷ sẽ hoán vị $k$ lá bài đó và lật úp chúng lại. Mỗi lần bạn làm vậy là một bước đi. Và bạn sẽ lặp lại thao tác trên.
Ta gọi game này là thành công nếu tồn tại $m$ nguyên dương nào đó và một chiến thuật nào đó ở tối đa $m$ bước đi, không quan trọng việc phù thuỷ xáo trộn bài của bạn.
Hỏi với $n$ và $k$ nào thì bạn có thể chiến thắng?
Bài viết đã được chỉnh sửa nội dung bởi JUV: 01-06-2016 - 09:00