Home‎ > ‎

Spot It 問題

最近有一個卡牌遊戲叫 "Spot It",是在一堆卡牌中,每張牌上有固定數目的圖樣,而任意兩張卡牌都剛好只有一個圖樣是相同的。例如,假設第一張牌上的圖樣是

A B C D E F G H

而第二張牌的圖樣是

A I J K L M N O

也就是只有 A 是相同的。遊戲的基本玩法是,每個人各發一張牌,剩下的牌放在中間。先看出自己的牌和中間堆疊最上面一張牌中,是哪個圖案相同,喊出圖樣後就可以拿走該張牌。
收集到最多牌的人就獲勝。

遊戲本身沒什麼特別,但有趣的是,如果一張牌上有 n 個圖樣時,那最多可以有幾張牌呢?

很明顯的,如果只有一個圖樣,那當然只能有兩張牌。但是如果可以有兩個圖樣,其實可以有無限多的牌,即:

A B
A C
A D
A E
A F
... etc

但這樣很無趣。如果加上第二個條件,也就是每個圖樣都至少出現在兩張牌以上,那麼一張牌有兩個圖樣的情形,就會變成

A B
A C
B C

也就是只能有三張牌。同理,在三個圖樣的情形下,是:

A B C
A D E
A F G
B D F
B E G
C D G
C E F

共七張。

那要怎麼產生這樣的卡牌呢?如果 n - 1 是一個質數,那麼可以用以下的方式來建立。以 n = 6 為例,先組成以下的 array:

A B C D E F
A G H I J K 
A L M N O P
A Q R S T U
A V W X Y Z
A 1 2 3 4 5

這六張牌都只有 A 是相同的。現在,使用以下的方式產生所有包括 B 的牌(除了第一張之外),也就是,把 A B C D E F 以外,除了 A 所剩下的 matrix,採取垂直方向取得圖樣:

G H I J K
L M N O P
Q R S T U
V W X Y Z
1 2 3 4 5

這樣可以產生五張新牌:

B G L Q V 1
B H M R W 2
B I N S X 3
B J O T Y 4
B K P U Z 5

這五張牌,很明顯的互相只有 B 是相同的,且和之前的 A 開頭的牌,各只有一個圖樣相同。

接下來,對同一個 matrix,以 +1 的 offset 建立以 C 開頭的五張牌,即:

C G M S Y 5
C H N T Z 1
C I O U V 2
C J P Q W 3
C K L R X 4

和前面一樣,這些牌和 A 開頭的牌,及 B 開頭的牌,都只有一個圖樣相同。

接著,以 offset + 2 來建立以 D 開頭的五張牌:

D G N U W 4
D H O Q X 5
D I P R Y 1
D J L S Z 2
D K M T V 3

同理可以建立 E 開頭及 F 開頭的五張牌。總共可以產生 n(n-1) +1 張牌。

E G O R Z 3
E H P S V 4
E I L T W 5
E J M U X 1
E K N Q Y 2

F G P T X 2
F H L U Y 3
F I M Q Z 4
F J N R V 5
F K O S W 1

注意如果 n - 1 不是質數,就無法這樣建立,這是因為會出現重覆的情形。例如,n = 5 的情形,如下:

A B C D E
A F G H I
A J K L M
A N O P Q
A R S T U

B F J N R
B G K O S
B H L P T
B I M Q U

C F K P U
C G L Q R
C H M N S
C I J O T

到這裡還沒有任何問題,但要建立 D 開頭的牌時,會發現:

D F L N T --- 和 B F J N R 有兩個重覆圖案

這是因為 n - 1 = 4 不是質數,故 offset 為 4 的因數(即 2 )時就發生問題。

有趣的是,當 n = 8 時(也就是 Spot It 卡牌的情況),共可以有 8 * 7 + 1 = 57 張牌,但實際上 Spot It 只有 55 張牌…

Comments