tại-sao-tro-choi-ghep-15-o-khong-the-giai-duoc

Tại sao trò chơi Ghép 15 ô không thể giải được?

Trò chơi "Ghép 15 ô", còn được gọi là "Bài toán 15 số", không phải là không thể giải được, mà là trạng thái đích không thể đạt được trong một số trạng thái ban đầu.

Mô tả trò chơi

"Ghép 15 ô là một trò chơi trượt, trong đó bàn chơi là một lưới 4x4 chứa 15 ô trượt được đánh số từ 1 đến 15 và một ô trống. Mục tiêu của người chơi là di chuyển các ô trượt theo thứ tự từ trái sang phải, từ trên xuống dưới, tạo thành một chuỗi có thứ tự từ 1 đến 15, với ô trống nằm ở góc dưới bên phải.

Các trường hợp không thể giải được

Trạng thái không thể di chuyển hợp lệ để đạt được trạng thái mục tiêu nếu và chỉ nếu số cặp nghịch đảo trong trạng thái ban đầu là lẻ. Một cặp nghịch đảo là một cặp số trong một dãy được gọi là một cặp nghịch đảo nếu vị trí trước và sau của chúng nằm theo thứ tự ngược lại về độ lớn, nghĩa là số ở phía trước lớn hơn số ở phía sau. Ví dụ, trong dãy 2, 4, 3, 1, các cặp nghịch đảo là (2, 1), (4, 3), (4, 1), (3, 1), tổng cộng là bốn cặp.

Chứng minh.

Việc di chuyển các ô trượt trên bàn chơi có thể được coi như một phép biến đổi của sự sắp xếp các ô trượt này. Mỗi khi một ô trượt được di chuyển, một ô trống thực sự được trao đổi với một ô trượt lân cận. Và thao tác hoán đổi này thay đổi tính chẵn lẻ của số mũ nghịch đảo của sự sắp xếp. Số mũ nghịch đảo của trạng thái mục tiêu là 0, là số chẵn. Nếu số mũ nghịch đảo của trạng thái ban đầu là lẻ, bất kể di chuyển bao nhiêu lần, số mũ nghịch đảo của nó không thể được thay đổi thành số chẵn, và trạng thái mục tiêu không thể đạt được.

Nếu bạn thích chơi Puzzles ball nữa, nó hoàn toàn miễn phí, thú vị và dễ dàng.