Maths Olympiad Prep

Library / /128 of 144

Combinatorics Difficulty 8.8 Shortlist Find the answer

Let n>1 n > 1 be an integer. Find all sequences a1,a2,an2\plusn a_1, a_2, \ldots a_{n^2 \plus{} n} satisfying the following conditions:
 (a) ai{0,1} for all 1in2\plusn; \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 \plus{} n;

 (b) ai\plus1\plusai\plus2\plus\plusai\plusn<ai\plusn\plus1\plusai\plusn\plus2\plus\plusai\plus2n for all 0in2\minusn. \text{ (b) } a_{i \plus{} 1} \plus{} a_{i \plus{} 2} \plus{} \ldots \plus{} a_{i \plus{} n} < a_{i \plus{} n \plus{} 1} \plus{} a_{i \plus{} n \plus{} 2} \plus{} \ldots \plus{} a_{i \plus{} 2n} \text{ for all } 0 \leq i \leq n^2 \minus{} n.
[i]Author: Dusan Dukic, Serbia[/i]

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

Solution

To construct sequences that satisfy these conditions, let's explore the structure of sequences in terms of segments or blocks of length n n :

For a sequence a1,a2,,an2+n a_1, a_2, \ldots, a_{n^2 + n} , consider representing it as composed of blocks of length n n :
- Sequence indices are split such that each au+vn a_{u+vn} corresponds to a position in the grid where 1un 1 \le u \le n and 0vn 0 \le v \le n .

Given these indices, analyze the sequence condition (b) (b) , where parts of the sequence need to obey the inequality regarding the sum of segments of length n n :
- Consider two consecutive segments of the sequence from elements i+1 i+1 to i+2n i+2n . The sum of the first n n elements in a segment (i.e., ai+1++ai+n a_{i+1} + \ldots + a_{i+n} ) must be less than the sum of the next n n elements (i.e., ai+n+1++ai+2n a_{i+n+1} + \ldots + a_{i+2n} ).

### Construction of Sequence

One valid sequence configuration is as follows:
1. For each u+vn u+v \leq n , set au+vn=0 a_{u+vn} = 0 ,
2. For each u+vn+1 u+v \geq n+1 , set au+vn=1 a_{u+vn} = 1 .

These result in arranging the sequence into blocks:
- The first block contains only zeros: (0,0,,0) (0, 0, \ldots, 0) of length n n .
- The second block shifts one zero to the left, and so on, increasing the number of 1's till the block is entirely filled with 1's at the last possible block, resulting in:
- (0,,0,1),(0,,0,1,1),,(1,1,,1) (0, \ldots, 0, 1), (0, \ldots, 0, 1, 1), \ldots, (1, 1, \ldots, 1) .

The sequence's layout can be seen as:
(00)n(00 1)n1(00 1 1)n2(00 11)nv(0 11)v(0 11)n1(11)n. \underbrace{(0 \cdots 0)}_{n} \underbrace{(0 \cdots 0 \ 1)}_{n-1} \underbrace{(0 \cdots 0 \ 1 \ 1)}_{n-2} \cdots \underbrace{(0 \cdots 0 \ 1 \cdots 1)}_{n-v} \underbrace{(0 \ 1 \cdots 1)}_{v} \cdots \underbrace{(0 \ 1 \cdots 1)}_{n-1} \underbrace{(1 \cdots 1)}_{n}.

This block arrangement ensures the given inequality condition (b) is satisfied for all valid indices, maintaining the property that the sum of any segment of zeros followed by fewer number of ones will always be less than the adjacent segment with more ones, as implied by the inequality specified.

### Conclusion

Thus, the sequences satisfying the given conditions can be explicitly formulated as follows based on the above configuration:
au+vn={0,u+vn,1,u+vn+1 for all 1un and 0vn. a_{u+vn} = \begin{cases} 0, & u+v \le n, \\ 1, & u+v \ge n+1 \end{cases} \text{ for all } 1 \le u \le n \text{ and } 0 \le v \le n.

This completes the construction and solution for the given problem.
Sequence as described is valid for given conditions. \boxed{\text{Sequence as described is valid for given conditions.}}

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