K-分割問題

Abstract

假設正整數 n≧k≧2。一個（k，n）一分割（（k ，n ）－partition ）是一由k 個 和為（ /2 ）的正整數P P ....P 所構成的非遞減序列（sequence），（P ,P , .....P ) 令N ＝｛１，２，…n ｝。若存在一組N 的互不相交子集N ,N ,..., N， 使得所有N 的聯集等於N ，且對於每一個i ， Ni 中所有數字的和均等於P ，則我們 稱這個（K ，n ）一分割是存活的（alive ）否則，就稱這個（k,n ）一分割是死亡 的（dead）。K －分割問題（K-partition problem ）就是來決定一個（K ，n ）一 分割是存活的還是死亡的。 在本論文中我們將注意力集中在k≦5的K －分割問題：第一節是一些基本定義和到目 前為止有關這個題目所已知的一些結果的介紹；第二節是有關一般K －分割問題的一 些性質的探討，並發展一些有助於我們解決問題的想法和工具；第三節則是利用第二 節所發展出來的想法和工具來解決K≦5的K －分割問題－也就是說，我們找出所有死 亡的（K ，n ）－分割，對於那些存活的，我們也有一個演算法（algorithm ）來求 出所有P 的組成元素；最後，在第四節我們提出我們對於這個問題的心得，以及二個 有趣的假說（conjecture）