環狀圖形上的相遇機率

作品摘要

「在一個具有 $n$個頂點的環狀圖形上，有兩人 A、B 分別在兩個不同的頂點上。設 A、B 兩人之間的距離為 $d$條邊，兩人每次移動時，可選擇向左或向右移動（不可留在原地不動），且每次都是移動至相鄰頂點，兩人皆移動 $m$次。能否求出兩人在移動過程中，曾在圖形中的任何一個頂點上相遇的機率？」本研究利用矩陣來探討此問題，試圖找出求相遇機率的計算方法，而最後不僅以歸納出了轉移矩陣以及「初始狀態轉換矩陣」的規律性，並透過程式語言寫出了輸入 $n, d, m$即可得到轉移機率的程式，另外也在研究的過程中發現了許多關於求出矩陣的有趣性質。