HMMT 二月 2013 · 团队赛 · 第 7 题

英文解析

7. [ 30 ] There are n children and n toys such that each child has a strict preference ordering on the toys.
   We want to distribute the toys: say a distribution A dominates a distribution B 6 = A if in A , eachchild receives at least as preferable of an toy as in B . Prove that if some distribution is not dominatedby any other, then at least one child gets his/her favorite toy in that distribution.
   Answer: N/A Suppose we have a distribution A assigning each child C , i = 1 , 2 , . . . , n , toy T ,
   i i
   ′
   such that no child C gets their top preference T 6 = T . Then, pick an arbitrary child C and constructi i 1
   ′ithe sequence of children C , C , C , . . . where i = 1 and C was assigned the favorite toy T ofi i i 1 i
   1 2 3 k +1 ikthe last child C . Eventually, some C = C ; at this point, just pass the toys around this cyclei i ik k 1
   so that each of these children gets their favorite toy. Clearly the resulting distribution dominates theoriginal, so we’re done.