Maths Olympiad Prep

Library / /9 of 17

Combinatorics Difficulty 5.8 AIME, harder Prove it Argentina

A chooses 13 different 3-digit numbers. Then B selects several of these 13 and tries to obtain, by using each selected number once and the operations +,,×+, -, \times, an expression with value strictly between 3 and 4. B wins if he succeeds in doing so; otherwise A wins. Who has a winning strategy?

Solution

Player B has a winning strategy. One way to see this is to divide the 3-digit numbers into 8 groups with the following property: For every two numbers aa, bb from the same group, a>ba > b, one has ab<43\frac{a}{b} < \frac{4}{3}.

G1={100,,133},G2={134,,178},G3={179,,238},G4={239,,318},G5={319,,425},G6={426,,567},G7={568,,757},G8={758,,999}. \begin{align*} G_1 &= \{100, \dots, 133\}, \\ G_2 &= \{134, \dots, 178\}, \\ G_3 &= \{179, \dots, 238\}, \\ G_4 &= \{239, \dots, 318\}, \\ G_5 &= \{319, \dots, 425\}, \\ G_6 &= \{426, \dots, 567\}, \\ G_7 &= \{568, \dots, 757\}, \\ G_8 &= \{758, \dots, 999\}. \end{align*}

For a justification it suffices to note that the ratio of the last number and the first number in a group is less than 43\frac{4}{3}, for instance, 567426<43\frac{567}{426} < \frac{4}{3}.

Since there are 13 different numbers chosen by A and 13>813 > 8, some two of them are in the same group GiG_i, 1<i<81 < i < 8. Let them be aa and bb with a>ba > b; then 1<ab<431 < \frac{a}{b} < \frac{4}{3}. Among the remaining 11 numbers B can find another two with the same property, say cc and dd with 1<cd<431 < \frac{c}{d} < \frac{4}{3}. This is because 11>811 > 8. Finally B can select one more analogous pair e,fe, f, satisfying 1<ef<431 < \frac{e}{f} < \frac{4}{3}, because there are still 9>89 > 8 numbers left. Now adding up gives 3=1+1+1<ab+cd+ef<343=43 = 1+1+1 < \frac{a}{b} + \frac{c}{d} + \frac{e}{f} < 3 \cdot \frac{4}{3} = 4, and the task of B is complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.