SET - 桌遊

先說結論......

我花時間找到答案之後才發現已經有大大寫過這篇文章了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

--