作者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