Re: [其他] 鴿籠
※ 引述《pop10353 (女乃 豆頁 單戈 示申)》之銘言：
: 現在有一堆長方形的紙
: 其長寬皆為正整數並介於1~90之間
: 請問要拿至少幾張可以保證其中兩張
: 一張可以蓋住另一張？
假設(長,寬)分別為(a,b)與(c,d)
(a≧b且c≧d)
若a=c或b=d則必有一張可以蓋住另一張
因此不能取到有兩張的長一樣或寬一樣
不妨設a>c,則此時b<d
最多可取45張時不互蓋
(例如:(90,1),(89,2),...(46,45))
因此應該取46張就可以互蓋...
(還沒時間細想, 可能有誤)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.141.67
討論串 (同標題文章)