Competition problem — Algebra — Maths Olympiad Prep

Library / /6 of 17

Algebra Difficulty 5.4 AIME, harder Prove it Mongolia

Let the sum of the elements of a set $X$ be denoted by $S(X)$ . How many ways can we divide the numbers $2^1, 2^2, \dots, 2^{10}$ into sets $A$ and $B$ such that the equation
$x^2 - S(A)x + S(B) = 0$
has a positive integer solution? (The sets $A$ or $B$ may be empty.)
*To divide the numbers $c_1, c_2, \dots, c_n$ into sets $A$ and $B$ means that $A$ and $B$ are disjoint sets and each of the numbers $c_1, c_2, \dots, c_n$ must belong to exactly one of them.*

Solution

Answer: 2.
The numbers $2^1, 2^2, \dots, 2^{10}$ can be used to produce only and all even numbers from $0$ to $2046$ . Thus, let $S(A) = 2n$ for some integer $0 \le n \le 1023$ . Then $S(B) = 2^1+2^2+\dots+2^{10}-S(A) = 2046-2n$ . Moreover $x^2-S(A)x+S(B) = x^2-2nx+(2046-2n) = 0$ implies
$23 \cdot 89 = 2047 = (n+1)^2 - (x-n)^2 = (2n+1-x)(x+1).$
The only positive integer solutions are $x = 22$ and $x = 88$ with $n = 55$ . Hence, there are exactly two ways to divide the numbers.

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.