, 2020

Number theory Difficulty 6.0 AIME, harder Prove it Romania

A nonempty, finite set $A$ of positive integers is called quadratic if the sum of the elements of $A$ equals the square of the number of elements of $A$ .
For example $A = \{1, 3, 4, 8\}$ is quadratic since $1 + 3 + 4 + 8 = 4^2$ .

a) Give an example of a quadratic set with 20 elements.

b) Prove that every quadratic set contains at least one odd integer.

c) Prove that the intersection of two quadratic sets with the same number of elements is nonempty.

Solution

a) An example is: $A = \{1, 2, 3, \ldots, 19\} \cup \{210\}$ .
The sum of elements is $1 + 2 + \ldots + 19 + 210 = \frac{19 \cdot 20}{2} + 210 = 400 = 20^2$ .

b) We argue by contradiction. Suppose $A$ is a quadratic set containing $n$ even positive integers. The sum of the elements of $A$ is at least $2 + 4 + \ldots + 2n = n(n+1) > n^2$ which is a contradiction.

c) We prove again by contradiction. Assume there exist two disjoint quadratic sets, $A$ and $B$ , each having $n$ elements. The total sum of the elements from the two sets is $2n^2$ . On the other side the smallest $2n$ distinct positive integers add up to $1 + 2 + \ldots + 2n = n(2n+1) > 2n^2$ , therefore a contradiction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.