2005 AMC 10B Problem 25

This is a "greatest possible" question, so show two things: $62$ numbers can be chosen, and more than $62$ cannot.

Part 1: which numbers can cause trouble?

1. A number $k$ is only a problem if its partner $125 - k$ is also between $1$ and $100$. For $k = 24$ the partner would be $101$, which is too big. So $1, 2, \ldots, 24$ never cause trouble.
2. The numbers $25$ through $100$ ($76$ numbers) pair up so each pair adds to $125$:
$$25 + 100,\quad 26 + 99,\quad 27 + 98,\quad \ldots,\quad 62 + 63.$$
That is $76 \div 2 = 38$ pairs, and no number is in two pairs.

Part 2: more than $62$ is impossible.

1. $B$ cannot hold both numbers of any pair, since they add to $125$. So from $25$ to $100$, $B$ has at most $38$ numbers, one per pair.
2. Adding the $24$ safe numbers, $B$ has at most $24 + 38 = 62$ numbers.

Part 3: $62$ is possible.

1. Take $B = \{1, 2, 3, \ldots, 62\}$. The two biggest numbers in it add to $62 + 61 = 123$, which is less than $125$. So no two numbers in $B$ add to $125$.

Sixty-two is possible and sixty-three is not, so the greatest size is $62$.

The answer is $\boxed{\textbf{(C)}\ 62}$.

When a rule says "no two chosen numbers may add to a certain total," pair each number with the partner it would clash with. You can take at most one from each pair, and numbers with no partner are free. For a "greatest" question, you also need an example that reaches the limit; here the smallest $62$ numbers do it.

Build the set greedily from the bottom: add $1, 2, 3, \ldots$ one at a time as long as no two chosen numbers add to $125$. The first clash is $62 + 63 = 125$, so you can go up to $62$. The pairing argument above is what proves you cannot do better another way.