PUMaC 2019 · 团队赛 · 第 11 题

PUMaC 2019 — Team Round — Problem 11

The game Prongle is played with a special deck of cards: on each card is a nonempty set of distinct colors. No two cards in the deck contain the exact same set of colors. In this game, a “Prongle” is a set of at least 2 cards such that each color is on an even number of cards in the set. Let k be the maximum possible number of prongles in a set of 2019 cards. Find b log ( k ) c . 2

解析

The game Prongle is played with a special deck of cards: on each card is a nonempty set of distinct colors. No two cards in the deck contain the exact same set of colors. In this game, a “Prongle” is a set of at least 2 cards such that each color is on an even number of cards in the set. Let k be the maximum possible number of prongles in a set of 2019 cards. Find b log ( k ) c . 2 Proposed by: Michael Gintz Answer: 2007 Consider every card as a vector in the mod-2 vector space of c variables, where c is the number of colors used. If the dimension is x , then take a set of x linearly independent cards which will be our basis, and every other subset of non-basis cards will have exactly 1 subset of the basis 2019 − x which gives us a Prongle, so 2 sets will give us a solution. Now note that we cannot have 2019 cards with dimension 10, so we must have dimension at least 11, which we can do 2008 by making sure that we have 11 cards with one color each. Then there are 2 − 1 solutions, where the -1 comes from the empty set.