PUMaC 2016 · 个人决赛（B 组） · 第 2 题

PUMaC 2016 — Individual Finals (Division B) — Problem 2

There are 12 candies on the table, four of which are rare candies. Chad has a friend who can tell rare candies apart from regular candies, but Chad can’t. Chad’s friend is allowed to take four candies from the table, but may not take any rare candies. Can his friend always take four candies in such a way that Chad will then be able to identify the four rare candies? If so, describe a strategy. If not, prove that it cannot be done. Note that Chad does not know anything about how the candies were selected (e.g. the order in which they were selected). However, Chad and his friend may communicate beforehand.

解析

Arrange the 12 candies in a circle. We pair up the four rare candies with non-rare candies in the following manner: choose a rare candy that doesn’t have a rare candy immediately to its left, pair it up with the candy immediately to its left, and remove them from the circle. Note that the ordering of the choice of rare candies doesn’t matter: each rare candy is identified with the candy originally 2 n − 1 candies to the left such that the 2 n − 2 candies in between them have half rare, and n is minimal. Chad’s friend chooses the non-rare candy in each pair. Chad can identify the four rare candies by identifying the four pairings from the chosen candies: he identifies each chosen candy with the candy 2 n − 1 candies to the right such that the 2 n − 2 candies in between have half chosen and half unchosen, with n minimal. Problem written by Zhuo Qun Song. ⌊ ⌋ c cn +