主題
Search

Katona 問題


找到一個 f(n) 的最小值,即對於一個包含 n 個元素的集合分離族子集 的最小數量,其中分離族是一個集合子集集合,其中每對相鄰元素都被分離,每個元素都位於兩個不相交子集之一中。例如,字母表的 26 個字母可以用九個族的字母分隔

 (abcdefghi) (jklmnopqr) (stuvwxyz); (abcjklstu) (defmnovwx) (ghipqryz); (adgjmpsvy) (behknqtwz) (cfilorux).

該問題由 Katona (1973) 提出,並由 C. Mao-Cheng 於 1982 年解決,

 f(n)=min{2p+3[log_3(n/(2^p))]:p=0,1,2},

其中 [x]向上取整函式f(n) 是非遞減的,並且 n=1, 2, ... 的值為 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600)。 f(n) 增加的值為 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601),因此 f(26)=9,如前面的例子所示。


另請參閱

分離族

使用 探索

WolframAlpha

更多嘗試

參考文獻

Honsberger, R. "蔡茂誠對 Katona 關於分離子集族問題的解法。" Ch. 18 in Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 224-239, 1985.Katona, G. O. H. "組合搜尋問題。" In A Survey of Combinatorial Theory (Ed. J. N. Srivasta, F. Harary, C. R. Rao, G.-C. Rota, and S. S. Shrikhande). Amsterdam, Netherlands: North-Holland, pp. 285-308, 1973.Sloane, N. J. A. 序列 A007600/M0456 和 A007601/M0525 在 "整數序列線上百科全書" 中。

在 上引用

Katona 問題

請引用為

Weisstein, Eric W. "Katona 問題。" 來自 Web 資源。 https://mathworld.tw/KatonasProblem.html

主題分類