Maths Olympiad Prep

Library / /11 of 20

Combinatorics Difficulty 6.5 National olympiad Prove it North Macedonia

Let nn be a positive integer and CC be nonnegative real number. Find the number of the sequences of real numbers 1,x2,,xn,11, x_2, \dots, x_n, 1, such that the absolute value of the difference of every two consecutive terms is equal to CC.

Solution

Let us suppose that the sequence 1,x2,,xn,11, x_2, \dots, x_n, 1 satisfy the condition of the problem. Then
1x2=x2x3==xn1=C.(1) |1 - x_2| = |x_2 - x_3| = \dots = |x_n - 1| = C. \quad (1)
Also
xn1=(xnxn1)+(xn1xn2)++(x21)(2) x_n - 1 = (x_n - x_{n-1}) + (x_{n-1} - x_{n-2}) + \dots + (x_2 - 1) \quad (2)
where the number of pairs of brackets of the right-hand side is n1n-1. We consider two cases: nn is odd and nn is even number.

Case 1. nn is odd, i.e. n1n-1 is even number.
Then the equality (2) get the form Δ1C=Δ2CΔ3CΔnCn1\Delta_1 C = \underbrace{\Delta_2 C \Delta_3 C \dots \Delta_n C}_{n-1}, where Δi{,+}\Delta_i \in \{-, +\}, 1in1 \le i \le n. The choice of Δi{,+}\Delta_i \in \{-, +\}, 2in2 \le i \le n determine a sequence 1,x2,,xn,11, x_2, \dots, x_n, 1, satisfying the sequence (1). Let we

note that the sum of the right-hand side of the equality Δ1C=Δ2CΔ3CΔnCn1\Delta_1 C = \underbrace{\Delta_2 C \Delta_3 C \dots \Delta_n C}_{n-1} (for one choice of Δi{,+},2in\Delta_i \in \{-, +\}, 2 \le i \le n) is even number of times CC, and the left-hand side is ±C\pm C, i.e. odd number times CC. Therefore, the right-hand side is equal to ±2kC\pm 2kC, for some kNk \in \mathbb{N}, and the left-hand side is equal to ±C\pm C. The last is possible only if C=0C=0 and then we obtain the sequence 1=x2==xn1=x_2=\dots=x_n, i.e. there exists only one sequence with the desired property.

Case 2. nn is even, i.e. n1n-1 is odd number.
If C=0C=0, then 1=x2==xn1=x_2=\dots=x_n. Let C>0C>0. Then again from the equality (2) we obtain
Δ1C=Δ2CΔ3CΔnCn1. \Delta_1 C = \underbrace{\Delta_2 C \Delta_3 C \dots \Delta_n C}_{n-1}.
Hence, the problem can be transformed to find the number of choices of Δi{,+},2in\Delta_i \in \{-, +\}, 2 \le i \le n such that Δ1C=Δ2CΔ3CΔnCn1\Delta_1 C = \underbrace{\Delta_2 C \Delta_3 C \dots \Delta_n C}_{n-1}. If on the left-hand side of the equality we have +C+C, then it must, on the right-hand side of the equality, the difference between the number of the positive and the number of the negative constants to be exactly 1, i.e. +C+C must appear n22+1=n2\frac{n-2}{2}+1=\frac{n}{2} times, and C-C appears exactly n22\frac{n-2}{2} ways. Such type of choices can be made on (n1n/2)=(n1(n2)/2)\binom{n-1}{n/2} = \binom{n-1}{(n-2)/2} ways (for a sequence with length n1n-1 we choose n/2n/2 positions where we will put +C+C, and on the rest we will put C-C). On the exact same number of ways can be written the sum of the right-hand side is the sum of the left-hand side is C-C. So, the total number of such representations is 2(n1n/2)2\binom{n-1}{n/2}.
Finally, if with r=r(n,C)r = r(n, C) we denote the number of the sequences satisfying the condition of the problem, then
r={1,C=00,n is odd and C>0.2(n1n/2),n is even and C>0. r = \begin{cases} 1, & C=0 \\ 0, & n \text{ is odd and } C > 0. \\ 2\binom{n-1}{n/2}, & n \text{ is even and } C > 0. \end{cases}

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.