|
|
pdf
1 Introduction/facts you should know
1. (Roots of unity) Let $n≥2$ be an integer and let $ζ=e^{2πi/n}=\cos(2π/n) +i\sin(2π/n)$. Then $1,ζ,ζ^2,\cdots,ζ^{n−1}$ are called the $n$th roots of unity.
2. If $ζ$ is an $n$th root of unity, $ζ$ satisfies $ζ^{n−1}=0$. If $ζ\ne1$, then $1+ζ+ζ^2+⋯+ζ^{n−1}=0$.
3. Let $ζ=e^{2πi/n}$. Then $x^{n−1}=(x−1)(x−ζ)(x−ζ^2)···(x−ζ^{n−1})$.
4. Let $ζ=e^{2πi/n}$. Then $1+x+x^2+⋯+x^{n−1}=(x−ζ)(x−ζ^2)⋯(x−ζ^{n−1})$.
5. $1+ζ^m+ζ^{2m}+⋯+ζ^{(n−1)m}$ is $n$ if $n|m$, and 0 otherwise.
6. (Primitive root of unity) $ζ$ is a primitive $n$th root of unity if it is an $n$th root of unity and $1,ζ,⋯,ζ^{n−1}$ are all distinct.
7. (Primitive root of unity v2) $ζ=e^{2πik/n}$ is a primitive $n$th root of unity iff ${\rm gcd}(k,n)=1$.
8. (Cyclotomic polynomial) The $n$th cyclotomic polynomial, $Φ_n(x)$, is the polynomial whose roots are the $n$th primitive roots of unity.
9. (Cyclotomic polynomial facts) The $n$th cyclotomic polynomial is the unique irreducible polynomial with integer coefficients that is a divisor of $x^{n−1}$ and not a divisor of $x^{k−1}$ for any $k<n$.
The $n$th cyclotomic polynomial is the minimal polynomial for the $n$th primitive roots of unity, i.e. for each primitive $n$th root $ζ$, $Φ_n(x)$, the monic polynomial with integer coefficients of minimum degree with $ζ$ as a root.
10. (Geometry) The roots of unity form the vertices of a regular $n$-gon on the unit circle in the complex plane. Multiplying complex numbers by $ζ=e^{2πi/n}$ corresponds to rotations of $2π/n$ about the origin.
11. (Trigonometry) If $ζ = e^{iθ}$, then $\cos(θ) ={ζ+ζ^{−1}\over2}$ and $\sin(θ) ={ζ−ζ^{−1}\over2i}$.
12. (Roots of unity filter) Let $f(x)=\sum_ia_ix_i$ be a polynomial and $ζ=e^{2πi/n}$. Then $\frac{f(x)+f(\zeta x)+f\left(\zeta^{2} x\right)+\cdots+f\left(\zeta^{n-1} x\right)}{n}=\sum_{n \mid i} a_{i} x^{i}$......(1)
2 Problem for discussion
1. Let $n$ be an odd positive integer, and let $ζ=\cos(2π/n)+i\sin(2π/n)$. Evaluate $\frac{1}{1+1}+\frac{1}{1+\zeta}+\frac{1}{1+\zeta^{2}}+\cdots+\frac{1}{1+\zeta^{n-1}}$.
2. Verify (1).
3. Evaluate $\left(\begin{array}{c}2017 \\ 0\end{array}\right)+\left(\begin{array}{c}2017 \\ 3\end{array}\right)+\cdots+\left(\begin{array}{c}2017 \\ 2016\end{array}\right)$.
4. (USAMO 1976) If $P(x),Q(x),R(x)$ are polynomials such that $P(x^5)+xQ(x^5)+x^2R(x^5)$ is divisible by $1+x+x^2+x^3+x^4$, prove that $P(x)$ is divisible by $x−1$.
5. Let $a,b,c,d$ be positive integers, such that an $a×b$ rectangle can be tiled with a combination of $c×1$ vertical strips, and $1×d$ horizontal strips. Prove that either $a$ is divisible by $c$ or $b$ is divisible by $d$.
6. Show that if a rectangle can be tiled by smaller rectangles each of which has at least one integer side, then the tiled rectangle has at least one integer side.
7. (IMO 1995) Let $p$ be an odd prime. Find the number of $p$-element subsets of $\{1,\cdots,2p\}$ with sum divisible by $p$.
Solution(From excalibir v13_n5 Example 6)
Consider the polynomial $F_a(x) = (1+ax)(1+a^2x)(1+a^3x)⋯(1+a^{2p}x)$. When the right side is expanded, let $c_{n,k}$ count the number of terms of the form $\left(a^{i_{1}} x\right)\left(a^{i_{2}} x\right) \cdots\left(a^{i_{k}} x\right)$, where $i_1, i_2, …, i_k$ are integers such that $1≤ i_1< i_2 <⋯< i_k ≤ 2p$ and $i_1+i_2 +⋯+i_k = n$. Then $F_{a}(x)=1+\sum_{k=1}^{2 p}\left(\sum_{n=1}^{\infty} c_{n, k} a^{n}\right) x^{k}$.
Now, in terms of $c_{n,k}$, the answer to the problem is $C=c_{p, p}+c_{2 p, p}+c_{3 p, p}+\cdots$. To get $C$, note the coefficient of $x^p$ in $F_a(x)$ is $\sum_{n=1}^{\infty} c_{n, p} a^{n}$. By (1), we see $C=\frac{1}{p} \sum_{j=0}^{p-1} \sum_{n=1}^{\infty} c_{n, p} \omega^{n j}$. Now the right side is the coefficient of $x^p$ in $\frac{1}{p} \sum_{j=0}^{p-1} F_{\omega^{j}}(x)$, which equals $\frac{1}{p} \sum_{j=0}^{p-1}\left(1+\omega^{j} x\right)\left(1+\omega^{2 j} x\right) \cdots\left(1+\omega^{2 p j} x\right)$.
For $j=0$, the term is $(1+x)^{2p}$. For $1≤j≤p−1$, using $1+t^{p}=(1+t)(1+\lambda t) \cdots\left(1+\lambda^{p-1} t\right)$ with $λ=ω^j$ and $t=λx$, we see the $j$-th term is $(1+x^p)^2$.Using these, we have $\frac{1}{p} \sum_{j=0}^{p-1} F_{\omega^{j}}(x)=\frac{1}{p}\left[(1+x)^{2 p}+(p-1)\left(1+x^{p}\right)^{2}\right]$. Therefore, the coefficient of $x^p$ is $C=\frac{1}{p}\left[\left(\begin{array}{c}2 p \\ p\end{array}\right)+2(p-1)\right]$.
$B=\{(x, y, z) ∈ M × M × M|x + y + z ≡ 0\pmod n,x, y, z\text{ are of pairwise distinct color}\}$. Prove that $2|A| ≥ |B|$.
3 Additional practice
9. (USAMO 1996) Prove that the average of the numbers $n\sin n◦$ for $n=2,4,6,⋯,180$ is $\cot1◦$.
10. Prove that $\cos(π/7)$ is a root of a cubic polynomial with integer coefficients.
11. (Putnam) Let $P_0=(0,0)$. For $n=1,2,⋯,8$, let $P_n$ be the rotation of point $P_{n−1}$ 45 degrees counter-clockwise around the point $(n,0)$. Determine the coordinates of $P_8$.
12. (USAMO 1977) Find all pairs of positive integers $(m,n)$ such that the polynomial $1+x^n+x^{2n}+⋯+x^{mn}$ is divisible by the polynomial $1+x+x^2+⋯+x^m$.
13. (Leningrad Mathematical Olympiad 1991) A sequence $a_1,a_2,⋯,a_n$ is called $k$-balanced if $a_1+a_{k+1}+⋯=a_2+a_{k+2}+⋯=⋯=a_k+a_{2k}+⋯$. Suppose the sequence
$a_1,a_2,⋯,a_{50}$ is $k$-balanced for $k=3,5,7,11,13,17$. Prove that all the values $a_i$ are zero.
14. (India 2015) Let $ω = e^{2πi/5}$. Show that there are no positive integers $a_1, a_2, a_3, a_4, a_5, a_6$ such that the following is an integer:$\left(1+a_{1} \omega\right)\left(1+a_{2} \omega\right)\left(1+a_{3} \omega\right)\left(1+a_{4} \omega\right)\left(1+a_{5} \omega\right)\left(1+a_{6} \omega\right)$.
15. The set of integers is partitioned into a finite number of arithmetic progressions with each integer in one progression. Prove that some two of these progressions have the same common difference.
16. (Jim Propp) $n$ light bulbs are located at the vertices of a regular $n$-gon. Initially, exactly one bulb is turned on. You can choose any collection of bulbs whose positions are the vertices of a regular polygon, and if they are all on, you can turn them all off, or if they are all off, you can turn them all on. For what $n$ can you eventually get all of the bulbs on?
17. Let $a_k,b_k,c_k$ be integers for $k=1⋯n$, and let $f(x)$ be the number of ordered triples $(A,B,C)$ of subsets (possibly empty) of the set $S=\{1,⋯,n\}$ that partition $S$ for which $$\sum_{i \in S \backslash A} a_{i}+\sum_{i \in S \backslash B} b_{i}+\sum_{i \in S \backslash C} c_{i} \equiv x \pmod 3$$Suppose that $f(0) = f(1) = f(2)$. Prove that there exists $i∈S$ such that $3|a_i+b_i+c_i$.
18. (IMO Shortlist 2007) Find all positive integers $n$ such that you can color the numbers in the set $S=\{1,⋯,n\}$ red or blue such that the set $S×S×S$ contains exactly 2007 monochromatic ordered triples $(x,y,z)$ for which $n|x+y+z$.
19. If $P$ is a nonzero polynomial with integer coefficients, show that there exists a complex number $z$ with $|z|=1$ and $|P(z)|≥1$.
20. Let $P(x)$ be a monic polynomial with integer coefficients such that all its zeros lie on the unit circle. Show that all the zeros of $P(x)$ are roots of unity, i.e., $P(x)|(x^n − 1)^k$ for some $n,k ∈\mathbb N$.
21. Let$A(x)=\sum_{k \geq 0} \frac{x^{3 k}}{(3 k) !}, \ B(x)=\sum_{k \geq 0} \frac{x^{3 k+1}}{(3 k+1) !}, \ C(x)=\sum_{k \geq 0} \frac{x^{3 k+2}}{(3 k+2) !}$, evaluate $A(x)^{3}+B(x)^{3}+C(x)^{3}-3 A(x) B(x) C(x)$. |
|
