Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:
Trong ô cờ thứ nhất đặt 1 hạt ngô
Trong ô cờ thứ hai đặt 2 hạt ngô
Trong ô cờ thứ ba đặt 4 hạt ngô
...
Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.
Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.
Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.
Bài dự thi trận $5$ của $\textrm{MSS}27$:
Chứng minh bổ đề phụ: Với $n\in \mathbb{N}$
$\triangleright $: $2^{n}\equiv 1(\bmod3)\Leftrightarrow 2\mid n$
Thật vậy, với $2\mid n$:
$\Rightarrow n=2k(k\in \mathbb{N})\Rightarrow 2^{n}=2^{2k}=4^{k}\equiv 1^{k}=1(\bmod 3)$
$\blacksquare$
$\triangleright$: $2^{n}\equiv -1(\bmod3)\Leftrightarrow 2\not{\mid}n$
Thật vậy, với $2\not{\mid} n$:
$n=2q+1\Rightarrow 2^{n}=2^{2q+1}=4^{q}.2\equiv 1^{q}.(-1)=-1(\bmod3)$
$\blacksquare$
Quay lại bài toán:
Vì bàn cờ vua $8 \times 8$ nên sẽ có $32$ ô đen và $32$ ô trắng xen kẻ nhau. Không mất tính tổng quát, giả sử quân mã bắt đầu ở ô trắng là $A8$. Theo giả thiết nên số hạt ngô sẽ được sắp xếp:
6.jpg 20.74K
0 Số lần tải
$A8=2^{0}$
$B8=2^{1}$
$C8=2^{2}$
...
$A7=2^{8}$
...
$H1=2^{64}$
Ta thấy ở những cột có số thứ tự chẵn ( tức $8,6,4,2$) ô trắng luôn là lũy thừa bậc chẵn của $2$
Và ở những cột có số thứ tự lẻ ( tức $7,5,3,1$) ô đen luôn là lũy thừa bậc chẵn của $2$.
Lại thấy nếu quân mã xuất phát từ ô trắng $A1$ thì phải sau một số nước chẵn mới có thể trở về ô trắng lúc đầu ( thỏa đề)
Vậy nếu quân mã nhảy từ cột này sang cột khác, hàng nhích $\frac{+}{ }1$, ví dụ từ $M_{A8}\rightarrow M_{B6}\rightarrow M_{C4}...$ và luôn theo quy luật như vậy thì ta có đpcm.
Thật vậy, khi quân mã di chuyển thì màu của ô nó đứng lúc đầu sẽ thay đổi ( từ trắng sang đen và ngược lại). Tức $n$ trong bổ đề sẽ thay đổi theo ( từ chẵn sang lẻ và ngược lại). Sau một số nước đi chẵn, tổng số hạt ngô mà quân mã thu được sẽ $\equiv 1-1+1-1+1-1...+1-1=0(\bmod3)$ ( áp dụng bổ đề trên). Đây là điều phải chứng minh$\blacksquare$
-----------------------------------
$\bigstar$ Nếu mỗi ô chỉ được đi một lần thì bài toán sẽ được chứng minh đơn giản hơn. Nhưng đề ở đây chưa thật rõ ràng. Vì ( theo em) nếu mỗi ô chỉ được đi một lần thì tại sao "sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó". ?
Bài toán sẽ sai trong ví dụ sau. Các nước đi của quân mã:
$A8\rightarrow C7\rightarrow E6\rightarrow C5\rightarrow E4\rightarrow G5\rightarrow E6\rightarrow C7\rightarrow A8$
Trong đó, theo như đề thì số ngô ở ô $A8$ đầu tiên sẽ không được tính, ở ô $A8$ cuối quân mã sẽ ăn nốt hạt ngô ở đó . Lúc đó ta có số ngô quân mã thu được sau các nước đi trên:
$S=2^{10}+2^{20}+2^{26}+2^{36}+2^{30}+2^{20}+2^{10}+2^{0}=69862426625\not{\vdots}3$
Vậy sau $8$ nước đi trên, số hạt ngô mà quân mã thu được không chia hết cho $3$. Vô lí
----------------------------------
Vậy: Em xin được chứng minh theo cách mỗi ô chỉ được đi một lần.
Áp dụng điều vừa chứng minh ở trên, giả sử nước đầu tiên quân mã đi là $B6$ thì trước nước cuối cùng quân mã phải ở ô $C7$, tức số nước đang lẻ ở ô có lũy thừa bậc chẵn của $2$, mà mỗi ô chỉ được đi một lần. Vậy tổng số thóc mà quân mã đã thu được ở thời điểm đó có dạng $2^{p}$ với $p$ lẻ tức tổng số thóc đó $\equiv -1 (\bmod3)$ (theo bổ đề). Vậy nước cuối cùng quân mã thu được hạt thóc ở ô $A8$ là $2^{0}=1$$\equiv 1 (\bmod3)$. Vậy cuối cùng số thóc mà quân mã thu được $\equiv -1+1=0 (\bmod3)$. Ta có điều phải chứng minh.
$\blacksquare \blacksquare \blacksquare$
Mở rộng $1$: Cho bàn cờ trống kích thước $m \times n$ , trong đó $m\leq n$ và $m;n$ đều lẻ, chứng minh một quân mã đặt từ một ô bất kì trên bàn cờ này không thể di chuyển sao cho trở lại được vị trí bạn đầu.
Chứng minh:
Trên bàn cờ vua, các ô đen và trắng xen kẽ nhau, một quân mã luôn đi từ một ô tới ô khác màu. Vì $m$ và $n$ đều là lẻ nên khi đó số các ô đen và trắng trên bàn cờ là khác nhau. Chẳng hạn bàn cờ $5 \times 5$ có $13$ ô đen và $12$ ô trắng. Muốn quân mã trở lại ô ban đầu thì phải có số ô đen và trắng bằng nhau, tổng số ô trên các nước đi là số chẵn. Do đó một hành trình đó không thể đi qua mỗi ô đúng một lần khi số các ô trên bàn cờ là số lẻ(theo đường đi Hamilton).
Từ đường đi Hamilton ta cũng chứng minh được mở rộng $2$: ( bằng lý thuyết đồ thị )
Cho bàn cờ vua trông có kích thước $8 \times 8$. Một con mã cũng được đặt ngẫu nhiên trên bàn cờ này. Hỏi quân mã có thể đi một hành trình sao cho kết thúc tại nơi nó bắt đầu đi sao cho mỗi ô chỉ được đi qua một lần? Biết quân mã đi theo đúng luật chơi cờ vua tức đi chéo hình chữ nhật có kích thước $2 \times 3$ hay gọi tắt là hình chữ $L-3$
Mở rộng $3$: Cho bàn cờ vua trông có kích thước $a \times a$ trong đó, $a\in \mathbb{N}^{*}$ và $3\mid a$. Đặt ngẫu nhiên số hạt ngô vào các ô trên bàn cờ sao cho tổng số hạt ngô bằng $a^{a}$ ( không chừa trống ô nào). Một con mã cũng được đặt ngẫu nhiên trên bàn cờ này. Hai người cùng chơi trò chơi sau. Mỗi lượt từng người sẽ di chuyển quân mã đi một nước và ăn số hạt ngô đặt ở ô vừa đi,nhưng không ăn hạt ngô ở ô bắt đầu, chỉ cho phép quân mã ăn số hạt ngô trong ô theo lũy thừa của $2$ ( tức $2^{0};2^{1};2^{2};...$). Cứ như thế... cho đến hết hạt ngô trên bàn cờ. Vì sao người chơi sau luôn thắng nếu có một chiến thuật hợp lí? Biết quân mã ở đây có thể nhảy tự do ( ) sang bất cứ ô nào trên bàn cờ sao cho ô đó có hạt ngô ( có thể nhảy qua lại một ô bao nhiêu lần tùy ý) và người chiến thắng là người di chuyển mã để ăn hết hạt ngô cuối cùng.
Đáp án:
Người chơi sau luôn thắng nếu có chiến thuật như sau:
Luôn nhảy đến ô có số hạt ngô có luỹ thừa bậc khác tính chẵn lẻ với luỹ thừa bậc (chẵn hoặc lẻ ) của $2$ mà người chơi trước đã ăn.
Chứng minh: Áp dụng bổ đề đã chứng minh ở đầu bài. Sau một lượt chơi, số hạt ngô còn lại trên bàn sẽ giảm đi một lượng $\equiv -1+1=0 (\bmod3)$. Cứ như thế cho đến hết lượt cuối cùng. Nguời thứ hai sẽ luôn là người đi sau và tin chắc mình sẽ ăn hạt ngô cuối cùng bởi $3\mid a\Rightarrow 3\mid a^{a}$ nên cứ mỗi lượt số sỏi lại chia hết cho $3$.
$\blacksquare \blacksquare \blacksquare \blacksquare \blacksquare$