Maths Olympiad Prep

Library / /64 of 86

Combinatorics Difficulty 6.7 National olympiad Prove it Estonia

Every term of the sequence a1,a2,a3,a_1, a_2, a_3, \dots is either 00 or 11. It is known that both 00 and 11 occur at least 10101010 times among every 20212021 consecutive terms of the sequence. May one be sure that the sequence is periodic from some place on, i.e., there exist positive integers nn and pp such that an+i=an+i+pa_{n+i} = a_{n+i+p} for every natural number ii?

Solution

Consider the tuples 1111011 times0001010 times\underbrace{11\dots1}_{1011 \text{ times}} \underbrace{00\dots0}_{1010 \text{ times}} and 1111010 times0001011 times\underbrace{11\dots1}_{1010 \text{ times}} \underbrace{00\dots0}_{1011 \text{ times}}. Concatenating infinitely many instances of these tuples in any order produces a sequence that satisfies the conditions of the problem. Indeed, consider any segment of 20212021 consecutive terms of such sequence. As any two consecutive full blocks of zeros or ones contain at least 20202020 terms in total, the segment under consideration contains terms of at most three such blocks. If it contains terms of three blocks then it contains the middle block fully. If the segment contained only two partial blocks of zeros or ones, it could contain at most 20202020 terms in total. Hence the segment under consideration must contain one full block even if it contains only terms of two consecutive blocks. In any case, the digit of the full block occurs either 10101010 or 10111011 times and the other digit must occur either 10111011 or 10101010 times, respectively. Combining the tuples defined at the beginning of the solution according to some non-periodic pattern (e.g., xyxxyxxxyxxxxyxyxxyxxxyxxxxy\dots), the resulting sequence is not periodic from any place on. Indeed, suppose the contrary; let the length of the period be pp. We can find a pattern of length lcm(p,2021)\text{lcm}(p, 2021) starting from the place where periodicity starts, containing the tuples defined at the beginning of the solution a full number of times. But the middle term of these tuples is not repeating periodically, implying that the entire pattern also cannot be periodic. Consequently, there exist non-periodic sequences that satisfy the conditions of the problem.

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.