Maths Olympiad Prep

Library / /394 of 520

Combinatorics Difficulty 5.7 AIME, harder Prove it

Three. (This question is worth 35 points) Divide the set M={1,2,,89}M=\{1, 2, \cdots, 89\} into two subsets AA and BB. If AB=,AB=MA \cap B=\varnothing, A \cup B=M, then it is called a partition of set MM. Prove that for any partition of set MM into two subsets AA and BB, the equation x1+x2++x9=x10x_{1}+x_{2}+\cdots+x_{9}=x_{10} must have a solution within one of the subsets.

Solution

Three, prove using the proof by contradiction.
Suppose the set is divided into two subsets AA and BB, in both AA and BB, the equation x1+x2++x9=x10x_{1} + x_{2} + \cdots + x_{9} = x_{10} has no solution.
If 1A1 \in A, to make the equation unsolvable, since
x1+x2++x99 x_{1} + x_{2} + \cdots + x_{9} \geqslant 9 \text {, }

then 9B9 \in B. Otherwise, if 9A9 \in A, then x1=x2==x9=1,x10=9x_{1} = x_{2} = \cdots = x_{9} = 1, x_{10} = 9 is a solution to the equation.

Therefore, 81A81 \in A, otherwise, if 81B81 \in B, by taking x1=x3==x9=9B,x10=81Bx_{1} = x_{3} = \cdots = x_{9} = 9 \in B, x_{10} = 81 \in B, the equation has a solution.

At this point, if 10A10 \in A, then by 81=10×8+181 = 10 \times 8 + 1, taking x1=x2==x8=10,x9=1,x10=81x_{1} = x_{2} = \cdots = x_{8} = 10, x_{9} = 1, x_{10} = 81, since 10A,1A10 \in A, 1 \in A, 81A81 \in A, the equation has a solution in AA, leading to a contradiction.

If 10B10 \in B, since 89=10×8+989 = 10 \times 8 + 9. Then taking x1=x2==x8=10B,x9=9Bx_{1} = x_{2} = \cdots = x_{8} = 10 \in B, x_{9} = 9 \in B, 89 must be in AA. At this time, by
89=1×8+81 89 = 1 \times 8 + 81 \text {, }

taking x1=x3==x8=1A,x9=81A,x10=89Ax_{1} = x_{3} = \cdots = x_{8} = 1 \in A, x_{9} = 81 \in A, x_{10} = 89 \in A. The equation has a solution in AA, leading to a contradiction.

Thus, for any partition of M={1,2,,89}M = \{1, 2, \cdots, 89\} into AA and BB, the equation x1+x2++x9=x10x_{1} + x_{2} + \cdots + x_{9} = x_{10} has a solution in one of the subsets.

Note: M={1,2,,89}M = \{1, 2, \cdots, 89\} is the smallest set such that the equation x1+x2++x9=x10x_{1} + x_{2} + \cdots + x_{9} = x_{10} has a solution in any partition of M={1,2,,n}M = \{1, 2, \cdots, n\}.

If M={1,2,,88}M' = \{1, 2, \cdots, 88\}, then a partition can be constructed such that the equation has no solution in both subsets AA and BB, for this, we can set
A={1,2,3,,8,81,82,,89},B={9,10,11,,79,80}. \begin{array}{l} A = \{1, 2, 3, \cdots, 8, 81, 82, \cdots, 89\}, \\ B = \{9, 10, 11, \cdots, 79, 80\} . \end{array}
(Provided by Tian Qiao Wang Lianxiao)

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.