臺灣國際科展

表格塗色遊戲之分析

科展類別
臺灣國際科展作品
屆次
2018年
科別
數學
得獎情形
四等獎
學校名稱
臺北市立建國高級中學
指導老師
蔡韋弘
作者
謝明圜;曾冠儒
關鍵字
格子對,鴿籠原理,柯西不等式

摘要或動機

這份研究所探討的主題源自於1976年USAMO第一大題:將一4×7矩形方格表的每格塗色黑色或白色,欲使所有能構成矩形頂點的四個方格皆不全為同色。試證明其塗色必定失敗、或給出滿足的塗色方式。此研究從上述題目延伸,增加可填入的顏色數量、改變方格表的長寬,甚至將方格表改為三角格子表。研究過程主要運用鴿籠原理、組合數量之計算及柯西不等式來分析。我們已幾乎完整討論完矩形方格表中填入2色、3色,及三角格子表中填入2色的所有情況;並且對於矩形方格表,我們找到了一條判別式,可以判斷一般化的某情況下塗色是否必定失敗,但有部分必定塗色失敗的情況無法由此判別式判斷,需藉由其他方式討論。此外,我們也嘗試從滿足的塗色方式中找尋規律並建立構造的規則。


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

檔案名稱 檔案大小 格式
表格塗色遊戲之分析 1 MB Adobe Reader(Pdf)檔案