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

※ 引述《grassboy2 (小胖子．吳草兒)》之銘言：
: (手殘按成回信，原 po sorry 0rz)
: 獻醜了XD
: 來個確定會中，但不保證是最少張的思考模式
: 把 1~49 個號碼分成25組：
: 分別是 {1,2} {3,4} {5,6} .... {45,46} {47,48} {49,1}
: 然後我們把這 25 組當中，"任取三組"的所有可能都買下來…
: 也就是 C(25,3) = 25 * 24 * 23 / 6 = 2300
: 如此，我認為這樣一定會中獎

這想法是對的, 不過本質上離 bound 差很遠.

你用的技巧是 grouping.
把兩個號碼弄成一組, 然後把 C(49,6) 轉成 C(49/2, 6/2) = C(25,3)..

舉個簡單的例子給你,
6 個號碼, 取四個, 我要買多少張, 才能保證會中兩個號碼?

Based on you grouping algorithm..
{1,2}, {3,4}, {5,6}.. -> C(3,2) = 3.

但實際上你只需要買 1 張就夠了.

這題目是 Graph 上面的 Vertex Covering,
有興趣的人可以去看這篇

Z. Furedi, G. J. Szekely, and Z. Zubor:
On the lottery problem,
J. Combinatorial Designs 4 (1996), 5-10.

http://www.math.uiuc.edu/~z-furedi/publ.html

不過用程式去解應該會很有趣.


--
一簫一劍平生意

負盡狂名十五年


--