作者LPH66 (-858993460)
看板puzzle
標題[中譯] ProjectEuler 376 Nontransitive sets of dice
時間Sun Mar 18 11:52:42 2012
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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.91
1F：→ jurian0101:關於Combinatorics請問有無推薦text? 03/20 08:09
2F：推 utomaya:解掉了 好機車的題目... 只拿到第39名 03/20 19:52
3F：→ utomaya:最多只有18種不同數字 只要求到N=18就好了 其他可用替換的 03/20 19:54
4F：推 utomaya:看了論壇後 果然如所預料的 在於DP狀態數的化簡 03/20 20:42
5F：→ utomaya:我的狀態數還是太多 難怪還是跑很久 03/20 20:44