Optimal strategy of coupon subset collection when each package contains half of the coupons
We consider the well-known problem of coupon subset collection. Optimal solutions are known for only two special cases: (n,k)=(4,2) ( n , k ) = ( 4 , 2 ) and (n,k)=(6,2) ( n , k ) = ( 6 , 2 ) . We prove that a simple strategy is optimal when k=n/2 k = n / 2 for any k. We prove that it is the unique optimal up to permutation of the coupons.
coupon subset collection probabilistic method distributed algorithms experimental design combinatorial problems