A primitive $n$-saur can have at most $4n-3$ cells. Consider a cross formation consisting of a center cell and four extensions of length $n-1$. Of any partitioning of this animal, one partition contains the center cell. The other partitions can have length at most $n-1$, so this animal is $n$-primitive. Pick an $n$-subanimal out of a primitive $n$-saur that minimizes the number of animals into which the other cells are divided, and consider the remaining cells. If there are more than $3(n-1)$ of them, and they divide themselves into $3$ or less animals, one of them must have at least $n$ cells, contradiction. If they divide themselves into $4$ or more animals, these animals must be attached to the $n$-subanimal at at least two distinct cells (since a cell can only have three free edges for $n > 1$), so it is possible to create another $n$-subanimal by combining one of the other animals with it and removing some cells around the location where the others are attached. This produces an $n$-subanimal such that the other cells are divided into less animals; contradiction.

Another solution (I hope it is correct): The construction is same. Now say we have a primitive animal with $ 4n-2$ cells, that cannot be divided into two animals, each with at least $ n$ cells. Going downwards from the top of animal, we can divide the animal into rows. Suppose the animal has $ k$ rows, and the $ i$-th row has $ a_{i}$ cells. If $ n \leq a_{1} + ... + a_{i} \leq 3n-2$ for some value of $ i$, cutting horizontally between the $ i$-th and $ i+1$-th rows would give two animals, each with at least $ n$ cells. Contradiction. Thus $ a_{1} + ... + a_{i} \leq n-1$, or $ a_{1} + ... + a_{i} \geq 3n-1$. From this, clearly we have for some value of $ i$ that: $ a_{1} + ... + a_{i-1} \leq n-1$ and $ a_{1} + ... + a_{i} \geq 3n-1$, so $ a_{i} \geq 2n$ for some $ i$. Now consider the $ i$-th row. Since it has at least $ 2n$ cells, divide the animal vertically in the middle of this string of horizontal cells. Now we have two animals, each with at least $ n$ cells. Contradiction.

epitomy, do I misunderstand your solution, or is this shape a counterexample to your argument? X _ X X X X _ X _ _ X X X X X _ _ X _ X X X X _ X One of your claims was that splitting between the $ i$th and $ i+1$th row splits the animal into to two new ones, right? Here, splitting the animal between the 1st and 2nd rows creates three new animals, not two. Your argument was basically my solution, except that you have to do more than just use rows. I couldn't get it to work without turning the animal into a graph, and then into a tree.

Graph theory was apparently the most natural way to approach this. In particular, I believe a nice solution I read considered a minimal spanning tree (which appears to be essentially what I did in my solution).

Quote: One of your claims was that splitting between the ith and i+1th row splits the animal into to two new ones, right? Here, splitting the animal between the 1st and 2nd rows creates three new animals, not two. Yes, sorry that is a flaw in my proof. Could you post your proof using graph theory? I don't understand how to fix my proof. Also, what is a spanning tree?

Here's a sketch of my proof. We don't get our individual problem scores back, but I estimate based on my total score and my solution quality for each problem that this was scored as a $ 6/7$. Turn the animal into a graph, then into a tree. Prove or state as well-known that there is a vertex with degree 1, and start there. Mark that vertex 1. Now go along vertices, increasing the number by 1 each time (so 1,2,3...), until you reach a vertex with more than degree 2. Go towards the vertex that is joined to more vertices; i.e. the subgraph created by splitting it off from the vertex you're at now is of the greatest size. For this vertex, count up all of the vertices on the other paths you did not take, and in addition to adding 1, also add the total you just computed. You can prove that if you ever write down a number in between $ 2008$ and $ n - 2007$ (where $ n$ is the size of the animal), there is a way to partition the animal into two dinosaurs. (I believe I lost my point from not stating this proof) Then by using the fact that the maximum degree of any vertex is 4, you can prove that a number in this interval must be assumed if $ n > 8025$, and you're done.

epitomy01 wrote: Also, what is a spanning tree? Search engines are your friend. Any connected graph $ G$ contains a spanning tree $ T$, a tree such that $ V(T) = V(G)$ and $ E(T) \subset E(G)$. ($ V$ = the set of vertices of, $ E$ = the set of edges of.)

