Maths Olympiad Prep

Library / /705 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Define the sequence b0,b1,,b59b_{0}, b_{1}, \ldots, b_{59} by bi={1 if i is a multiple of 30 otherwise  b_{i}= \begin{cases}1 & \text { if } \mathrm{i} \text { is a multiple of } 3 \\ 0 & \text { otherwise }\end{cases} Let {ai}\left\{a_{i}\right\} be a sequence of elements of {0,1}\{0,1\} such that bnan1+an+an+1(mod2) b_{n} \equiv a_{n-1}+a_{n}+a_{n+1} \quad(\bmod 2) for 0n59(a0=a600 \leq n \leq 59\left(a_{0}=a_{60}\right. and a1=a59)\left.a_{-1}=a_{59}\right). Find all possible values of 4a0+2a1+a24 a_{0}+2 a_{1}+a_{2}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Try the four possible combinations of values for a0a_{0} and a1a_{1}. Since we can write ana_{n} \equiv bn1an2an1b_{n-1}-a_{n-2}-a_{n-1}, these two numbers completely determine the solution {ai}\left\{a_{i}\right\} beginning with them (if there is one). For a0=a1=0a_{0}=a_{1}=0, we can check that the sequence beginning 0,0,0,0,1,10,0,0,0,1,1 and repeating every 6 indices is a possible solution for {ai}\left\{a_{i}\right\}, so one possible value for 4a0+2a1+a24 a_{0}+2 a_{1}+a_{2} is 0 . The other three combinations for a0a_{0} and a1a_{1} similarly lead to valid sequences (produced by repeating the sextuples 0,1,1,1,0,1;1,0,1,1,1,00,1,1,1,0,1 ; 1,0,1,1,1,0; 1,1,0,1,0,11,1,0,1,0,1, respectively); we thus obtain the values 3,5 , and 6.

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.