Maths Olympiad Prep

Library / /4 of 4

Algebra Difficulty 6.6 National olympiad Prove it Silk Road Mathematics Competition

A sequence ss consisting of zeroes and ones is given. For each positive integer kk we define vkv_k as the maximum number of ways to find consecutive digits forming the sequence ss in a sequence of kk digits. (For example, if s=0110s = 0110, then v7=v8=2v_7 = v_8 = 2, since in the sequences 0110110 and 01101100 consecutive digits 0110 are found in two places, and three pairs of ones surrounded by zeroes can not occur in a sequence of 7 or 8 digits.) It is known that vn<vn+1<vn+2v_n < v_{n+1} < v_{n+2} for some positive integer nn. Prove that all the digits in the sequence ss are identical.

Solution

Let the sequence s=c1c2cms = c_1c_2 \dots c_m have length mm, and some sequence XX of length nn be a1a2ana_1a_2 \dots a_n. If two occurrences of ss in XX begin with apa_p and ap+ka_{p+k}, then ap+i=ap+i+k=ci+1a_{p+i} = a_{p+i+k} = c_{i+1} for 0i<m0 \le i < m. When kmk \le m this means that ci=ci+kc_i = c_{i+k} for 1imk1 \le i \le m-k, that is, ss is the beginning of the (infinite) periodic sequence a1a2aka1a2aka1a_1a_2 \dots a_k a_1a_2 \dots a_k a_1 \dots with period kk. We choose the minimum such kk; if no such k<mk < m exists, we let k=mk = m (since ss is obviously the beginning of the periodic sequence a1a2ama1a2ama1a_1a_2 \dots a_m a_1a_2 \dots a_m a_1 \dots).

We have seen that the number of places in XX where the occurrences of ss begin must differ at least by kk. If there are tt such occurrences, the last one should begin at the place with number not less than 1+k(t1)1+k(t-1), so m+k(t1)nm+k(t-1) \le n. It follows that the number of occurrences of ss in any sequence of length nn does not exceed nmk+1\lfloor \frac{n-m}{k} \rfloor + 1.

On the other hand, an example of a sequence where ss can be found in this number of ways, is given by the periodic sequence a1a2aka1a2aka1a_1a_2 \dots a_k a_1a_2 \dots a_k a_1 \dots.

We have proved that vn=nmk+1v_n = \lfloor \frac{n-m}{k} \rfloor + 1, and the problem states that
nmk<nm+1k<nm+2k. \lfloor \frac{n-m}{k} \rfloor < \lfloor \frac{n-m+1}{k} \rfloor < \lfloor \frac{n-m+2}{k} \rfloor .
If the inequality ak<a+1k\lfloor \frac{a}{k} \rfloor < \lfloor \frac{a+1}{k} \rfloor holds for an integer aa and a positive integer kk, then kk divides a+1a+1 (since an integer which is greater than ak\frac{a}{k} and not greater than a+1k\frac{a+1}{k}, can be presented as a fraction with denominator kk and therefore equals a+1k\frac{a+1}{k}). Therefore, the problem implies that kk divides both nm+1n-m+1 and nm+2n-m+2, which is possible for k=1k=1 only. By the definition of kk we have ci=ci+1c_i = c_{i+1} for 1im11 \le i \le m-1, that is, every two consecutive digits in ss are equal. Thus all the digits of ss are equal.

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.