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

HMMT February 2013 — Team Round — Problem 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 , each child receives at least as preferable of an toy as in B . Prove that if some distribution is not dominated by any other, then at least one child gets his/her favorite toy in that distri bution.

解析

[ 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 , each child receives at least as preferable of an toy as in B . Prove that if some distribution is not dominated by 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 construct i i 1 i ′ the sequence of children C , C , C , . . . where i = 1 and C was assigned the favorite toy T of i i i 1 i 1 2 3 k +1 i k the last child C . Eventually, some C = C ; at this point, just pass the toys around this cycle i i i k k 1 so that each of these children gets their favorite toy. Clearly the resulting distribution dominates the original, so we’re done.