Re: [其他] 鴿籠
※ 引述《pop10353 (女乃 豆頁 單戈 示申)》之銘言：
: 現在有一堆長方形的紙
: 其長寬皆為正整數並介於1~90之間
: 請問要拿至少幾張可以保證其中兩張
: 一張可以蓋住另一張？
若你的"蓋住"指的是邊的方向須平行或垂直
令長a寬b的矩形記為(a,b),a≦b,則
(1,1),(1,2),..,(1,89),(1,90),(2,90),..,(89,90),(90,90)
(2,2),(2,3),..,(2,88),(2,89),(3,89),..,(88,89),(89,89)
......
(44,44),(44,45),(44,46),(44,47),(45,47),(46,47),(47,47)
(45,45),(45,46),(46,46)
以上45列包含所有形狀的矩形,且每一列左項均可包含在右項
故若取46張必可有一張蓋住另一張
而45張不行,例如(1,90),(2,89),..,(44,47),(45,46)
故最少為46張
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.9.66
※ 編輯: XII 來自: 111.248.9.66 (07/22 15:48)
→
07/22 15:53, , 1F
07/22 15:53, 1F
討論串 (同標題文章)