To determine all values of n for which the function f is bijective, we need to analyze the behavior of the function f defined on the set of all possible configurations of n lamps. We will use polynomial theory and properties of finite fields to achieve this.
1. Polynomial Representation:
Consider the configuration of lamps as a polynomial ga(x) in F2[x] modulo xn−1. Each lamp configuration can be represented as a polynomial where the coefficient of xi is 1 if the i-th lamp is on and 0 if it is off.
2. Function Definition:
The function f can be expressed in terms of polynomials as:
f(ga)=x−1xga(x2)−ga(x)(modxn−1)
This function describes the transformation of the lamp configuration after performing the cool procedure.
3. Bijectivity Condition:
For f to be bijective, it must be injective. This means that if f(ga)=0, then ga must be 0. We need to analyze when f(ga)=0 implies ga=0.
4. **Factorization of n**:
Let n=2k⋅m, where m is odd. We will consider two cases: m=1 and m>1.
5. **Case m>1:
- Lemma**: If xn−1∣xga(x2)−ga(x), then:
x−1xga(x2)−ga(x)=0orx−1xn−1(modxn−1)
- Proof of Lemma: Since x−1xn−1 divides x−1xga(x2)−ga(x), we have:
x−1xga(x2)−ga(x)=q(x)⋅x−1xn−1
for some polynomial q(x). This implies that the lemma holds.
- Permutation Analysis: Consider the function h(x)=2x+1(modn). This function is a permutation on the set {0,1,…,n−1} with at least two cycles when m>1. This is because h(m⋅2k−1)=m⋅2k−1, forming a cycle of length 1.
- Cycle Construction: For a cycle of length j containing elements c1,c2,…,cj, construct the polynomial:
ga(x)=i=1∑jxci
This polynomial satisfies xn−1∣xga(x2)−ga(x). Since there are at least two cycles, either one of them is 0, or the sum of them will be 0. Thus, there exists a non-zero polynomial g such that f(g)=0.
6. **Case m=1**:
- When n=2k, we need to show that f is bijective. Consider the function h(x)=2x+1(modn). If ga(x) has a term xm where m=2k−1, then:
xn−1∣xga(x2)−ga(x)
By analyzing the 2-adic valuation υ2, we can show that no such m1 exists, leading to a contradiction. Therefore, ga(x)=x2k−1 gives f(ga)=x−1x2k−1=0.
Conclusion:
- For n=2k, the function f is bijective.
- For n=2k⋅m with m>1, the function f is not bijective.
The final answer is n=2k.