證明一系列的操作不能達到某個結果,一般的思路是這樣(當然不排除別的思路,具體問題具體分析):
1、確定操作具體是什麼。
2、尋找某個(些)量,這個量在操作前後是不變的,這個量又被稱為不變數。
3、如果兩個狀態的不變數是不同的,那麼肯定不能透過該操作來互換這兩個狀態。
當然,難就難在尋找不變數。
可以把黑框記為 ,從左到右,從上到下這樣排列起來,本題就是 和 這兩個狀態的互換。
對於這類問題的不變數,學界早已研究清楚——不變數是逆序數的奇偶。
例如: ,逆序的數對有: , , , , ,所以逆序數是 ,逆序數是奇的。可以證明,在 的一個排列上,交換任意一對數對,逆序數奇偶性改變。具體證明過程可參閱有講到逆序的線性代數書籍、抽象代數書籍。或者,自己動手證明一下也不是什麼難事。
本題具體的操作是什麼呢?注意在這裡,並不能任意數對互換,只有 才代表黑框,每一次移動本質上都是 在移動。而且,移動到最後, 必須回到原來的位置。設移動的次數為 。再設 經過上、下、左、右四個方向移動的次數分別為: 、 、 、 (上下左右的英文首字母),那麼必有: 。又因為最後 會回到原位,所以有多少次向上移動,就必定有多少次向下;有多少次向左移動,就必定有多少次向右,於是 , 。於是 是偶數。
每移動一次,就是交換一對數對,那麼逆序數的奇偶就改變一次。共改變了 次,而且 是偶數,所以最後逆序數的奇偶不變。
這就證明了題目無解。
至於還有沒有更簡單的不變數,你不妨嘗試尋找一下,不要侷限於一種方法。
證明一系列的操作不能達到某個結果,一般的思路是這樣(當然不排除別的思路,具體問題具體分析):
1、確定操作具體是什麼。
2、尋找某個(些)量,這個量在操作前後是不變的,這個量又被稱為不變數。
3、如果兩個狀態的不變數是不同的,那麼肯定不能透過該操作來互換這兩個狀態。
當然,難就難在尋找不變數。
可以把黑框記為 ,從左到右,從上到下這樣排列起來,本題就是 和 這兩個狀態的互換。
對於這類問題的不變數,學界早已研究清楚——不變數是逆序數的奇偶。
在 的一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。例如: ,逆序的數對有: , , , , ,所以逆序數是 ,逆序數是奇的。可以證明,在 的一個排列上,交換任意一對數對,逆序數奇偶性改變。具體證明過程可參閱有講到逆序的線性代數書籍、抽象代數書籍。或者,自己動手證明一下也不是什麼難事。
本題具體的操作是什麼呢?注意在這裡,並不能任意數對互換,只有 才代表黑框,每一次移動本質上都是 在移動。而且,移動到最後, 必須回到原來的位置。設移動的次數為 。再設 經過上、下、左、右四個方向移動的次數分別為: 、 、 、 (上下左右的英文首字母),那麼必有: 。又因為最後 會回到原位,所以有多少次向上移動,就必定有多少次向下;有多少次向左移動,就必定有多少次向右,於是 , 。於是 是偶數。
每移動一次,就是交換一對數對,那麼逆序數的奇偶就改變一次。共改變了 次,而且 是偶數,所以最後逆序數的奇偶不變。
這就證明了題目無解。
至於還有沒有更簡單的不變數,你不妨嘗試尋找一下,不要侷限於一種方法。