2018 Putnam B Problems/Problem 1

Problem

Let $\mathcal{P}$ be the set of vectors defined by $\mathcal{P} = \left\{\begin{pmatrix} a \\ b \end{pmatrix} \, \middle\vert \, 0 \le a \le 2, 0 \le b \le 100, \, \text{and} \, a, b \in \mathbb{Z}\right\}.$ Find all $\mathbf{v} \in \mathcal{P}$ such that the set $\mathcal{P}\setminus\{\mathbf{v}\}$ obtained by omitting vector $\mathbf{v}$ from $\mathcal{P}$ can be partitioned into two sets of equal size and equal sum.

Solution

We start with $P = \{(a, b) : a \in \{0, 1, 2\}, \ b \in \{0, \dots, 100\}\}.$ There are $ 3 \cdot 101 = 303 $ vectors. Their total sum is $S = (S_x, S_y) = ((0 + 1 + 2) \cdot 101, \; 3 \cdot \sum_{b=0}^{100} b) = (303, 15150).$ If we remove $ v = (a_0, b_0) $, the remaining sum is $S' = (303 - a_0, \; 15150 - b_0).$ For the remaining set to be partitioned into two subsets of equal sum, $ S' $ must be twice some integer vector. Hence both coordinates of $ S' $ are even. That forces $ 303 - a_0 $ even $ \implies a_0 = 1 $, and $ 15150 - b_0 $ even $ \implies b_0 $ even. So only vectors $ (1, b) $ with $ b $ even are possible.

To show these actually work, consider the symmetry map $f(a, b) = (2 - a, \; 100 - b).$ Each pair $ \{(a, b), f(a, b)\} $ sums to $ (2, 100) $. This partitions $ P $ into 151 such pairs, including the special fixed point $ (1, 50) $. This gives us two cases.

Case 1: If we remove $ (1, 50) $, then exactly 150 intact pairs remain. Choose one vector of each pair for set $ A $ and the other for set $ B $. Each pair contributes equally, so $ |A| = |B| = 150 $ and sums are equal. Done.

Case 2: If we remove $ (1, t) $ with $ t $ even and $ t \neq 50 $, then the pair $ \{(1, t), f(1, t)\} $ is broken, leaving its partner $ f(1, t) = (1, 100 - t) $. All other 150 pairs are intact. Split those intact pairs evenly between two sets as before. Then place $ (1, 100 - t) $ in one set and the fixed point $ (1, 50) $ in the other. Both have $ x $-coordinate 1, and since $ t $ is even the total $ y $-sum balances correctly. This yields two equal-size subsets with equal sums.

Thus precisely the vectors $ (1, b) $ with $ b $ even satisfy the condition.

Therefore, our answer is $ v = (1, b) $ where $ b = 0, 2, 4, \dots, 100 $

Please note this is my first time using latex.

~Pinotation

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.

Page

Toolbox

Search

2018 Putnam B Problems/Problem 1

Problem

Solution