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 likessome 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 choosesthese pizzas such that no matter which toppings Arno likes, she can then make him a sixth pizza withall the toppings he likes and no others. What are all possible combinations of the five initial pizzas forthis 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 fivepizzas, each with some subset of the five toppings. For each pizza, Arno states (with either a “yes” ora “no”) if the pizza has any toppings that he does not like. Purineqa chooses these pizzas such that nomatter which toppings Arno likes, she has enough information to make him a sixth pizza with all thetoppings he likes and no others. What are all possible combinations of the five initial pizzas for thisto be the case?
Answer: see below We claim the only way for Purineqa to deduce Arno’s preferences is for eachpizza to contain exactly one topping, with no topping be repeated. It is obvious that he can deducethe toppings in this case.
We now claim that this is not possible with any other combination. Suppose that Arno tells Purineqathat he does not like any of the five pizzas. Then, Purineqa should be able to rule out at least one ofthe 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 allfive toppings T , so we’re done.
Team B