# 費氏蛇

2007年

## 摘要或動機

At the website “MathLinks EveryOne,” we found a problem “Snakes on a chessboard,” which was raised by Prof. Richard Stanley. The following is the problem. A snake on the m n chessboard is a nonempty subset S of the squares of the board with the following property: Start at one of the squares and continue walking one step up or to the right, stopping at any time. The squares visited are the squares of the snake. Prove that the total number of ways to cover an m × n chessboard with disjoint snakes is a product of Fibonacci numbers. We call the total number of ways to cover a chessboard with disjoint snakes “the snake-covering number.” This problem hasn’t been solved since it was posted on September 18, 2004, so it aroused our interest to study it. First, we used the way in which we added each block to the chessboard, and therefore we discovered some regulations about the snake-covering number of the1 × n , 2 × n and 3 × n chessboard. Through “recursive relation” and “mathematical induction”, we proved the general term of the snake-covering number of the1 × n , 2 × n and 3 × n chessboard. In the following study, we found a key method in which we added a group of blocks to the chessboard. Finally, we proved the general term of the snake-covering number of the m × n chessboard. Also, we discovered the way to figure out the snake-covering number of the nonrectangular chessboard.在網站“ MathLinks EveryOne ”中，我們找到了一個有趣的問題“棋然上的蛇” ( Snakes on a chessboard ) ，這個問題是由教授 Richard Stanley 所提出。問題如下：在m x n棋盤形格子上，蛇由任意一格出發，但蛇的走法只能往右 → ，往上↑，或停住 ‧ 若此蛇已停住，將由另一條蛇來走，且不同蛇走過的格子不可重疊”證明：將 m × n 棋盤形格子完全覆蓋的總方法數為費氐（ Fibonacci ）數列某些項的乘積。我們將把棋盤形格子完全覆蓋的所有方法數稱之為“蛇填充數” 由於這個問題自從 2004年 9 月 18 日被登在網站上後，還沒有人提出解答，於是引發了我們研究的興趣。首先，我們使用了將一個一個格子加到棋盤上的方法，並發現了 l × n 、 2 x n、 3 × n 棋盤形格子蛇填充數的一些規律。我們使用遞迴關係及數學歸納法來證明 l x n 、 2 x n ， 3 × n 棋盤形格子蛇填充數的一般項。在接下來的研究中我們發現一個特別的方法，一次增加數個方塊 ‧ 最後我們證明了，m x n, ，棋然形格子的蛇填充數的一般項 ‧ 而且，我們也找到如何求出不規則棋盤形格子的蛇填充數。

「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」，以及 提供使用者有文書軟體選擇的權利，本館檔案下載部分文件將公布ODF開放文件格式， 免費開源軟體可至LibreOffice 下載安裝使用，或依貴慣用的軟體開啟文件。」