[/quote]
,
.
be an acute-angled triangle in which 
and 
.
lie on segment 
and point 
lie on segment 
such that 
,
and 
.
be the circumcenter of triangle 
,
the orthocenter of triangle 
the point of intersection of the lines 
and 
.
consecutive even numbers, such that the square of their product divides the sum of their squares.
to the system:![\[a_1^2 + a_1 - 1 = a_2\]](http://latex.artofproblemsolving.com/a/4/e/a4e26b83c929b82800576bac11e12de0c3aa1cf6.png)
![\[ a_2^2 + a_2 - 1 = a_3\]](http://latex.artofproblemsolving.com/9/9/5/995e8eec93828b82901b0639463f907f5ff95d08.png)
![\[\hspace*{3.3em} \vdots \]](http://latex.artofproblemsolving.com/e/e/1/ee15e1fefe2ad550d3c9b1c51207eaf66fbfa41f.png)
![\[a_{n}^2 + a_n - 1 = a_1\]](http://latex.artofproblemsolving.com/7/c/7/7c727d1f2044c1bf7c80981e1074bb3cde807b8f.png)
and 
are the feet of the altitudes through 
and 
respectively. The incenters of the triangles 
and 
are 
and 
respectively; the circumcenters of the triangles 
and 
are 
and 
respectively. Prove that 
and 
are parallel.
with 
prime and ![\[a^p+b^p=p!.\]](http://latex.artofproblemsolving.com/f/e/b/feb27894b1f6497559eeb094cfe92256bc26688e.png)
such that 
.
such that 
.
.
be a cyclic quadrilateral with circumcenter 
,
is not a diameter of its circumcircle. The lines 
and 
intersect at point 
lies between 
and 
lies between 
is acute and let 
and 
and 
.
,
.
which satisfy the condition![\[ f(m + n) \geq f(m) + f(f(n)) - 1
\]](http://latex.artofproblemsolving.com/4/b/d/4bddce124cf0da82cb8bb6c6ae2325239354f27c.png)
Find all possible values of 
be a positive integer and 
be a positive integer coprime to 
.
,
,
Find, in terms of 
,
such that 
is divisible by 
.
table are initially white. Alice and Bob play a game. First Alice paints 
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 
)
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 
which satisfy 
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 
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 
and 
,
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!
,
and 
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:
.
and add 
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 
,
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 
