[/quote]
,
be an odd prime number. Let 
be the sequence defined as follows: 
,
,
such that in 
there are no arithmetic progressions of length 
.
with 
,
be an integer. In a configuration of an 
board, each of the 
cells contains an arrow, either pointing up, down, left, or right. Given a starting configuration, Turbo the snail starts in one of the cells of the board and travels from cell to cell. In each move, Turbo moves one square unit in the direction indicated by the arrow in her cell (possibly leaving the board). After each move, the arrows in all of the cells rotate 
counterclockwise. We call a cell good if, starting from that cell, Turbo visits each cell of the board exactly once, without leaving the board, and returns to her initial cell at the end. Determine, in terms of 
positive integers 
such that for every index 
,
,
is a multiple of 
.
and 
be positive integers satisfying the equation ![$(a, b) + [a, b]=2021^c$](http://latex.artofproblemsolving.com/2/4/6/246ccbb22acecb7adc72219afb8afb34c9b05101.png)
.
is a prime number, prove that the number 
is composite.
be the set of real numbers. Determine all functions 
such that ![\[ f(x^2 - y^2) = x f(x) - y f(y) \]](http://latex.artofproblemsolving.com/6/8/f/68f78e0df627f6ac04052433c01627bf16f0af8e.png)
for all pairs of real numbers 
and 
.
into 
or 
can sometimes be quite complex. That's why I’ve written a program to assist with this process.
be real numbers such that 
Prove that 
Where 
with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of 
Prove that 
,
,
,
'![\[n=a_1+a_2+\dots+a_m,\]](http://latex.artofproblemsolving.com/6/c/2/6c2a979a5ff6c40bf2d7152c8c32088fc36f848b.png)
where 
,
,
and 
.
equally spaced points on a circular track 
of circumference 
in some order, each label used once. Initially, Bunbun the Bunny begins at 
.
,
,
,
to 
,
of 
is a diameter of 
Y by Adventure10, Mango247, PikaPika999, Fishheadtailbody, and 1 other user
Let 
be a positive integer. Given a sequence 
, 
, 
with 
or 
for each 
, , 
, the sequences 
, , 
and 
, , 
are constructed by the following rules: ![\[a_0 = b_0 = 1, \quad a_1 = b_1 = 7,\]](//latex.artofproblemsolving.com/d/f/d/dfd49833078b6b676cd261cc358e8114b2c4b7f4.png)
![\[\begin{array}{lll}
a_{i+1} =
\begin{cases}
2a_{i-1} + 3a_i, \\
3a_{i-1} + a_i,
\end{cases} &
\begin{array}{l}
\text{if } \varepsilon_i = 0, \\
\text{if } \varepsilon_i = 1, \end{array}
& \text{for each } i = 1, \dots, n - 1, \\[15pt]
b_{i+1}=
\begin{cases}
2b_{i-1} + 3b_i, \\
3b_{i-1} + b_i,
\end{cases} &
\begin{array}{l}
\text{if } \varepsilon_{n-i} = 0, \\
\text{if } \varepsilon_{n-i} = 1, \end{array}
& \text{for each } i = 1, \dots, n - 1.
\end{array}\]](//latex.artofproblemsolving.com/8/9/0/8908021c60992e39acdb4fcf6b587f96b88539e0.png)
Prove that 
.
Proposed by Ilya Bogdanov, Russia
be a positive integer. Given a sequence 
, 
, 
with 
or 
for each 
, , 
, the sequences 
, , 
and 
, , 
are constructed by the following rules: ![\[a_0 = b_0 = 1, \quad a_1 = b_1 = 7,\]](http://latex.artofproblemsolving.com/d/f/d/dfd49833078b6b676cd261cc358e8114b2c4b7f4.png)
![\[\begin{array}{lll}
a_{i+1} =
\begin{cases}
2a_{i-1} + 3a_i, \\
3a_{i-1} + a_i,
\end{cases} &
\begin{array}{l}
\text{if } \varepsilon_i = 0, \\
\text{if } \varepsilon_i = 1, \end{array}
& \text{for each } i = 1, \dots, n - 1, \\[15pt]
b_{i+1}=
\begin{cases}
2b_{i-1} + 3b_i, \\
3b_{i-1} + b_i,
\end{cases} &
\begin{array}{l}
\text{if } \varepsilon_{n-i} = 0, \\
\text{if } \varepsilon_{n-i} = 1, \end{array}
& \text{for each } i = 1, \dots, n - 1.
\end{array}\]](http://latex.artofproblemsolving.com/8/9/0/8908021c60992e39acdb4fcf6b587f96b88539e0.png)
Prove that 
.Proposed by Ilya Bogdanov, Russia
This post has been edited 2 times. Last edited by djmathman, Jun 26, 2015, 11:54 PM
Reason: changed latex to match that of english version of ISL2009
Reason: changed latex to match that of english version of ISL2009
for all 
.
should have 
equal 0 or 1 as the cases, as opposed to 
.
![\[b_{i + 1} = \left\{
\begin{array}{cl}
2b_{i - 1} + 3b_i, & \text{if} \ \epsilon_i = 0, \\
3b_{i - 1} + b_i, & \text{if} \ \epsilon_i = 1,
\end{array}
\right.\]](http://latex.artofproblemsolving.com/e/0/6/e0627ce852b41285c3779601549d522e6caa7c38.png)
![\[b_{i + 1} = \left\{
\begin{array}{cl}
2b_{i - 1} + 3b_{i}, & \text{if} \ \epsilon_{n-i} = 0, \\
3b_{i - 1} + b_{i}, & \text{if} \ \epsilon_{n-i} = 1,
\end{array}
\right.\]](http://latex.artofproblemsolving.com/6/7/d/67dbb1a0667b3fd37ff921e5e92f03c1aaeb7ba0.png)
the ring of 
matrices over the rational numbers.
and 
by 
and 
.
,
by 
.
if 
,
if 
.
(this is just another way to rewrite the equation 
,
satifies 
(this follows by induction over 
,
)
,
.
(because 
)
(this is just another way to rewrite the equation 
,
(this follows by induction over 
)
.
(because 
)
.
.
which satisfies 
,
satisfies 
.
be the invertible matrix 
.
)
satisfies 
(where 
is the identity matrix 
)
for any two 
and 
.
for any 
and any 
,
,
.
and 
,
.
now. Clearly, this will follow immediately once we have shown that 
for every 
and 
,
(since 
.
is to choose 
is a linear combination of 
and 
)
which satisfy 
be a field, and 
which satisfy 
matrices 
)
by 
satisfies 
for any 
.
an invertible 
.
,
for every matrix 
define 
recursively as follows: ![\[(1,7)^{\emptyset}=7,\quad(1,7)^0=23,\quad(1,7)^1=10\]](http://latex.artofproblemsolving.com/e/4/a/e4a469aa691d77cbb9e35d3e69557ac190c407a4.png)
![\[(1,7)^{wxy}=\begin{cases}2(1,7)^w+3(1,7)^{wx},\quad&\text{if }x\in\{0,1\},y=0\\3(1,7)^w+(1,7)^{wx},\quad&\text{if }x\in\{0,1\},y=1\end{cases}\]](http://latex.artofproblemsolving.com/b/1/b/b1b73cca4a77b6f283b8f44a4aec6d877b177bde.png)
Also define 
as the binary word obtained by reversing the digits of ![\[(1,7)^{xyw}=((1,7)^w,(1,7)^{yw})^x,\quad x,y\in\{0,1\}\]](http://latex.artofproblemsolving.com/b/b/d/bbd376b5afbb237d9aa551b4e0a35f62eed462f0.png)
by induction on the length of 
for 
.
by induction on the length of 
where ![\[(1,7)^{\overline{xyz}}=(1,7)^{zy\overline{x}}=((1,7)^{\overline{x}},(1,7)^{y\overline{x}})^z=((1,7)^x,(1,7)^{xy})^z=(1,7)^{xyz}\]](http://latex.artofproblemsolving.com/c/b/9/cb9e74d3d2b92b0686b901bff03f14c3a9b85ae5.png)
where 
,
.
,
,
or 
.![[asy]
size(6cm);
int n = 7;
for (int i=1; i <= n; ++i) {
draw( (i,0)--(i-1,0)--(i-1,1)--(i,1)--cycle );
if (i <= 2) { MP("\epsilon_" + (string) i, (i,1), dir(90)); }
if (i == n-2) { MP("\epsilon_{n-2}", (i,1), dir(90)); }
if (i == n-1) { MP("\epsilon_{n-1}", (i,1), dir(90)); }
}
[/asy]](http://latex.artofproblemsolving.com/a/8/8/a889e7c1129a27a597672590c0f5acb4e1331419.png)
arranged in a row. There are 
walls; we label the wall between rooms 
with 
.
are two colors of a wall. For walls labelled zero, we dictate that ![\[ i \in \left\{ j-2, j-1, j, j+1, j+2 \right\} \pmod{13}. \]](http://latex.artofproblemsolving.com/1/b/8/1b867575a620cb23cee6c18ebf9fadcd1e83994b.png)
For walls labelled one, we dictate that 
.
,
counts the number of ways to paint the leftmost 
rooms of the mansion, while 
counts the number of ways to paint the rightmost 
.
rooms with the colors 
.
colors we can select for 
,
,
choices. This happens for 
mansions. The recursion 
follows.
follows.![\[ i \in \left\{ j-2, j-1, j, j+1, j+2 \right\} \pmod{13} \]](http://latex.artofproblemsolving.com/4/6/0/460de31ebc2338cc1eba45af7acf8ff5b062a066.png)
for walls labelled zero, and ![\[ i = j \]](http://latex.artofproblemsolving.com/8/9/8/898982d17ae2223317db41399008b46fdac45dcd.png)
for walls labelled one?
,
,
for some integer coefficients 
.
,
would be the backwards coefficients. The coefficients are unique to the string 
.
for 
.
and 
.
.
.
and doing the first 
.
and simplifying this gives 
.
and evaluating the first 
and evaluating the first 
steps backwards. But starting with 
under both operations, so we're done.
?
.
and we can get 
of multivariate polynomials as follows: 
and 
for 
.
corresponds to 
corresponds to 
.
,
if 
,
if 
.
is the same if we reverse the order of the 
.
be the power of 
.
,
if 
if 
.
'
'
from 
,
we see how to construct more similar problems :
and vector 
.
.
,
.
,
,![\[
P_n = (2+x_{n-1})P_{n-2} + (3-2x_{n-1})P_{n-1}
\]](http://latex.artofproblemsolving.com/1/b/9/1b9e1b9d87cf851293c45f761b2acd11e7325920.png)
for 
.
as well. We proceed by strong induction on 
are easily checked by hand. For the inductive step, note that ![\[
P_n(x_1,\ldots, x_{n-1}) = (2+x_{n-1})P_{n-2}(x_1,\ldots, x_{n-3}) + (3-2x_{n-1})P_{n-1}(x_1,\ldots, x_{n-2}).
\]](http://latex.artofproblemsolving.com/b/8/b/b8b248d654ad14be50fe609a6e1cb774be4422da.png)
Now, ![\[
\begin{aligned}
P_n(x_{n-1}, \ldots, x_1) &= (2+x_1)P_{n-2}(x_{n-1},\ldots, x_3) + (3-2x_1)P_{n-1}(x_{n-1},\ldots, x_2)\\
&= (2+x_1)P_{n-2}(x_3,\ldots, x_{n-1}) + (3-2x_1)P_{n-1}(x_2,\ldots, x_{n-1}). \qquad \qquad (\spadesuit)
\end{aligned}
\]](http://latex.artofproblemsolving.com/c/d/6/cd61d633ab2c076b62f3d2c1b9ba56df2c856f6f.png)
Now, ![\[
P_{n-1}(x_2,\ldots, x_{n-1}) = (2+x_{n-1})P_{n-3}(x_2,\ldots, x_{n-3}) + (3-2x_{n-1})P_{n-2}(x_2,\ldots, x_{n-2}),
\]](http://latex.artofproblemsolving.com/9/d/f/9dff90cddc17db2ff1585fb9fcf780cd85e00910.png)
and![\[
P_{n-2}(x_3,\ldots, x_{n-1}) = (2+x_{n-1})P_{n-4}(x_3,\ldots, x_{n-3}) + (3-2x_{n-1})P_{n-3}(x_3,\ldots, x_{n-2}).
\]](http://latex.artofproblemsolving.com/e/7/9/e79c7b852cd0e59bc25f9cb9f54f293a2892295a.png)
Substituting into 
and collecting 
and 
terms, we see that ![\[
P_n(x_{n-1},\ldots, x_1) = (2+x_{n-1})((2+x_1)P_{n-4}(x_3,\ldots, x_{n-3})+(3-2x_1)P_{n-3}(x_2,\ldots, x_{n-3}))\]](http://latex.artofproblemsolving.com/7/e/8/7e81f2549b2b3f46faca071450e482ad49e05087.png)
![\[+(3-2x_{n-1})((2+x_1)P_{n-3}(x_3,\ldots, x_{n-2}) + (3-2x_1)P_{n-2}(x_2,\ldots, x_{n-2})).
\]](http://latex.artofproblemsolving.com/9/3/f/93f341679d036332f1ad2a1cb7a00b83ecd0ebd3.png)
The first collapses into ![\[
(2+x_{n-1})((2+x_1)P_{n-4}(x_{n-3},\ldots, x_{3})+(3-2x_1)P_{n-3}(x_{n-3},\ldots, x_2))\]](http://latex.artofproblemsolving.com/d/3/a/d3a2d4f586056a79070a0104d2cbcd5f7f7701cb.png)
![\[= (2+x_{n-1})P_{n-2}(x_{n-3},\ldots, x_1) = (2+x_{n-1})P_{n-2}(x_1,\ldots, x_{n-3}),
\]](http://latex.artofproblemsolving.com/4/3/9/43970191b42607b86b9ff7cbe1b63f189eda1d97.png)
while the latter collapses into ![\[
(3-2x_{n-1})((2+x_1)P_{n-3}(x_{n-2},\ldots, x_{3}) + (3-2x_1)P_{n-2}(x_{n-2},\ldots, x_{2}))\]](http://latex.artofproblemsolving.com/5/e/a/5ea9256c8c6babb373215d9f2cbd81ad582f37f5.png)
![\[ = (3-2x_{n-1})P_{n-1}(x_{n-2},\ldots, x_1) = (3-2x_{n-1})P_{n-1}(x_1,\ldots, x_{n-2}),
\]](http://latex.artofproblemsolving.com/1/f/3/1f330e74e14d6e9a6bcfa4c8754b7f6bf8224525.png)
which when summed equals 
.
.
where 
is the 
t
given by the corresponding choice of 
.
,
denotes reversing the order. We'll induct on the length of 
with base cases 
obvious. For the inductive step, it's enough to show that if 
,
.
and 
so it's enough to show these latter quantities are equal. Suppose 
and 
;
.
.
.
;
proves the equality.
.
;
,
.
;
,
.
;
,
(
and 
if e is 0, and 
if e is 1. Same for 
.
![\[a_{i+1} = (2+\varepsilon_i)a_{i-1} + (3-2\varepsilon_i)a_i\]](http://latex.artofproblemsolving.com/d/2/1/d21933293ef90c39c1e068bd00906719e9082553.png)
and ![\[a_{i+1} = (2+\varepsilon_{n-i})a_{i-1} + (3-2\varepsilon_{n-i})a_i.\]](http://latex.artofproblemsolving.com/3/c/3/3c3632d26bc94a4493292a1534b097f46656612c.png)
Using these relations without plugging in 
,
-
.
interchange. It is intuitively clear that it suffices to show this for all 
for some fixed 
of degree at most 
for some fixed 
,
.
where 
and 
for 
for any ![\[P(x_1,\ldots,x_n)\ne 0.\]](http://latex.artofproblemsolving.com/9/2/4/92466a443dead01062c2be37b4038a96e60f9020.png)
This is a contradiction, so we're done. 
.
if 
and 
if 
.
if 
if 
,
,
.
s
,![\[x=\sum_{B}\lceil f(B)/2\rceil,\]](http://latex.artofproblemsolving.com/7/b/4/7b446b039581722cc603e2eb06d57ce2a8107810.png)
where 
is the size of the block. This stays the same if we flip the sequence, so we're done.
Starting with 
and 
,
as a polynomial in 
.
,
is used wherever 
is used instead. So now we can forget about the 
sequence entirely!
whose coefficients are in terms of the new variable ![\[
\begin{tabular}{cc}
$a_1:$ & $\emptyset$ \\
$~$ & $7$
\end{tabular}
\]](http://latex.artofproblemsolving.com/7/e/a/7ead9078bc4499b647ed69a33a2bf847c5317562.png)
The table for 
is:![\[
\begin{tabular}{ccc}
$a_2:$ & $0$ & $1$ \\
$~$ & $23$ & $-13$
\end{tabular}
\]](http://latex.artofproblemsolving.com/5/2/2/52247d9368984f8a7666bfb1d1191abfe743fea1.png)
The table for 
is:![\[
\begin{tabular}{ccccc}
$a_3:$ & $00$ & $10$ & $01$ & $11$ \\
$~$ & $83$ & $-39$ & $-39$ & $26$
\end{tabular}
\]](http://latex.artofproblemsolving.com/b/8/6/b86bac996935543b31d685cc0eb1bf2481827cfb.png)
The table for 
is:![\[
\begin{tabular}{ccccccccc}
$a_4:$ & $000$ & $100$ & $010$ & $001$ & $110$ & $101$ & $011$ & $111$ \\
$~$ & $295$ & $-143$ & $-117$ & $-143$ & $78$ & $65$ & $78$ & $-52$
\end{tabular}
\]](http://latex.artofproblemsolving.com/6/a/8/6a8141a07bce8e8017c487a5961483cd5c746498.png)
![\[ a_{n+1} = 3a_n- 2\varepsilon_n a_n + 2a_{n-1} + 1\varepsilon_n a_{n-1}. \]](http://latex.artofproblemsolving.com/4/f/f/4ff93f4e5a0d6b215ca9883d6fbb6f54ae8e96be.png)
So to generate the table for 
from previous tables:
.
to the end. Multiply the values all by 
to the end. Multiply the values all by 
as follows: 
,
,
,
Prove 
for all binary strings 
denotes removing 
from the end of 
denotes the reverse of ![\begin{align*}
f(00S00) &= 3f(00S0)+2f(00S) \\
&= 3f(0\overline{S}00)+2f(\overline{S}00) \\
&= 3[3f(0\overline{S}0)+2f(0\overline{S})] + 2[3f(\overline{S}0)+2f(\overline{S})] \\
&= 9f(0\overline{S}0 + 6f(0\overline{S}) + 6f(\overline{S}0) + 4f(\overline{S}).
\end{align*}](http://latex.artofproblemsolving.com/7/0/4/7041c27196d306a993e27f405e3f1976e3c2bd33.png)
since the two middle terms have the same coefficient.![\begin{align*}
f(00S01) &= -2f(00S0)+f(00S) \\
&= -2f(0\overline{S}00)+f(\overline{S}00) \\
&= -2[3f(0\overline{S}0)+2f(0\overline{S})]+[3f(\overline{S}0)+2f(\overline{S})] \\
&= -6f(0\overline{S}0)-4(0\overline{S})+3f(\overline{S}0)+2f(\overline{S}) \\
\end{align*}](http://latex.artofproblemsolving.com/9/0/f/90f5182661f56bf8ca1cffb9c9bbc12df1d6461d.png)
comes out to 
,
.
.![\begin{align*}
f(00S11) &= -2f(00S1) \\
&= -2f(1\overline{S}00) \\
&= -2[3f(1\overline{S}0)+2f(1\overline{S})] \\\
&= -6f(1\overline{S}0-4f(1\overline{S}).
\end{align*}](http://latex.artofproblemsolving.com/d/a/c/dacd0098749287c92d23e58b0ef116792be50b98.png)
comes out to 
.
is irrelevant, but it's used to write the initial nice recursive formula. This is expected by ``polynomial intuition'', and the examples I listed confirm it. Then the final case-bash works -- I omitted some of the writeups but they are very similar to each other and I included the first few. You have to make cases on both the first two and last two because of the reversing.
are trivial and 
is easy to check.
and 
,
.
,
and 
.
and 
(with order of operations from left to right), and we want to show 
.
and 
where 
,
,
,
.
,
,
hint led me to this monstrosity, so at least I can divert some blame.
and 
for each ![\[x_n \in \{12x_{n-2} + 2x_{n-1}, 6x_{n-2} + 8x_{n-1}\}.\]](http://latex.artofproblemsolving.com/0/5/a/05ade0d2a2249759faddc9f37ae85138bcfeb35e.png)
This satisfies the important (!) property that 
.
different 
the number of ways to color the first 
t
colorings. If we color the cell, we have one of two cases:
cases here.
cells, yielding 
cases for the 
,
ways to color it and we have again a bijection to the 
colorings here.
,
.
,
and 
both count the number of ways to color the entire line, which means that they are equal.
statement) in general as long as the recursion reads ![\[x_n \in \{2a x_{n-1} + (k-2a)x_{n-2}, 2b x_{n-1} + (k-2b)x_{n-2}\}.\]](http://latex.artofproblemsolving.com/7/a/0/7a0d05195b262c26fc97c5cd518206c2cf0afe75.png)
In this case, the two types of walls permit colors with distance within 
and within 
,
list when you try to induct)
and 
but they are sort of annoying to try out.
and 
.
to the end of the first sequence, it is actually added to the start of the second sequence. In essence, soon we start to realize that the choice of 
where 
.
as well in some sense, which should become clearer later in this solution so that's nice.
![\[\{\varepsilon_1,\dots,\varepsilon_{n-1}\}:= (c_1,c_2)\]](http://latex.artofproblemsolving.com/e/8/b/e8b73e1a5c7976840dbc03ab2ec132b6ba716b08.png)
![\[\{\varepsilon_{n-1},\dots,\varepsilon_1\}:= (d_1,d_2)\]](http://latex.artofproblemsolving.com/d/4/b/d4b829f1630148911d67650dd00aea2e061896cd.png)
and by inductive hypothesis assume that 
.
.
we actually start with 
(essentially shift one term forward, since 
and we get 
as the desired common value.
leads to. To do this, write![\[\{\varepsilon_1,\dots,\varepsilon_{n-2}\}:=(C_1,C_2)\]](http://latex.artofproblemsolving.com/2/0/7/2074463ec7c2d446bd0b835ec65e2acca0725c5b.png)
![\[\{\varepsilon_{n-2},\dots,\varepsilon_1\}:=(D_1,D_2)\]](http://latex.artofproblemsolving.com/f/b/3/fb38552faa79bcf3871bcf92d0d48f898ec3899d.png)
so we'd like to show that![\[2(C_1+7C_2)+3(c_1+7c_2)=7d_1+23d_2\implies C_1+7C_2=2d_1+d_2.\]](http://latex.artofproblemsolving.com/4/a/1/4a11de2d02815ee77a99bc5111d988762b376699.png)
More brainstorming now (I put it already above but it's useful right now) by inductive hypothesis we want![\[C_1+7C_2=D_1+7D_2=2d_1+d_2.\]](http://latex.artofproblemsolving.com/5/e/d/5ed5e1807d21613dacf862a968a58af04ae5ef29.png)
Now consider a sequence 
which is extended with the rules outlined in the problem for sequence 
with set 
,
and 
,
.
,![\[3(C_1+7C_2)+(c_1+7c_2)=7d_1+10d_2\implies C_1+7C_2=2d_1+d_2\]](http://latex.artofproblemsolving.com/6/d/2/6d23b676193e55c3f5c5ef9b5ec909693e06213e.png)
and the rest is the same. good stuff man ! learned a decent amount about brainstorming from this i guess and also some about bashing as it is quite bashy and a little about backtracking too i guess as i failed on the direct bash approach where you just write in terms of multivar poly in 
and write 
for all 
(when 
doesn't alter 
,
(when 
yields 
,![\[\left\{\begin{array}{ll}
x_n=3m_n+l_n \\
y_n=2m_n
\end{array}\right.\]](http://latex.artofproblemsolving.com/a/2/4/a2442a67b382653452ebe7033e52ee9f3df05d25.png)
from where 
.
yields 
,![\[\left\{\begin{array}{ll}
x_n=m_n+l_n \\
y_n=3m_n
\end{array}\right.\]](http://latex.artofproblemsolving.com/6/a/6/6a6ac8ac879a618feae51fc988d88a86047ee75a.png)
from where 
,
forces 
and 
forces 
and 