The answer is 4*n-3.Now,for example,pick an animal with center cell and n-1 cells from each direction.Now,lets prove we can partitate 4*n-2.We do this by simple induction on n.For n=1,2 is obvious.Now,we pick a subanimal with 4*n-6 cells(it is obvious we can do this) and from the inductive hypothesis we have that this can be partioned in two subanimals with n-1 cells or more.Now,if both of them have more than n-1,we are done,so we suppose they don't.Now,we add 4 cells.Now,if some of them touches an animal with n-1,we are finished,so suppose not.Now,the subanimal must be adjacent to the bigger subanimal at least at one cell,so if we pick that cell,it can partitate the bigger subanimal into at most 3 parts an the bigger subanimal now has 3*n-2 cells(cause the 4 we added must form a subanimal with it by assumption),so there exist one with n cells and the rest is a one subanimal,so we are done

Optimal construction is shown above To show that $4n-2$ 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. We say 2 cells are connected if there is a path between them that doesn't go through the origin. Consider the set of cells which are connected to $\{(-1,0), (1,0), (0,1), (0,-1)\}$ (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). By the pigeonhole principle, one of these sets has $n-1$ points. WLOG let that set be the connected points of $(1,0)$. The connected set of $(1,0)$ and the point $(1,0)$ create an n-saur with at least $n$ points. This is because there exists some path from (1,0) to every point in this set and thus every point in this set can get to any other point in this set by going through (1,0), thus creating a connected graph/partition The rest of the points not in the connected set of $(1,0)$ form a partition because they could not have been adjacent to a point in the connected set of $(1,0)$ or else they would be in that set. If there are less than $n$ points remaining, then we employ the greedy algorithm on the connected set of $(1,0)$. First, we choose $(1,0)$. And then we choose all points adjacent to $(1,0)$ and then all points adjacent to those adjacent points et cetera until we get another $n$-saur.

Is this solution correct? We show that $4n-2$ does not work. Mark one random square with at most three neighbors. Consider the following process: 1. Consider the last marked square. There are at most three "new" neighbours (other than the one already considered previously), so the unmarked squares can be categorized into three different connected "routes." Since there are at most $n$ marked squares currently ($(n-1)+1$), there are $3n-2$ squares yet to be marked, so one of the routes will have at least $n$ squares. Mark all of the squares that are not in that route. Thus, after this, there are always exactly two connected pieces and the unmarked one is a dinosaur. 2. If there are at least $n$ marked squares now, we are done since the marked square figure is connected and the unmarked figure is connected and a dinosaur 3. Mark the square in the unmarked route adjacent to the square we just processed

Does anyone know if my solution is correct? At first, I had another solution, but found an error, so I am wondering if there is still an error that I overlooked. Thank you so much for all your help! All advice is much appreciated

Let $k=2007$. The answer is $4k-3$. The construction is to take a central cell and append four rods, each consisting of $k-1$ cells, to the four sides of the central cell. Now we show that all dinosaurs with $V \ge 4k-2$ cells are not primitive. Transfer the problem to graph theory terms: form a spanning tree $T$ to represent the dinosaur, where cells are vertices and shared sides are edges. We wish to bipartition $T$ by removing an edge such that both resulting subtrees have at least $k$ vertices. Let $v \in T$ be any vertex. Consider any neighbor $w$ of $v$, and define $S_{v, w}$ as the largest subtree containing $w$ but not $v$; we say $S_{v, w}$ is a branch emanating from $v$. We say $S_{v, w}$ is small if it has fewer than $k$ vertices, large if it has greater than $V-k$ vertices, and medium otherwise. Our goal is to find a $v$ with a neighbor $w$ such that $S_{v, w}$ is medium, since we can then take the bipartition $\{S_{v, w}, T \setminus S_{v, w}\}$. Let us start by picking any $v \in T$. If $v$ has a medium branch, we are done, so assume otherwise. As $1 \le \deg v \le 4$, not all of $v$'s branches can be small, since that would imply that $|T| \le 4(k-1) + 1 < V$. Also note that $v$ cannot have two or more large branches; hence, $v$ has exactly one large branch. This observation is the basis for our algorithm: Let $w$ be the neighbor of $v$ such that $S_{v,w}$ is large. Then, $w$ has a branch $S_{w,v}$ consisting of $v$ appended to all of $v$'s small branches, meaning $S_{w,v}$ has at least $1$ more vertex than the largest small branch of $v$. Also note that $S_{w,v}$ has at most $3(k-1) + 1 = 3k-2 \le V-k$ vertices. Thus, $S_{w,v}$ is either medium or small. If $S_{w,v}$ is medium, we're done. If $S_{w,v}$ is small, forget $v$ and consider $w$ instead. Repeat these two steps with $w$ playing the role of $v$. In this manner, we move from vertex to vertex until we find a medium branch for the first time. At every step of the way, the size of the largest small branch of our vertex in consideration increases by at least $1$, and that branch never overshoots $V-k$ vertices, so this algorithm must terminate when we find a medium branch.

