2018020613549個人組兩隊來打3對3籃球的問題

包包仔內底囥著妳,愛呷的烏糖粿,我若忝矣,呷一喙會當感受,妳對我的疼惜。

— 取自歌曲《烏糖粿》

一、前言

      在師大許志農教授提供的《算術講義》第 13 章中,許老師在其文章最後給了一個挑戰題,請參考[1]。其實該挑戰題裡面有兩段,兩者之間或許有相關。但為了方便討論,我們將其分述如下:

[問題1]:空間中有六個相異點,任何四點都不共平面,並將此六點中,任兩相異點作線段。如果將這些線段塗上白色或黃色的油漆,則可以從六點中找到相異的三點,使此三點所連成的三個邊都是同一個顏色的(稱這種三角形為單色三角形)。是否能更進一步證明:無論你如何塗顏色(仍限定白、黃二色),這種單色三角形至少可以找到兩個以上。

[問題2]某籃球鬥牛賽接受高中生當場組隊比賽,但是規定每隊由三人組成且此三人必須兩兩互相認識或者彼此完全不認識方可組成一隊。若現場有9 位高中生,則試說明可以組成兩隊來進行籃球鬥牛賽。倘若現場僅有8 位高中生時,那麼是否有辦法組成兩隊來進行籃球鬥牛賽呢?

      其中[問題1]的第一題在本站文章[2]中的[性質1]已經回答了,讀者不妨先參考一下該性質的證明。

二、只有一半的證明

      先關心[問題2]中的兩個問題。如果我們把上面[問題2]的9 個人想成9個頂點,其中兩個人互相認識就在代表那兩人的頂點間連上紅色邊,反之,如果兩個人互相不認識就在代表那兩人的頂點間連上綠色邊。因此,問題1 就轉化為一個有九個頂點的圖,且每兩點間恰有一邊,邊的顏色為綠色或紅色。

      假設上面 9 個頂點的名字為1,2,3,…,9,則現在可以分析問題如下:

[解答]:對於1,2,3,4,5,6這六個人來說,由[1]的性質1,可知他們之中必然有三個人滿足兩兩互相認識或者彼此完全不認識。不失一般性,假設1,2,3這三個人兩兩互相認識或者彼此完全不認識,且他們決定組成一隊,那剩下還沒有組隊的,就是4,5,6,7,8,9這六個人。

      剩下的六個人之中,再次利用[1]的性質1,再次可知他們之中必然有三個人滿足兩兩互相認識或者彼此完全不認識,因此這三個人又可再組成第二隊。至此,[問題2]的第一部份就解決了。

      如果只有8個人,稱他們為1,2,3,4,5,6,7,8。對於1,2,3,4,5,6 這六個人來說,跟據上面的討論,可知他們之中必然有三個人可組成一隊。假設還是1,2,3組成一隊,而剩下的4,5,6,7,8這五個人,是存在有可能無法組隊的反例的,如下圖:


圖1

      不過圖1的反例,不一定表示8個人必然無法組成兩隊。原因是,你怎麼知道1,2,3,4,5,6,7,8一定要先由1,2,3先組第1隊,才發現4,5,6,7,8像上圖無法組第2隊呢?說不定,這8個人有另外的方法可以組成兩隊,比如說,1,4,6互相認識組成第一隊,2,5,7兩兩不認識組成第二隊(此時1,2,3也不用組隊了),這樣就有兩隊了。

      許老師想問的,應該不是「8個人是否有可能組成兩隊」,原因很簡單,只要假設1,2,3彼此認識且4,5,6彼此認識,這樣就有兩隊了。所以,許老師想問的,應該是底下的問題:

命題1:「請說明八個人是否存在一種情況,使得他們無法組成兩隊」

筆者發現這是個有難度的問題,難在反例不太好找。或者,至少對筆者來說不簡單。

      所以,[問題2]的第二部份筆者尚未解出,證明只完成了一半。有興趣的讀者,不妨來試試。

三、結語

      看起來,要說明任意8個人究竟有沒有一種情形使得無法組成兩隊,比說明9 個人一定有辦法組成兩隊來得困難,可是說不定也沒那麼難,只是需要一個反例,這個反例中有八個頂點,且用兩種顏色塗完各邊後,裡面沒有兩個「不共用頂點」的同色三角形。因為,有兩個「不共用頂點」的同色三角形,就可以組成兩隊了。

      說到「不共用頂點[問題1]的第二題要找的兩個同色三角形,則不必受到共用頂點與否」的限制,因為沒有要組隊。這是[問題1]與[問題2]兩者的第二小題之間的差異。筆者畫了好幾個圖,發現都有兩個同色三角形,卻想不到方法說明一般情形。所幸再努力後,已經解決了這個問題。

       也許有一天,只要繼續研究,終將可以知道如何證明[問題2]的第二小題。至於文章開始前分享的歌詞,是取自[3]這首台語歌,有興趣的讀者不妨聽聽,也可以聽聽[4]這個稍微改編過,把淡淡哀愁轉化為正面能量的版本。

   

[參考資料]

[1]許志農,哈密頓原理,算術講義

http://math.ntnu.edu.tw/~maco/macobook/arith/13.pdf

[2]K17完全圖的一個小問題,本站文章

http://blog.xuite.net/isdp2008am/wretch/241214512

[3]烏糖粿,曲:蔡婉怡 詞:蔡婉怡/陳怡安,有感覺樂團

https://www.youtube.com/watch?v=05kgtPstGYU

[4]烏糖粿改編版,曲:蔡婉怡 詞:蔡婉怡/陳怡安,有感覺樂團

https://www.youtube.com/watch?v=os5wrk_-ark

(本文作者:連威翔,曾任職於交大理學院科學學士班)

沒有上一則|日誌首頁|沒有下一則
回應
關鍵字
    沒有新回應!





Powered by Xuite