Maths Olympiad Prep

Track / Stage 6 / 296 of 400 #1296 of 1964

Problem 1296

National olympiad, first round
Combinatorics Difficulty 6.6 Find the answer

Compute the number of monic polynomials q(x)q(x) with integer coefficients of degree 1212 such that there exists an integer polynomial p(x)p(x) satisfying q(x)p(x)=q(x2).q(x)p(x) = q(x^2).

[i]Proposed by Yang Liu[/i]

A number or a short expression. Spacing and $ signs are ignored.

Official solution

1. Understanding the Problem:
We need to find the number of monic polynomials q(x) q(x) with integer coefficients of degree 12 such that there exists an integer polynomial p(x) p(x) satisfying q(x)p(x)=q(x2) q(x)p(x) = q(x^2) .

2. **Analyzing the Condition q(x)p(x)=q(x2) q(x)p(x) = q(x^2) :**
- For q(x)p(x)=q(x2) q(x)p(x) = q(x^2) to hold, the roots of q(x) q(x) must be such that if α \alpha is a root of q(x) q(x) , then α2 \alpha^2 must also be a root of q(x) q(x) .
- This implies that the roots of q(x) q(x) must be closed under squaring.

3. Roots of Unity:
- The roots of q(x) q(x) must be roots of unity because roots of unity are closed under squaring.
- Specifically, the roots of q(x) q(x) must be among the 12th roots of unity, since q(x) q(x) is a polynomial of degree 12.

4. Cyclotomic Polynomials:
- The 12th roots of unity are the roots of the polynomial x121 x^{12} - 1 .
- The polynomial x121 x^{12} - 1 can be factored into cyclotomic polynomials:
x121=(x61)(x6+1)=(x21)(x2+1)(x4x2+1)(x4+x2+1) x^{12} - 1 = (x^6 - 1)(x^6 + 1) = (x^2 - 1)(x^2 + 1)(x^4 - x^2 + 1)(x^4 + x^2 + 1)
- The cyclotomic polynomials involved are Φ1(x),Φ2(x),Φ3(x),Φ4(x),Φ6(x), \Phi_1(x), \Phi_2(x), \Phi_3(x), \Phi_4(x), \Phi_6(x), and Φ12(x) \Phi_{12}(x) .

5. **Forming q(x) q(x) :**
- q(x) q(x) must be a product of these cyclotomic polynomials.
- The degree of q(x) q(x) must be 12, so we need to select cyclotomic polynomials whose degrees sum to 12.

6. Possible Combinations:
- The degrees of the cyclotomic polynomials are:
deg(Φ1)=1,deg(Φ2)=1,deg(Φ3)=2,deg(Φ4)=2,deg(Φ6)=2,deg(Φ12)=4 \deg(\Phi_1) = 1, \quad \deg(\Phi_2) = 1, \quad \deg(\Phi_3) = 2, \quad \deg(\Phi_4) = 2, \quad \deg(\Phi_6) = 2, \quad \deg(\Phi_{12}) = 4
- We need to find all combinations of these polynomials that sum to 12.

7. Counting the Combinations:
- We can use the stars and bars method to count the number of ways to distribute the degree 12 among the cyclotomic polynomials.
- The possible combinations are:
- Φ12(x) \Phi_{12}(x) (degree 4) and Φ6(x) \Phi_6(x) (degree 2) repeated 4 times.
- Other combinations can be formed similarly by ensuring the total degree sums to 12.

8. Verification:
- We need to ensure that each combination is unique and valid.
- After verifying, we find that there are 119 valid combinations.

The final answer is 119 \boxed{ 119 } .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.