Maths Olympiad Prep

Library / /349 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Find the answer

Consider nn lamps clockwise numbered from 11 to nn on a circle.

Let ξ\xi to be a configuration where 0n0 \le \ell \le n random lamps are turned on. A cool procedure consists in perform, simultaneously, the following operations: for each one of the \ell lamps which are turned on, we verify the number of the lamp; if ii is turned on, a signal of range ii is sent by this lamp, and it will be received only by the next ii lamps which follow ii, turned on or turned off, also considered clockwise. At the end of the operations we verify, for each lamp, turned on or turned off, how many signals it has received. If it was reached by an even number of signals, it remains on the same state(that is, if it was turned on, it will be turned on; if it was turned off, it will be turned off). Otherwise, it's state will be changed.

The example in attachment, for n=4n=4, ilustrates a configuration where lamps 22 and 44 are initially turned on. Lamp 22 sends signal only for the lamps 33 e 44, while lamp 44 sends signal for lamps 11, 22, 33 e 44. Therefore, we verify that lamps 11 e 22 received only one signal, while lamps 33 e 44 received two signals. Therefore, in the next configuration, lamps 11 e 44 will be turned on, while lamps 22 e 33 will be turned off.

Let Ψ\Psi to be the set of all 2n2^n possible configurations, where 0n0 \le \ell \le n random lamps are turned on. We define a function f:ΨΨf: \Psi \rightarrow \Psi where, if ξ\xi is a configuration of lamps, then f(ξ)f(\xi) is the configurations obtained after we perform the cool procedure described above.

Determine all values of nn for which ff is bijective.

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

Solution

To determine all values of n n for which the function f f is bijective, we need to analyze the behavior of the function f f defined on the set of all possible configurations of n 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) g_a(x) in F2[x] \mathbb{F}_2[x] modulo xn1 x^n - 1 . Each lamp configuration can be represented as a polynomial where the coefficient of xi x^i is 1 if the i i -th lamp is on and 0 if it is off.

2. Function Definition:
The function f f can be expressed in terms of polynomials as:
f(ga)=xga(x2)ga(x)x1(modxn1) f(g_a) = \frac{x g_a(x^2) - g_a(x)}{x-1} \pmod{x^n - 1}
This function describes the transformation of the lamp configuration after performing the cool procedure.

3. Bijectivity Condition:
For f f to be bijective, it must be injective. This means that if f(ga)=0 f(g_a) = 0 , then ga g_a must be 0. We need to analyze when f(ga)=0 f(g_a) = 0 implies ga=0 g_a = 0 .

4. **Factorization of n n **:
Let n=2km n = 2^k \cdot m , where m m is odd. We will consider two cases: m=1 m = 1 and m>1 m > 1 .

5. **Case m>1 m > 1 :
-
Lemma**: If xn1xga(x2)ga(x) x^n - 1 \mid x g_a(x^2) - g_a(x) , then:
xga(x2)ga(x)x1=0orxn1x1(modxn1) \frac{x g_a(x^2) - g_a(x)}{x-1} = 0 \quad \text{or} \quad \frac{x^n - 1}{x-1} \pmod{x^n - 1}
- Proof of Lemma: Since xn1x1 \frac{x^n - 1}{x-1} divides xga(x2)ga(x)x1 \frac{x g_a(x^2) - g_a(x)}{x-1} , we have:
xga(x2)ga(x)x1=q(x)xn1x1 \frac{x g_a(x^2) - g_a(x)}{x-1} = q(x) \cdot \frac{x^n - 1}{x-1}
for some polynomial q(x) q(x) . This implies that the lemma holds.

- Permutation Analysis: Consider the function h(x)=2x+1(modn) h(x) = 2x + 1 \pmod{n} . This function is a permutation on the set {0,1,,n1} \{0, 1, \ldots, n-1\} with at least two cycles when m>1 m > 1 . This is because h(m2k1)=m2k1 h(m \cdot 2^k - 1) = m \cdot 2^k - 1 , forming a cycle of length 1.

- Cycle Construction: For a cycle of length j j containing elements c1,c2,,cj c_1, c_2, \ldots, c_j , construct the polynomial:
ga(x)=i=1jxci g_a(x) = \sum_{i=1}^j x^{c_i}
This polynomial satisfies xn1xga(x2)ga(x) x^n - 1 \mid x g_a(x^2) - g_a(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 g such that f(g)=0 f(g) = 0 .

6. **Case m=1 m = 1 **:
- When n=2k n = 2^k , we need to show that f f is bijective. Consider the function h(x)=2x+1(modn) h(x) = 2x + 1 \pmod{n} . If ga(x) g_a(x) has a term xm x^m where m2k1 m \neq 2^k - 1 , then:
xn1xga(x2)ga(x) x^n - 1 \mid x g_a(x^2) - g_a(x)
By analyzing the 2 2 -adic valuation υ2 \upsilon_2 , we can show that no such m1 m_1 exists, leading to a contradiction. Therefore, ga(x)=x2k1 g_a(x) = x^{2^k - 1} gives f(ga)=x2k1x10 f(g_a) = \frac{x^{2^k} - 1}{x-1} \neq 0 .

Conclusion:
- For n=2k n = 2^k , the function f f is bijective.
- For n=2km n = 2^k \cdot m with m>1 m > 1 , the function f f is not bijective.

The final answer is n=2k \boxed{ n = 2^k } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.