Bài 6. Cho $n, k$ là hai số nguyên, $n \ge k \ge 2$. Bạn tham gia vào một trò chơi với một phù thuỷ ác độc (?!)
Phù thuỷ có $2n$ lá bài, với mỗi $i = 1, 2, \cdots , 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ì game này thành công?
Ta sẽ chứng minh rằng $2\leq k< n$ là điều kiện cần và đủ để ta có thể chiến thắng.
Đầu tiên xét $2\leq k< n$, ta sẽ đặt $2n$ tấm bài vào $2n$ hộp được đánh số từ 1 đến $2n$. Ta sẽ chọn ra $k$ lá bài trong $k$ hộp để xem bài, sau đó phù thuỷ sẽ hoán vị $k$ lá bài đó vào $k$ hộp mà ban đầu đựng chúng.Ta sẽ giả sử không có may mắn trong các lần chọn và ta không thể chọn được 2 lá bài ghi cùng số trước khi có thể đến được bước mà ta có thể chắc chắn chiến thắng. Đầu tiên ta sẽ xem các lá bài ở trong $k$ hộp $1,2,...,k$. Ta sẽ ghi lại $k$ số này trên giấy và phù thuỷ sẽ hoán đổi các lá bài trong $k$ hộp này. Sau đó ta sẽ lật $k$ lá bài trong $k$ hộp $2,3,...,k+1$ và ghi $k$ số này trên giấy. Vì $k-1$ lá bài trong các hộp $2,3,...,k$ đã được ghi trên giấy ở lần đầu nên trong 2 lần ghi số trên giấy thì có ít nhất $k-1$ số được ghi 2 lần.Nếu trong 2 lần chỉ có đúng $k-1$ số được ghi lại 2 lần thì sẽ có duy nhất 1 số được ghi ở lần 1 mà không được ghi ở lần 2, gọi số đó là $x$.Số của lá bài nằm ở hộp 1 sau lần lật bài thứ nhất đã được ghi 1 lần nhưng đến lần thứ 2 thì nó sẽ không được ghi, vì vậy lá bài ở trong hộp 1 hiện tại có số $x$. Nếu trong cả 2 lần lật bài mà cả $k$ số được ghi lại ở cả 2 lần thì ta sẽ gọi số của lá bài trong hộp $k+1$ trong lần lật bài thứ 2 là $y$. Theo giả sử vì ta không có may mắn nên $k-1$ số ghi trong các lá bài trong $k-1$ hộp $2,3,...,k$ trong lần lật bài thứ 2 đều khác $y$. Vì vậy lá bài ở trong hộp 1 hiện tại chứa số $y$. Vì vậy trong cả 2 trường hợp thì ta đều có thể xác định số của lá bài trong hộp 1 sau 2 lần lật bài. Trong lần lật bài thứ $p$ với $p\leq 2n-k+1$, ta sẽ lật bài ở trong các hộp $p,p+1,...,p+k-1$. Sau lần lật thứ 2, ta có thể xác định số quân bài trong hộp 1 và cứ tương tự như thế, sau lần lật bài thứ $p$, ta sẽ xác định được số quân bài trong hộp $p-1$ với $p\leq 2n-k+1$. Vì vây sau lần lật bài thứ $2n-k+1$ thì ta sẽ xác định được $2n-k$ số của các lá bài trong hộp $1,2,...,2n-k$ và vị trí của chúng trong $2n-k$ hộp đó. Có $k<n$ nên $2n-k\geq n+1$. Vì vậy trong $2n-k$ hộp đã biết thì luôn có 2 hộp có lá bài mang cùng số. Ta sẽ chọn lật 2 lá bài đấy và chiến thắng
Với $n=k$, ta sẽ chứng minh được rằng không thể chiến thắng nếu không có may mắn . Ban đầu phù thuỷ sẽ sơn tất cả mặt dưới các lá bài màu trắng và úp chúng xuống. Sau đó phù thuỷ sẽ phù phép sao cho khi ta chọn $n$ lá bài để lật lên thì mặt dưới của $n$ lá bài đó sẽ chuyển thành 1 màu khác với tất cả các màu của $n$ lá bài còn lại. Giả sử người chơi có 1 cách để chắc thắng mà không cần may mắn. Để đẩy người chơi vào cảnh thua cuộc thì ta có thể thêm 1 luật như sau:
Sau khi người chơi chọn n hộp có chứa n lá bài để lật thì phù thuỷ có quyền được hoán đổi các lá bài có cùng màu với nhau vào các hộp của chúng một cách nào đó rồi sau đó màu ở mặt dưới n lá bài được người chơi chọn sẽ đổi màu thành 1 màu mà không trùng với bất cứ lá bài nào không được chọn và sau đó mới được lật lên cho người chơi xem
Việc này không ảnh hưởng đến kế hoạch chiến thắng của người chơi vì ở mỗi lần lật bài, cho dù phù thuỷ có đổi vị trí thế nào thì đó cũng chỉ là 1 trường hợp con của tập các trường hợp mà trò chơi có thể diễn ra trong đầu người chơi. Ta gọi 1 màu trong số các màu trên các quân bài sau lần lật bài thứ $p$ là màu đại diện nếu như sau lần lật bài thứ $p$, $n$ lá bài mà người chơi chọn chuyển thành màu đó. Ta thấy rằng tại mọi thời điểm thì có đúng $n$ lá bài có màu đại diện, $n$ lá bài còn lại mang nhiều nhất $n$ màu khác nhau nên tại mọi thời điểm, $2n$ lá bài được tô bằng nhiều nhất $n+1$ màu. Với mọi số tự nhiên $t$, trước lần lật bài thứ $t$, phù thuỷ có thể hoán vị các quân bài cùng màu để khi người chơi lật $n$ quân bài mà anh ta chọn, $n$ quân bài đó có ghi $n$ số là $1,2,3,...,n$. Vì đầu tiên tất cả các quân bài mang màu trắng nên phù thuỷ có thể hoán đổi vị trí $2n$ quân bài sao cho người chơi không thể chiến thắng. Mệnh đề đúng với $t=1$, giả sử mệnh đề đúng với $t=k$, xét lần lật bài thứ $k+1$. Sau lần lật bài thứ $k$ thì người chơi lật $n$ lá bài mang các số từ 1 dến $n$ nên trước lần lật bài thứ $k+1$, các lá bài mang màu đại diện được có các số từ 1 đến $n$. Vì mỗi số chỉ xuất hiện 2 lần trên đúng 2 lá bài và các lá bài mang màu đại diện chứa các số từ 1 đến $n$ nên không có 2 lá bài nào không mang màu đại diện mà số ghi trên 2 lá bài đó trùng nhau. Ở trong lần lật bài thứ $k+1$, người chơi sẽ chọn 1 số lá bài mang màu đại diện và 1 số lá bài không mang màu đại diện. Giả sử người chơi chọn $i$ lá bài mang màu đại diện và $n-i$ lá bài không mang màu đại diện thì $n-i$ lá bài không mang màu đại diện đó có chứa $n-i$ số khác nhau trên mỗi lá bài trong $n$ số $1,2,...,n$ theo chứng minh trên. Mà $n$ lá bài mang màu đại diện có ghi $n$ số phân biệt $1,2,...,n$ nên có thể hoán đổi vị trí các lá bài đó sao cho với $i$ lá bài mang màu đại diện được chọn thì sẽ có $i$ giá trị khác nhau trong tập $1,2,...,n$ mà mỗi số trong $i$ số đó không được viết lên bất cứ $n-i$ lá bài được chọn không mang màu đại diện. Vì vậy sau khi lật bài, người chơi sẽ thấy các số $1,2,...,n$ được viết trên $n$ lá bài. Vì vậy dù chọn thế nào thì người chơi không thể chọn được 2 lá bài mang cùng số. Vì vậy người chơi không thể chiến thắng.
Vậy điều kiện của $n$ và $k$ là: $n\geq 3$, $2\leq k\leq n-1$
Bài viết đã được chỉnh sửa nội dung bởi JUV: 25-05-2016 - 23:33