Hmm, how do we know each "cell" has exactly 4 edges with the current wording?

stroller wrote: Hmm, how do we know each "cell" has exactly 4 edges with the current wording? A cell is a unit square if I understood it correctly, so the maximum degree of the vertices is 4.

Define a thing as an animal that is not a dinosaur. Define an animal with size n if it consists of n equal-sized cells. We will prove the broader case of when n is the size of a dinosaur, the answer is $4n-3.$ Construction: cross of tiles. very ez to prove Proving the maximum: We will prove by contradiction. Let’s say for some $n>\ge 2$ ($n = 1$ is obvious) there is an arrangement of at least $4n-2$ cells such that it cannot be partitioned into $2$ primitive dinosaurs. Let the maximum number of cells be $m$. It is obvious that we can have at least $1$ dinosaur in these $4n-2$ cells. Consider a dinosaur such that when removed, it creates the biggest thing. We can assume the dinosaur has size $n$ to maximize the size of the animal. If this biggest thing has size $x$ where $x < n-1$, we, then we can add cells to this thing to increase its size to $n-1$, and we would have created an animal with more than m cells. To prove this won’t make an animal that can be partitioned into two dinosaurs, if we can, then we see that this added cell must have been added to one of these dinosaurs, which means before we added it, it had a size of $n-1$, which is greater than $x$, a contradiction (we assumed $x$ to be the biggest thing that could be created). Therefore, this thing must have size $n-1.$ We now see that we are left with at least $2n-1$ cells that aren’t included in the dinosaur or this thing. We can just assume it is $2n-1$ for now since we are proving with contradiction. If we remove the dinosaur again temporarily, we see that these $2n-1$ cells are all distributed among things. If one of these things were a dinosaur, then we would have a contradiction. Therefore, if these $2n-1$ cells are distributed among $2$ things, then by the Pigeonhole Principle, we would have an animal with at least $n$ cells, making it a dinosaur. Define a used cell as a cell that is part of the dinosaur, call it dinosaur $1$, that is adjacent to this $n-1$ sized thing. This means we must have these $2n-1$ cells distributed among $3$ things. Now consider a used cell. If we remove this cell from the dinosaur and add it to the $n-1$ sized thing. The $n-1$ sized thing is now a dinosaur, and the dinosaur is now a thing. However, dinosaur $1$ was connected to at least $3$ things, each with size at least $1.$ 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 $2$ dinosaurs, a contradiction. However, to prevent this, if we remove this cell from dinosaur $1,$ it could also be connected to other things too, not only the $n-1$ sized thing. This means for dinosaur $1$ to not be able to “steal” one of the things cells, the things must be connected to the dinosaur at this cell and only this cell. However, each cell only has $4$ sides. One of the sides is already connected to one of the sides of the dinosaur. Another side is also connected to the $n-1$ sized thing. Therefore, there are only $2$ sides left with at least $3$ things to be adjacent to. By the Pigeonhole Principle, one of the things will not be connected to dinosaur $1$ at this cell, a contradiction. Therefore, we cannot have a $4n-2$ celled animal, as all of them will be able to be partitioned into $2$ dinosaurs. This means $4n-3$ is the answer. Very messy drawing:

