: (2)大乐透的规则是 49 个号码当中,取 6 个号码开奖;只要彩券有 3 个以上的号码与
: 开奖结果相同,就是中奖。依此规则请问:
: a. 最少需买几张才可以保证中一张?
: b. 概述如何以程式验证 a.的答案。
其实如果能解出这题的话,可以去MIT当数学教授,
真正的解答还没有人解出来,
有找到一篇文章,
目前找到的上界为163张,解法如下:
参考请google:Betting Wheels, Lotteries & Lotto Designs
We can get an upper bound by noticing the construction that gives:
L(49,6,6,3) <= L(22,6,3,3) + L(27,6,4,3) <= 77+86 = 163.
Proof: Take any p=6-set out of the 49 elements. Either there are at least 3
elements from the 22 elements and we have one of the 77 blocks intersecting
the 6-set in at least three elements or there are at least 4 elements from
the 27 elements and there is a block intersecting the 6-set in at least 3
elements.
Now LD(22,6,3,3;77) is a well-known combinatorial design and you could not
get a better lotto design.
Whereas LD(27,6,4,3;86) was found by a computer program using a simulated
annealing algorithm. It can probably be improved.
But even if LD(27,6,4,3;86) was the best you could do, there may be better
ways to split the 49 elements or better different constructions.
所以原PO被洗脸别太难过,因为主管连自己也不知道答案