分割問題的若干結(jié)論
一個m×n的大矩形可以由a×b的小矩形拼接而成,當(dāng)且僅當(dāng)(1)mn=ab;(2)m和n均可寫成a和b的和的形式;(3)n或m是a的倍數(shù)且n或m是b的倍數(shù)?!灸峁爬?德布魯因,大衛(wèi)?克拉那爾,1969】
存在至少一種分割問題,該問題不能由涂色法證明。【約翰?康威,杰佛瑞?拉加利亞斯,1990】
“一個由方塊并列構(gòu)成的圖形能否由水平放置的1×2矩形和豎直放置的1×3矩形構(gòu)成?”是一個NP完全問題?!景@锟?雷米拉,邁克?羅伯森,1995】
3.1? 如果取消水平豎直的限制,復(fù)雜程度為O(n)?!?span id="s0sssss00s" class="font-size-16">埃里克?雷米拉】
傳遞定理:若矩形R能以一系列矩形瓦塊拼接而成,且每一個矩形瓦塊都至少有一條邊的長度為整數(shù),則矩形R本身也至少有一條邊的長度為整數(shù)。
4.1? 傳遞定理可以推廣到有理數(shù)和代數(shù)數(shù)。
最少需要21個大小不同的正方形才能拼成一個大正方形,且此時拼接的方式是唯一的?!径啪S斯?迪恩,1978】
可以用邊長為1,2,3,…,n的正方形鋪滿整個平面,且每個正方形僅用一次?!痉鹄椎吕锟?亨勒,詹姆斯?亨勒,2008】
當(dāng)且僅當(dāng)t為代數(shù)數(shù),且其極小多項式的所有根的實部為正數(shù)時,1×t矩形的相似矩形可以拼接成正方形?!究死锼?佛雷凌,丹?里納,1994;米克洛斯?拉斯科維奇,喬治?塞凱賴什,1995】
只有不超過2種分割方法可以將一個大矩形分割成三個完全相同的部分,且分割得到的部分也必須是矩形?!舅_穆埃爾?馬爾特比,1992】
若矩形(正方形)能以等面積三角形拼接而成,則三角形的數(shù)目為偶數(shù)。【保羅?蒙斯基,1970】