Library / India — Team Selection Test /16 of 77

India — Team Selection Test, 2009

Algebra Difficulty 5.4 AIME, harder Prove it India

If $a_1, a_2, \dots, a_n$ are $n$ non-zero complex numbers, not necessarily distinct, and $k, l$ are distinct positive integers such that $a_1^k, a_2^k, \dots, a_n^k$ and $a_1^l, a_2^l, \dots, a_n^l$ are two identical collections of numbers. Prove that each $a_j$ , $1 \le j \le n$ , is a root of unity.

Solution

The given hypothesis implies that there is a bijection $f : \{1, 2, 3, \dots, n\} \to \{1, 2, 3, \dots, n\}$ such that $f(j) = m$ implies $a_j^k = a_m^l$ . Consider the sequence
$1, f(1), f^{(2)}(1), \dots,$
Since $f$ is a bijection on a finite set, there are positive integers $r, s$ such that $f^{(r)}(1) = f^{(s)}(1)$ , where $0 \le r < s \le n-1$ . (Here $f^{(0)}(1) = 1$ ). Since $f$ is a bijection, we get $f^{(t)}(1) = 1$ , where $t = s - r$ . We have
$a_1^k = a_{f(1)}^l, \quad a_{f(1)}^k = a_{f^{(2)}(1)}^l.$
Thus $a_1^{k^2} = a_{f^{(2)}(1)}^{l^2}$ . Using induction, we get
$a_1^{k^t} = a_{f^{(t)}(1)}^{l^t} = a_1^{l^t}.$
Since $l \neq k$ , it follows that $a_1$ is a root of unity. This holds for any $a_j$ in place of $a_1$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.