Devilish for amo 1/4 but pretty cool Replace $2007$ with $n$; the answer is $4n-3$. As a construction, consider a cross with a center cell and four "arms" each $n-1$ long. If this animal is partitioned, the partition containing the center cell has at least $3n-2$ cells, so the other partitions have length at most $n-1$. As such this animal is primitive. Now it suffices to show that no $4n-2$-cell dinosaur is primitive. Suppose otherwise, and consider a "semi-maximal path" $P=c_1,\ldots,c_k$ along the cells of the dinosaur $D$—that is, a path that cannot be made longer by "naively" adding cells to its start or end. Upon removing this path from $D$ there should remain some number (possibly zero) of connected components. For each of these components, let its "anchor" be one of its cells that is adjacent to $P$ (pick arbitrarily). Define a sequence of animals $a_0,\ldots,a_k \subseteq D$, starting with $a_0=\emptyset$. To construct the rest, "walk" from $c_1$ to $c_k$, and upon entering a cell $c_i$ set $a_i$ equal to the union of $a_{i-1},c_i$, and whatever connected components are anchored to $c_i$. Note that $a_k=D$ and $$0=|a_0|<|a_1|<\cdots<|a_{k-1}|<|a_k|=|D|=4n-2.$$Further, as $P$ is "semi-maximal" we actually have $|a_1|=1$ and $|a_{k-1}|=4n-3$. Now, it is clear that for all $i$, we can partition $D$ into the two possibly empty animals $a_i$ and $D \setminus a_i$—that is, both of these are connected figures. Because we can't have both of these be dinosaurs by assumption, there must exist some $2 \leq i \leq n-1$ with $$|a_{i-1}|\leq n-1 \text{ and } |a_i|\geq (4n-2)-(n-1)=3n-1.$$Note that $i=1$ and $i=n$ fail because of their known values. By definition, this means that the connected components anchored to $c_i$ must have total size at least $(3n-1)-(n-1)-1=2n-1$. On the other hand, there are only two possible edges to which a connected component could possibly be anchored to $c_i$, as the other two are "occupied" by $c_{i-1}$ and $c_{i+1}$. It then follows that there are at most two connected components anchored to $c_i$, and therefore one of them must contain at least $n$ cells. Let this connected component be $C$; then $D \setminus C$ is an animal, being connected "through" $P$, which also contains $3n-2\geq n$ cells, so we can partition $D$ into the dinosaurs $C$ and $D \setminus C$, contradiction. As such, $D$ cannot exist, so every $4n-2$-cell dinosaur is non-primitive. $\blacksquare$

Please could someone check this as it feels too short.

The following lemma kills the problem. Construct the tree with a base vertex of degree $4$ and with four length $2007$ paths. Lemma: There is some vertex $v$ so that $G - v$ does not leave behind any dinosaurs. Proof: Assume that for every vertex $v \in V(G)$, $G - v$ leaves behind dinosaurs. Then we have that if we consider the base of this tree, then we have at most four components for which aren't dinosaurs. A contradiction. $\square$ Hence we have the four components give us $4(n - 1)$ vertices and adding back the base of the tree gives us $4(n - 1) + 1$ total vertices. $\blacksquare$

Let $n=2007$. The answer is $4n-3$, achieved by a "+" shape where there are $n-1$ cells sticking out of the middle in all four directions. We will now prove that $4n-2$ doesn't work, so assume FTSOC that there is a primitive dinosaur of size $4n-2$. View an animal as a graph where the cells are the nodes and the edges are whether the two cells are orthogonally connected. Note that each node has degree at most $4$. Now arbitrarily remove edges until the graph is a tree. Clearly, any solution on the tree must work on the original graph. Now consider any leaf node in the tree, say $A$. Consider the longest path starting from $A$ in the tree(if there are multiple, choose any), and say it ends at $B$, which must be a leaf node. Let this path have length $k$, and let the path be $AP_1P_2\dots P_{k-1}B$. Define $P_0=A$ and $P_k=B$. Now let $f(x)$ be the number of nodes dangling off the path not including $P_x$(the ones that would be not connected to something in the path if $P_x$ were removed from the tree and all of its edges were removed), plus one(for $P_x$), at $P_x$. Also, define \[g(x)=f(0)+f(1)+\dots+f(x).\] Now consider the least $m$ such that $g(m)\ge n$. If $g(m)\le 3n-2$ we already have a contradiction by deleting the edge between $P_m$ and $P_{m+1}$, so we must have $g(m)\ge 3n-1$. But $g(m-1)\le n-1$ by definition, so \[2n=(3n-1)-(n-1)\le g(m)-g(m-1)=f(m).\]Therefore, by pigeonhole, there must be some tree dangling off of $P_m$ that has size at least $n$, contradiction.

Let $n = 2007$. The answer is $4n - 3$. The construction is same as above. Now we'll prove that the primitive dinosaur has at most $4n - 3$ edges. Let $G$ be a our primitive dinosaur and let $v$ be a cell in $G$. Let $v_{1}, \dots, v_{k}$ be neighbors of $v$. Define a vertex $u$ is $i$-good if there exist path $v$ to $u$ passing through vertex $v_{i}$. Let $A_{i}$ be a set of $i$-good vertices. For some $i$, if $|A_{i}| \geq n$, then $A_{i}$ is dinosaur and the rest of cells form a dinosaur, a contradiction. So the number of cell in $G$ not exceeds $1 + \sum_{i=1}^{k}|A_{k}| \leq 1 + 4(n - 1) = 4n - 3$. This completes proof. $\blacksquare$

