PUMaC 2014 · 组合（A 组） · 第 8 题

PUMaC 2014 — Combinatorics (Division A) — Problem 8

[ 8 ] There are 60 friends who want to visit each others home during summer vacation. Everyday, they decide to either stay home or vist the home of everyone who stayed home that day. Find the minimum number of days required for everyone to have visted their friends’ homes. 1

解析

[ 8 ] There are 60 friends who want to visit each other’s home during summer vacation. Everyday, they decide to either stay home or vist the home of everyone who stayed home that day. Find the minimum number of days required for everyone to have visted their friends’ homes. Solution: ( ) 8 In 8 days, let each student go out on 4 days. Since there are = 70 ways to do so, we can let 4 every student go out on distinct combination of 4 days. Thus we see that for any two students A and B , there is at least one day for which A goes out to vist while B stays home and vice versa. Hence everyone will have visited all others by 8 days. 5 For 7 days, by Sperner’s Theorem, we see that the maximum number of subsets of days such ( ) 7 that there are no two subsets with one contained in the other, is = 35. Hence 7 days is 3 impossible. Since 60 > 35, this can also be proven by grouping the combination of days into sets like { (1 , 2 , 3) , (1 , 2 , 3 , 4) } where no two students can have their days going out from the same set, and applying pigeonhole principle after that. 6