HMMT 二月 2012 · TEAM2 赛 · 第 10 题

HMMT February 2012 — TEAM2 Round — Problem 10

[ 20 ] Purineqa is making a pizza for Arno. There are five toppings that she can put on the pizza: mushrooms, olives, green peppers, cheese, and pepperoni. However, Arno is very picky and only likes some subset of the five toppings. Purineqa makes 5 pizzas, each with some subset of the five toppings, then for each of those Arno tells her if that pizza has any toppings he does not like. Purineqa chooses these pizzas such that no matter which toppings Arno likes, she can then make him a sixth pizza with all the toppings he likes and no others. What are all possible combinations of the five initial pizzas for this to be the case?

解析

[ 20 ] Purineqa is making a pizza for Arno. There are five toppings that she can put on the pizza. However, Arno is very picky and only likes some subset of the five toppings. Purineqa makes five pizzas, each with some subset of the five toppings. For each pizza, Arno states (with either a “yes” or a “no”) if the pizza has any toppings that he does not like. Purineqa chooses these pizzas such that no matter which toppings Arno likes, she has enough information to make him a sixth pizza with all the toppings he likes and no others. What are all possible combinations of the five initial pizzas for this to be the case? Answer: see below We claim the only way for Purineqa to deduce Arno’s preferences is for each pizza to contain exactly one topping, with no topping be repeated. It is obvious that he can deduce the toppings in this case. We now claim that this is not possible with any other combination. Suppose that Arno tells Purineqa that he does not like any of the five pizzas. Then, Purineqa should be able to rule out at least one of the possibilities that Arno likes none of the toppings and that Arno likes exactly one of the toppings T . It is clear that this is possible if and only if there is a pizza with only T on it. This is true for all five toppings T , so we’re done. Team B