376. Nontransitive sets of dice
http://projecteuler.net/problem=376
考慮下列三個非正規點數的骰子:
骰子Ａ: 1 4 4 4 4 4
骰子Ｂ: 2 2 2 5 5 5
骰子Ｃ: 3 3 3 3 3 6
兩人玩一個遊戲，各自依序選擇一個骰子丟，點數大者勝。
若玩家一選骰子Ａ，玩家二選骰子Ｂ，則玩家二獲勝的機率是 7/12 > 1/2；
若玩家一選骰子Ｂ，玩家二選骰子Ｃ，則玩家二獲勝的機率是 7/12 > 1/2；
若玩家一選骰子Ｃ，玩家二選骰子Ａ，則玩家二獲勝的機率是 25/36 > 1/2。
因此無論玩家一選哪一個，玩家二都能選擇一個超過一半勝率的骰子。
一組骰子有如此特性者稱為「無遞移性的骰子組」。
我們想要確定有多少組無遞移性的骰子組。假設以下條件：
* 骰子固定為三個六面骰，其點數可由１到Ｎ。
* 六面點數組合相同的骰子視為相同，無論其點數分佈是在哪個面上。
* 同樣點數可以出現在不同的骰子上；若兩人骰出同點則無人獲勝。
* 骰子組 {A,B,C} 和 {B,C,A} 和 {C,A,B} 視為相同的組合。
對 N = 7 一共有 9780 組。
問 N = 30 時有多少組？
--
另一組「無遞移性的骰子組」可參考 #1A_gMud3 及 #1A_sTgTZ
那裡的三顆骰子是
: 第一顆：無灌鉛普通骰子，六面點數：1,2,3,4,5,6
: 第二顆，六面點數分別為：0,0,0,0,10,10
: 第三顆，六面點數分別為：-1,-1,6,6,6,6
稍微改動一下就是 N = 9 的其中一種情形了:
{{3,4,5,6,7,8},{2,2,2,2,9,9},{1,1,8,8,8,8}}
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
All Comments