今天去面試IC設計軟體工程師被打爆的題目 - 工程師

: (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被洗臉別太難過，因為主管連自己也不知道答案



--