We solve the more general case. An animal with at least $k$ cells is known as a k-nimal. Now, we claim that the maximum number of cells in a primitive $k-$nimal is $4k-3$. Consider a $k-$nimal with its cells in the shape of its cross with $k-1$ cells in each of the arms. This gives a total of $4k-3$ cells, and any set of $k$ cells in this configuration must pass through the center square implying that only one such set of cells exists (For any animal with less than $4k-3$ cells simply remove an adequate number of cells of the arms). Now, look at this animal with $n$ cells as a simple connected graph $G$, where each vertex represents a cell and each edge between two vertices represents two cells being adjacent. Then, we know there exists a spanning tree $T$ of this graph. Then, we have the following (kinda) well known result. Claim : Let $T$ be a tree and $v$ be any vertex of $T$. Let $v_1,v_2,\dots,v_m$ be the vertices adjacent to $v$. Let $T_i$ be the tree which contains $v_i$ which is obtain upon deleting the edge $vv_i$.Then, let $f(v)=\max_{i=1}^m|V(T_i)|$. Let $\Delta>1$ be the maximum degree among all vertices of $T$. Then, there exists a vertex $v$ such that \[\frac{n-1}{\Delta} \leq f(v) \leq \frac{(\Delta -1)(n-1)}{\Delta} \] Proof : Let $d$ 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}\]Now, to see why the right inequality must be true, consider the vertex $v$ such that $f(v)$ is minimum. Suppose $f(v) \geq \frac{(\Delta-1)(n-1)}{\Delta}+1$. Let $v_i$ be the neighbour of $v$ with $|T_i| \geq \frac{(\Delta-1)(n-1)}{\Delta}+1$. Then, clearly the tree containing $v$ after removing $v_iv$ contains at most $n - \frac{(\Delta -1)(n-1)}{\Delta}-1 = \frac{n-1}{\Delta}$. Now, if the tree $T_j$ which attains the maximum of $f(v_i)$ contains $v$, then $f(v_i) \leq \frac{n-1}{\Delta} \leq \frac{(\Delta -1)(n-1)}{\Delta}$ (with equality holding if and only if $\Delta=2$ in which case the result is obvious anyways). Thus, this violates the minimality of $f(v)$. If $T_j$ does not contain $v$ on the other, hand $f(v_i)=f(v)-1<f(v)$ again violating the minimality. Thus, our assumption must have been false and indeed, the required inequality holds. Now, note that if the given inequality is true, the spanning tree $T$ of our graph contains two vertices $v,v_i$ such that when we delete edge $vv_i$ we have two trees such that the larger of them, has length at least $\frac{n-1}{\Delta}$ and the smaller has length at least $n-\frac{(\Delta -1)(n-1)}{\Delta} = \frac{n-1}{\Delta}$. Thus, $T$ and indeed $G$ contain two vertex-disjoint connected subgraphs containing at least $\lceil{\frac{n-1}{\Delta}}\rceil$. Thus, for all $n\geq 4k-2$, we have two vertex-disjoin connected subgraphs such that each has at least \[\lceil{\frac{n-1}{\Delta}}\rceil \geq \lceil{\frac{4k-2-1}{4}}\rceil \geq k\]thus implying that it includes two $k-$nimals. Thus, such an animal cannot be primitive and we are done.

Answer is $8025$, which is attained with a $+$ shape with one central square and $2006$ squares in each branch. To show that $n \ge 8026$ is bad, we apply the spanning tree reduction stuff. Take an edge $uv$ 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 $u$, has at most $k \le 2006$ vertices, then we can find another edge incident to $v$ such that its removal from the original tree induces a component with between $k + 1$ and $n - k - 1$ edges, and blah blah blah minimality wrong done.

Replacing $k$ with $2007$, the answer is $4k-3 = 8025$, obtained by gluing four $2006 \times 1$ rectangles onto the edge of a unit square. Suppose we have an animal with $4k-2$ 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, $x \leq k$ squares are colored black, then $4k-2-x$ squares are colored white, so one of the two/three white animals has an area of at least