holds for all real numbers 
.
be positive real numbers such that 
Prove that:
and 
be two sequences defined by:![\[
a_{n+1} = \frac{1 + a_n + a_n b_n}{b_n} \quad \text{and} \quad b_{n+1} = \frac{1 + b_n + a_n b_n}{a_n}
\]](http://latex.artofproblemsolving.com/a/a/0/aa0a5c5acedc990eb345fb50a8395db05307a4e7.png)
for all 
,
and 
.![\[
a_{2024} < 5.
\]](http://latex.artofproblemsolving.com/f/c/a/fca6e6630f33429b5a7ea867d639a2e29ff881f2.png)
and write the numbers 
down on a board. A move consists in erasing any two numbers 
and 
,
and 
on the board, and then removing repetitions (e.g., if the board contained the numbers 
,
and 
,
)
Y by Adventure10, Mango247, and 3 other users
An animal with 
cells is a connected figure consisting of equal-sized cells[1].
A dinosaur is an animal with at least
cells. It is said to be primitive it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.
(1) Animals are also called polyominoes. They can be defined inductively. Two cells are adjacent if they share a complete edge. A single cell is an animal, and given an animal with cells, one with 
cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.
cells is a connected figure consisting of equal-sized cells[1].A dinosaur is an animal with at least
cells. It is said to be primitive it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.(1) Animals are also called polyominoes. They can be defined inductively. Two cells are adjacent if they share a complete edge. A single cell is an animal, and given an animal with
cells, one with 
cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.This post has been edited 1 time. Last edited by phxu, Mar 27, 2016, 8:39 PM
cells.
.
of them, and they divide themselves into 
or less animals, one of them must have at least 
or more animals, these animals must be attached to the 
)
cells, that cannot be divided into two animals, each with at least 
cells.
rows, and the 
-
cells.
for some value of 
-
,
.
and 
for some 
cells, divide the animal vertically in the middle of this string of horizontal cells. Now we have two animals, each with at least 
.
and 
(where 
,
contains a spanning tree 
,
and 
.
= the set of edges of.)
be a vertex in a tree, and 
be its neighbors, let 
be the subtree contation 
after the deletion of edge connecting 
.
be the maximal degree in a graph. Then there exists 
.
is 
.
vertices, which means it cannot be the subtree with maximal edge set. so 
,
,
but there exists 
.
,
.
doesn't work, put the n-saur onto the coordinate plane and place all the cells as integer coordinates and draw edges between adjacent cells. In this case, a connected graph is a partition and if 2 disjoint subgraphs would represent 2 different partitions.
(It is possible that a cell is connected to more than one of these, and it is also possible that one of the cells in this set is not actually on the n-saur and thus its connected set has size 0).
.
)
squares yet to be marked, so one of the routes will have at least 
.
and one center piece (looks like a plus sign). Attempt to partition this dinosaur. The center piece must be in one of the other partitions. The other partitions have size at most 
with size 
.
with vertices at each of the cells and edges between two vertices if and only if the corresponding cells are connected in 
be a spanning tree of 
,
denote the number of vertices in 
)
denote the maximal degree of any vertex in 
by definition and the problem constraints (each cell can only be connected in four places).
in graph 
denote the degree of 
,
denote the subtree formed by removing edge 
and taking the resulting tree containing ![\[\left|S_{V,N}+S_{N,V}\right|=n.\]](http://latex.artofproblemsolving.com/9/f/f/9ffe2f5e42f81484709ff48bc6f80b7d9413c0eb.png)
denote the neighbor of 
for any neighbor ![\[\left|S_{V,M\left(V\right)}\right|\geq\frac{n-1}{\deg_{\mathcal{T}}\left(V\right)}\geq\frac{n-1}{D\left(\mathcal{T}\right)}\geq\frac{n-1}{4}>2006\]](http://latex.artofproblemsolving.com/b/6/7/b673a4d98b7d2f802badce39a767293876954c19.png)
by the Pigeonhole Principle. Since 
is an integer, we get that 
.
be the vertex in 
.
is a proper subtree of 
,![\[\left|S_{M\left(A\right),M\left(M\left(A\right)\right)}\right|<\left|S_{A,M\left(A\right)}\right|,\]](http://latex.artofproblemsolving.com/c/a/5/ca5adcd780cdf5973dcdc160ecccedd47dab6ddd.png)
contradiction 
.
to form a forest with trees 
and 
(with ![\[\left|\mathcal{T}_A\right|=\left|S_{M\left(A\right),A}\right|=\left|S_{M\left(A\right),M\left(M\left(A\right)\right)}\right|\geq2007\]](http://latex.artofproblemsolving.com/f/2/e/f2e7ebca724f1ac3a240ea583682f715e405085f.png)
and ![\[\left|\mathcal{T}_{M\left(A\right)}\right|=\left|S_{A,M\left(A\right)}\right|\geq2007.\]](http://latex.artofproblemsolving.com/9/9/e/99e027218a6081832659b3cc76a26d7e677fbd3a.png)
Thus, if we revert back to our cell version of this graph, we have found a partition of 
.
.
cells, to the four sides of the central cell.
cells are not primitive. Transfer the problem to graph theory terms: form a spanning tree 
to represent the dinosaur, where cells are vertices and shared sides are edges. We wish to bipartition 
vertices.
be any vertex. Consider any neighbor 
of 
as the largest subtree containing 
vertices, and medium otherwise. Our goal is to find a 
.
,
.
is large. Then, 
consisting of 
more vertex than the largest small branch of 
vertices. Thus, 
primitive dinosaurs. Let the maximum number of cells be 
.
where 
,
cells that aren’t included in the dinosaur or this thing. We can just assume it is 
This means when we remove this cell, we can also remove a cell that is part of one of these things that is adjacent to one of the dinosaur’s cells, which means this will for 
it could also be connected to other things too, not only the 
along the cells of the dinosaur 
—
(pick arbitrarily).
,
.
to 
,
set 
equal to the union of 
,
and
Further, as 
and 
.
,
—
with
Note that 
and 
fail because of their known values.
.
and 
.
;
is an animal, being connected "through" 
cells, so we can partition 
as the maximum number of cells. Let an n-dinosaur be an animal with at least 
cells there exists a partition of it into two animals, both of which contain at least 
cells, we are done, as we can do a partition, one sub-dinosaur being the branch with the largest number of cells and the other being the remaining cells (note that an animal connected to another animal is an animal and since the non-branch partition is formed by connecting the original smaller partition with the cell from which the branches protrude - which is an animal - and between 0 and 2 branches, both of which are animals, the non-branch partition is an animal).
does not leave behind any dinosaurs.
,
vertices and adding back the base of the tree gives us 
total vertices. 
.
,
.
and 
.
be the number of nodes dangling off the path not including 
(![\[g(x)=f(0)+f(1)+\dots+f(x).\]](http://latex.artofproblemsolving.com/1/7/b/17b04b645208d7e44458a25899e3fadafc47e13f.png)
.
we already have a contradiction by deleting the edge between 
and 
,
.
by definition, so![\[2n=(3n-1)-(n-1)\le g(m)-g(m-1)=f(m).\]](http://latex.artofproblemsolving.com/2/b/3/2b3eb2a772fac5f7d1b2c720a1cb4f8d8d1c12c1.png)
Therefore, by pigeonhole, there must be some tree dangling off of 
.
.
be a our primitive dinosaur and let 
be neighbors of 
is 
.
be a set of 
,
.
n
be the vertices adjacent to 
.
.
be the maximum degree among all vertices of ![\[\frac{n-1}{\Delta} \leq f(v) \leq \frac{(\Delta -1)(n-1)}{\Delta} \]](http://latex.artofproblemsolving.com/7/8/7/78755517cb87806bcd2baf940bbdd60fab2e443e.png)
be the degree of some vertex. The left inequality clearly follows from Pigeonhole Principle as,![\[f(v) \geq \frac{n-1}{d} \geq \frac{n-1}{\Delta}\]](http://latex.artofproblemsolving.com/d/5/3/d53a865c53a1239a80b39515a37121c296282887.png)
Now, to see why the right inequality must be true, consider the vertex 
.
.
contains at most 
.
which attains the maximum of 
contains 
(with equality holding if and only if 
in which case the result is obvious anyways). Thus, this violates the minimality of 
again violating the minimality. Thus, our assumption must have been false and indeed, the required inequality holds.
such that when we delete edge 
and the smaller has length at least 
.
.
,![\[\lceil{\frac{n-1}{\Delta}}\rceil \geq \lceil{\frac{4k-2-1}{4}}\rceil \geq k\]](http://latex.artofproblemsolving.com/6/a/c/6ac8ba701091d5b50e62ec8e782d35b55b13f68f.png)
thus implying that it includes two 
shape with one central square and 
is bad, we apply the spanning tree reduction stuff. Take an edge 
that minimizes the difference between the number of vertices in the two components induced by its removal. If one of the components, without loss of generality say the one containing 
vertices, then we can find another edge incident to 
and 
edges, and blah blah blah minimality wrong done.
,
rectangles onto the edge of a unit square.
cells – we will partition this animal into two dinosaurs. Color one cell of the animal black, and the rest of the cells white. Each second, we find a white square adjacent to a black square, and color the white square black. If the white squares still form an animal, we continue, but our main concern is if they don't: by coloring this one square black, the white squares may be split into up to three animals. If, at the moment, 
squares are colored black, then 
squares are colored white, so one of the two/three white animals has an area of at least![\[\left \lceil \frac{4k-2-x}{3} \right \rceil \geq \left \lceil \frac{3k-2}{3} \right \rceil = k.\]](http://latex.artofproblemsolving.com/c/1/d/c1db56d04e205a21468efc502dbed3368dd6a60b.png)
Keep this animal white, and shade everything else black. This process can be repeated until at least 
.
-
is never primitive since, given extra cells, we may remove them temporarily until there are 
so, by Pigeonhole, since there are at most four neighbors, one of them has size at least 
,
connected to the "beefy side" is overweight, observe that our side 
has size at most 
adjacent to it. The "beefy side" of 
on the other side of the "beefy side" of 
will strictly decrease until it is at most 
where we replace 
such that 
leaves behind no dinosaurs
