Re: [閒聊] SET

看板BoardGame (桌遊 - Board Games)作者tony332976 (tony)時間9年前 (2015/11/17 00:48)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串2/2 (看更多)

先說結論...... 我花時間找到答案之後才發現已經有大大寫過這篇文章了QAQ 只好跟大家聊一下心路歷程前些日子有位朋友突然表示， http://www.plurk.com/p/lble35 「set這款桌遊發到第幾張的時候必定有解?15張不行，17張應該可以。」「因為各缺一樣的情況下(沒綠色、沒有3、沒有空心、沒有菱形)，只要再多任何一張牌就會形成set了。」當下看到的大家雖然不明白但覺得好像很厲害，便各回各家各找各媽去了。那天夜裡我躺在床上進入夢鄉之後，我在夢中看見了許久不見的高中數學老師，他緩步走到我面前，搖著搖頭說道: 「痴兒阿，痴兒阿」，我好像明白了什麼又好像什麼都不明白「老師，我做錯了什麼嗎?」他說道:「你忘了為師怎麼教你的嗎?」 “x張牌任選3張牌，都不能形成一組解，x最大為多少?” 這個問題並不等於 “x張牌任選3張牌，能夠形成一組解，x最小為多少” 後面這個問題的答案是2阿! 因為如果只是能夠形成一組解的(硬找一組)能只需要3張牌(就剛好找出一組set) 但是上面那兩個命題要等價，下面的問題應該要是 “x張牌任選3張牌，必然形成一組解，x最小為多少” (請參考高中數學有關等價命題的部分) 夢到了這裡，我忽然就醒了過來，才發現已經濕透了全身醒來之後我就開始思索這個問題的答案是什麼? 如果要寫一個程式的話，我可能會想要這樣表達每張牌以(a,b,c,d)表示 a,b,c,d分別為-1、0、1三個數字，每一張牌皆唯一將81張牌取3地所有可能表示出來而每一組3張牌中a、b、c、d分別加總只要有一個總合為3的倍數(-3、0、3)就把該組踢掉但後來想想寫一個程式實在太麻煩了以我高中數學老師的名義發誓要找出一個數學思路也是一樣不太可行這時候我大學時候受過的專業google訓練突然就派上用場了 …… …… https://zh.wikipedia.org/wiki/%E7%A5%9E%E5%A5%87%E5%BD%A2%E8%89%B2%E7%89%8C 咦?維基百科好像就有夠多的分析了這個問題他也有提供參考的論文，雖然連結已死，但其實搜尋得到 http://homepages.warwick.ac.uk/staff/D.Maclagan/papers/set.pdf 之後又是一個夜裡我躺在床上進入夢鄉之後，這次我見到的數學老師他面帶著微笑說道: 「孺子可教也」「老師，這就是你不願意傳授我的最後一招遇強則屈借花獻佛嗎?」「啪!」我的後腦勺忽然被打了一下一回頭，我夢醒了正準備上板PO文前才注意到已有前人的文章只好抱著至少讓文章浮上來或許也有人會喜歡這個主題吧:P ※ 引述《hcy1 ()》之銘言： : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 1 ======= : 原始問題是：「最多可以湊出幾張牌，在裡面完全找不出SET。」 : 以下是我在網路上找到的解答。 : 網址： http://www.setgame.com/set/noset.htm : 或許有人不想看英文，我試著翻譯成中文， : 由於有圖且頁數較多，以固定頁面位置方式，方便大家閱讀。 : 按 Page Down / Page Up 或 ↑ ↓ 可換頁 : 按 q 或 Ctrl-C 可中斷 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 2 ======= : 處理複雜的問題前，通常會先把問題簡化 : 因此我們先只觀察一張牌的兩種特性： : 形狀 (彎曲形、菱形、楕圓形) 與數量(1、2、3) : 如此，我們可以使用一個3x3的矩陣，來標示出每一張牌 : 　１　２　３ : 　┌─┬─┬─┐ : 彎 │●│ │ │ : 　 ├─┼─┼─┤ : 菱 │ │ │ │ : 　 ├─┼─┼─┤ : 圓 │ │ │ │ : 　 └─┴─┴─┘ : 舉例來說，在上圖中，這個圓點代表的牌：1個彎曲形。 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 3 ======= : 利用這個矩陣，我們可以觀察出3張牌是否形成一個SET： : 只要在矩陣上連成一條線 (直、橫、斜皆可)，即代表這3張牌是一個SET。 : 　１　２　３ : 　┌─┬─┬─┐ : 彎 │●│ │ │ : 　 ├─┼─┼─┤ : 菱 │●│ │ │ : 　 ├─┼─┼─┤ : 圓 │●│ │ │ : 　 └─┴─┴─┘ : 舉例來說，在上圖中，3張牌的圖形數量相同、形狀不同。 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 4 ======= : 同樣的，在下面的三個圖中，由於都連成一線，因此也都是一種SET。 : 　１　２　３　１　２　３１　２　３ : 　┌─┬─┬─┐ 　 ┌─┬─┬─┐ ┌─┬─┬─┐ : 彎 │ │ │●│ 　彎 │ │ │ │ 彎 │ │●│ │ : 　 ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ : 菱 │ │●│ │ 　菱 │ │ │ │ 菱 │ │ │●│ : 　 ├─┼─┼─┤　　　　　 ├─┼─┼─┤ ├─┼─┼─┤ : 圓 │●│ │ │ 　圓 │●│●│●│ 圓 │●│ │ │ : 　 └─┴─┴─┘ 　 └─┴─┴─┘ └─┴─┴─┘ : 左：數量不同、形狀不同。中：數量不同、形狀相同。右：數量不同、形狀不同。 : 需特別注意最右邊的圖，直觀看起來雖然不是一直線，但是把１這一直列移到最右邊， : 還是一個直線。　(把矩陣想成左右兩端會繞回來接在一起) : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 5 ======= : 在只有形狀與數量兩種特性下，最多可以找到幾張牌，而不會在當中形成SET呢？ : 利用這個矩陣，我們便可以找到答案。 : 　１　２　３ : 　┌─┬─┬─┐ : 彎 │●│ │●│ : 　 ├─┼─┼─┤ : 菱 │ │ │ │ : 　 ├─┼─┼─┤ : 圓 │●│ │●│ : 　 └─┴─┴─┘ : 如上圖所示，最多可以標示4個點，而仍然不會構成連線。 : 意即若只有兩種特性，可以找得出4張牌而不會形成SET。 : 若是加入第5張，則必定會有SET存在。 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 6 ======= : 現在我們再加入第三種特性：填滿狀態 (實心、空心、斜線) : 由於有了第三種特性，所以需要有3個3x3的矩陣。 : 而要觀察連線，可以把這3個3x3的矩陣想像成是疊在一起的，也就是3D版的井字遊戲。 : 　１　２　３　１　２　３１　２　３ : 　┌─┬─┬─┐ 　 ┌─┬─┬─┐ ┌─┬─┬─┐ : 彎 │●│ │●│ 　彎 │ │○│ │ 彎 │ │ │ │ : 　 ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ : 菱 │ │ │ │ 　菱 │○│ │○│ 菱 │ │◎│ │ : 　 ├─┼─┼─┤　　　　　 ├─┼─┼─┤ ├─┼─┼─┤ : 圓 │●│ │●│ 　圓 │ │○│ │ 圓 │ │ │ │ : 　 └─┴─┴─┘ 　 └─┴─┴─┘ └─┴─┴─┘ : 　實心　　　　　　　　　　　空心斜線 : 如上圖所示，在這個3層的3x3矩陣中， : 我們最多可以標示出9個點，而仍然不會形成任何連線。 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= Page 7 ======= : 最後，我們再放入第四種特性：顏色 (紅、綠、紫)。 : 現在是立體版的井字遊戲，再加上第四維度 - 時間軸。 : 或著也可以想像成往兩種方向交疊的立體版井字遊戲。 : 我們總共需要 3x3 個 3x3 的矩陣來標示81張牌。 : 在當中最多可以標示出幾個點，而不會構成連線呢？ (不會形成SET) : 答案是： 20。 (若抽出21張牌，則當中100%會存在SET) : 完整圖示見下頁。 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : 　１　２　３　１　２　３１　２　３ : 　┌─┬─┬─┐ 　 ┌─┬─┬─┐ ┌─┬─┬─┐ : 彎 │●│ │●│ 　彎 │ │○│ │ 彎 │ │ │ │ : 　 ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ : 菱 │ │ │ │ 　菱 │○│ │○│ 菱 │ │◎│ │ 紅 : 　 ├─┼─┼─┤　　　　　 ├─┼─┼─┤ ├─┼─┼─┤ : 圓 │●│ │●│ 　圓 │ │○│ │ 圓 │ │ │ │ : 　 └─┴─┴─┘ 　 └─┴─┴─┘ └─┴─┴─┘ : 　┌─┬─┬─┐ 　 ┌─┬─┬─┐ ┌─┬─┬─┐ : 彎 │ │●│ │ 　彎 │○│ │○│ 彎 │ │ │ │ : 　 ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ : 菱 │●│ │●│ 　菱 │ │ │ │ 菱 │ │◎│ │ 綠 : 　 ├─┼─┼─┤　　　　　 ├─┼─┼─┤ ├─┼─┼─┤ : 圓 │ │●│ │ 　圓 │○│ │○│ 圓 │ │ │ │ : 　 └─┴─┴─┘ 　 └─┴─┴─┘ └─┴─┴─┘ : 　┌─┬─┬─┐ 　 ┌─┬─┬─┐ ┌─┬─┬─┐ : 彎 │ │ │ │ 　彎 │ │ │ │ 彎 │ │ │ │ : 　 ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ : 菱 │ │●│ │ 　菱 │ │○│ │ 菱 │ │ │ │ 紫 : 　 ├─┼─┼─┤　　　　　 ├─┼─┼─┤ ├─┼─┼─┤ : 圓 │ │ │ │ 　圓 │ │ │ │ 圓 │ │ │ │ : 　 └─┴─┴─┘ 　 └─┴─┴─┘ └─┴─┴─┘ : 　實心　　　　　　　　　　　空心斜線 : ^L#@N@d,f+1,下一頁#@P,f-1,上一頁#@d,f+1,下一頁#@u,f-1,上一頁# : ======= End ======= : 思考這個問題的過程，其實滿有趣的，也衍伸想了一些其他的問題。 : 不過這個原始題目的解答，對我來說還真的滿困難的。 : 最後，附上BGG上面的一張圖，就是完全找不出SET的20張牌。 : http://www.boardgamegeek.com/image/421151/set : ^LE -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.96.202 ※ 文章網址: https://www.ptt.cc/bbs/BoardGame/M.1447692520.A.C82.html ※ 編輯: tony332976 (140.123.105.61), 11/17/2015 09:54:43