Chủ đề này có 5 trả lời

[Math Is Love]

$\boxed{\text{Bài toán}}$Cho một bảng hình vuông kích thước $10\times 10$ và một quân xe ở ô bất kì trên bảng.Ta di chuyển con xe trên bảng theo luật chơi cờ. Biết rằng các nước đi chỉ có thể là nước đi $1$ ô hoặc nước đi $2$ ô và các nước đi $1$ và nước đi $2$ luân phiên xen kẽ nhau(bước đầu tiên có thể là $1$ hoặc $2$).Hỏi quân xe này có thể "đứng" qua tất cả các ô trên bảng sao cho mỗi ô nó "đứng" đúng $1$ lần hay không?

Bài viết đã được chỉnh sửa nội dung bởi doxuantung97: 25-10-2012 - 19:06

[hxthanh]

Sau khi xem xét một cách cẩn thận thì bài này không hề đơn giản!

Mục đích của bài toán là: chỉ ra tồn tại hay không tồn tại một chu trình Hamilton với $\dfrac{n^2}{2}$ "cạnh 1" và $\dfrac{n^2}{2}$ "cạnh 2" qua $n^2$ đỉnh.
$($Với hình vuông $n\times n)$

Đối với $n=4$ hoặc $n=8$ có thể chỉ ra một cách tạo chu trình Hamilton như hình dưới đây
 Banco.png   62.36K   20 Số lần tải

Đối với $n$ lẻ dễ dàng chứng minh được không tồn tại chu trình này
Còn các trường hợp khác ?

[The Gunner]

Ta đánh số bảng như sau:
0 1 2 3 0...
1 2 3 0 1...
2 3 0 1 2...
3 0 1 2 3...
0 1 2 3 0...
ta cứ đánh số như vậy cho đến hết bảng thì ta thấy ở ô đánh số $i$ thì nó sẽ có đường đi đến các ô có giá trị như sau ( tính theo mod 4
$i \to i+1 \to i+3 \to i \to i+2 \to i+3 \to i+1 \to i+2 \to i$ (*)
Đk cần để tồn tại một chu trình là bắt đầu từ ô $i$ cũng phải kết thúc tại ô $i$
Nếu $n$ lẻ thì có $n^2$ bước đi , mà khi đó bước đi cuối cùng là cạnh 1 nên theo (*) thì số bước đi có dạng $4k+3$ vô lí
Nếu $n$ chẵn thì bước đi cuối cùng có cạnh 2 nên theo (*) số bước đi phải chia hết cho 8 nên suy ra $ n^2$ chia hết cho 8. do đó $n$ phải chia hết cho 4
Vói $n=4k$ thì em chưa tìm được thuật toán tổng quát hi vọng thầy hxthanh có thể tìm đc thuật toán tổng quát cho TH này. còn với bài toán trên $n=10$ là ko thể

[hxthanh]

Một cách độc lập với The Gunner, tôi cũng chứng minh được $n=4k$ là điều kiện cần để tồn tại chu trình bằng cách đánh số bảng đúng như thế!

Nhưng đó chưa phải là điều kiện đủ! $n=12$ là một ví dụ (thực hành nhưng chưa chứng minh) rằng không tồn tại chu trình

Nếu không bó buộc về kích thước của bảng thì tôi nhận thấy: Độ dài của một chu trình bất kỳ (bắt đầu từ một ô và kết thúc tại ô đó) phải là một luỹ thừa của $2$

Tồn tại các chu trình $2^2, 2^3, 2^4, 2^5, 2^6, ... $ cạnh.
...
Xem ra bài toán này còn nhiều điều cần nghiên cứu lắm!

[Math Is Love]

ta cứ đánh số như vậy cho đến hết bảng thì ta thấy ở ô đánh số $i$ thì nó sẽ có đường đi đến các ô có giá trị như sau ( tính theo mod 4
$i \to i+1 \to i+3 \to i \to i+2 \to i+3 \to i+1 \to i+2 \to i$ (*)
Đk cần để tồn tại một chu trình là bắt đầu từ ô $i$ cũng phải kết thúc tại ô $i$
Nếu $n$ lẻ thì có $n^2$ bước đi , mà khi đó bước đi cuối cùng là cạnh 1 nên theo (*) thì số bước đi có dạng $4k+3$ vô lí
Nếu $n$ chẵn thì bước đi cuối cùng có cạnh 2 nên theo (*) số bước đi phải chia hết cho 8 nên suy ra $ n^2$ chia hết cho 8. do đó $n$ phải chia hết cho 4
Vói $n=4k$ thì em chưa tìm được thuật toán tổng quát hi vọng thầy hxthanh có thể tìm đc thuật toán tổng quát cho TH này. còn với bài toán trên $n=10$ là ko thể

Nhưng mà bạn ơi!Cách bạn làm là chỉ đối với trường hợp nước đi đầu tiên là nước đi $1$.Nhưng nếu nước đi đầu tiên là nước đi $2$ thì sao?

Một cách độc lập với The Gunner, tôi cũng chứng minh được $n=4k$ là điều kiện cần để tồn tại chu trình bằng cách đánh số bảng đúng như thế!

Nhưng đó chưa phải là điều kiện đủ! $n=12$ là một ví dụ (thực hành nhưng chưa chứng minh) rằng không tồn tại chu trình

Nếu không bó buộc về kích thước của bảng thì tôi nhận thấy: Độ dài của một chu trình bất kỳ (bắt đầu từ một ô và kết thúc tại ô đó) phải là một luỹ thừa của $2$

Tồn tại các chu trình $2^3, 2^4, 2^5, 2^6, ... $ cạnh.
...
Xem ra bài toán này còn nhiều điều cần nghiên cứu lắm!

Đây là đáp án của bài toán này,thầy xem có áp dụng được để giải bài tổng quát không nhé!
Tô màu bảng như sau.

Theo cách tô trên thì sẽ có $58$ ô đen và $48$ ô trắng
TH1:Nước đi đầu tiên là nước đi $1$:
Vì tổng cộng có $99$ nước đi nên sẽ có $50$ nước đi $1$ và $49$ nước đi $2$.
Nhận xét,mỗi nước đi 2 sẽ đứng qua $1$ ô trắng và $1$ ô đen.Hai nước đi $2$ liên tiếp sẽ không bị trùng ô nào do có nước đi $1$ phân cách.Như vậy sẽ có $$\geq 49$$ ô trắng do chưa kể quân đầu tiên là ô trắng hay ô đen.
Tuy nhiên trên bảng chỉ có $48$ ô trắng nên vô lí,không thể thực hiện.
TH2:Nước đi đầu tiên là nước đi $2$.
Tương tự
P/S:Bài này thầy giáo em cho 6 anh ôn thi IMO vừa rồi làm mà mấy tuần mà các anh ý vẫn không ra!Hại não thật!Khó nhất là cách tô màu.

[The Gunner]

lúc đầu đọc đề mình tưởng là đi bước 1 trc. Nhưng ko sao nếu đi bước 2 trc thì tương tự như trên thì nếu n lẻ thì ta có số bước đi có dạng 8k+5 ko chính phưưng (vô lí). Còn với n chẵn thì tương tự n chia hết cho 4.
P/s: cách của thầy bạn mình cũng đã thử, nhưng lúc đó đang làm bài tổng quát nên thấy cách đó khó khả thi ( chủ quan thôi)