2018 Putnam B Problems/Problem 1

Problem

Let be the set of vectors defined by Find all such that the set obtained by omitting vector from can be partitioned into two sets of equal size and equal sum.

Solution

We start with There are \( 3 \cdot 101 = 303 \) vectors. Their total sum is If we remove \( v = (a_0, b_0) \), the remaining sum is 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 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 on AoPS using latex. Feel free to make edits this is currently the only solution.

~Pinotation

See Also

Entire Test

First Question

Putnam B Problem 2

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