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.

Which numbers can be part of a pair summing to $125$? A number $k$ needs a partner $125 - k$ that also lies in $1$ to $100$, which requires $25 \le k \le 100$. So the numbers $1$ through $24$ are completely safe: all $24$ of them can go into $B$.

The numbers $25$ through $100$ ($76$ numbers) split into the $38$ disjoint pairs
$$\{25, 100\},\ \{26, 99\},\ \ldots,\ \{62, 63\},$$
each summing to $125$. $B$ may contain at most one number from each pair, so it has at most $38$ of these numbers.

Upper bound: $|B| \le 24 + 38 = 62$.

This is achievable: take $B = \{1, 2, \ldots, 62\}$. Its two largest elements sum to $62 + 61 = 123 < 125$, so no two elements reach $125$.

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