I was worried this would be mess of casework, and maybe it can be, but the problem's actually extremely nice. (Warning: this contains images that will completely spoil the solution, so don't open if you just want a hint.)

We also asked this problem at the Canadian IMO winter camp in 2011 "mock olympiad": https://sites.google.com/site/imocanada/2011-winter-camp I'm not sure if the China TSTST got it from us or came up with it independently, but our version was in turn adapted from (in my opinion) the most beautiful programming contest problem ever posed: https://code.google.com/codejam/contest/801485/dashboard#s=p5

darthur wrote: We also asked this problem at the Canadian IMO winter camp in 2011 "mock olympiad": https://sites.google.com/site/imocanada/2011-winter-camp I'm not sure if the China TSTST got it from us or came up with it independently, but our version was in turn adapted from (in my opinion) the most beautiful programming contest problem ever posed: https://code.google.com/codejam/contest/801485/dashboard#s=p5 In fact, it is the same person who proposed this problem and the problem in Google Code Jam.

sorry for reviving , but doesn't this coloring agree with all the conditions? . i think i've understood the problem wrongly, please correct me.

@above the graph must be connected "path".

Replace $2017$ with any odd integer $n$. Furthermore, we will casually induct $n$ (i.e. induction is not the main idea), so note that the base case of $n=1$ is trivial. Interpret the graphs as ``snakes'', and color one blue and one red (purple will denote a snake of indeterminate color). Here is a nontrivial example for $n=7$ of a valid snake partition (taken from the google code jam problem statement). [asy][asy] int m=8,n=8; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i < m-1) draw((i-0.5, j-0.5)--(i + 1 - 0.5, j-0.5)); if(j < n-1)draw((i-0.5, j-0.5)--(i-0.5, j + 1 - 0.5)); } } dot((5,6),red); dot((4,2),red); dot((6,6),blue); dot((3,3),blue); draw((5,6)--(0,6)--(0,0)--(6,0)--(6,4)--(2,4)--(2,2)--(4,2),red); draw((6,6)--(6,5)--(1,5)--(1,1)--(5,1)--(5,3)--(3,3),blue); [/asy][/asy] Define the outer rim of the grid to be the outermost $4n-4$ squares. We have the following ``topological'' claim. Claim: Suppose we have two blue squares on the outer rim. Then, the snake path connecting them is always on the outer rim. Proof: Note that the path divides the square into two disconnected regions $R_1$ and $R_2$, which must both contain red squares. This is a contradiction as the red squares must be connected by a contiguous snake. [asy][asy] int m=8,n=8; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i < m-1) draw((i-0.5, j-0.5)--(i + 1 - 0.5, j-0.5)); if(j < n-1)draw((i-0.5, j-0.5)--(i-0.5, j + 1 - 0.5)); } } dot((5,6),blue); dot((0,3),blue); draw((5,6)--(2,6)--(2,4)--(0,4)--(0,3),blue); label("$R_1$",(0,6)); label("$R_1$",(1,6)); label("$R_1$",(0,5)); label("$R_1$",(1,5)); for(int x=0; x < 7;++x) { label("$R_2$",(x,0)); } for(int x=0; x < 7;++x) { label("$R_2$",(x,1)); } for(int x=0; x < 7;++x) { label("$R_2$",(x,2)); } for(int x=1; x < 7;++x) { label("$R_2$",(x,3)); } for(int x=3; x < 7;++x) { label("$R_2$",(x,4)); } for(int x=3; x < 7;++x) { label("$R_2$",(x,5)); } for(int x=6; x < 7;++x) { label("$R_2$",(x,6)); } [/asy][/asy]$\blacksquare$ The following claim is the key idea behind the problem. Claim: Suppose we have a turn in a snake. Then, the green ray as shown below must contain the endpoint of some snake. Call this green ray the characteristic ray of the turn. [asy][asy] int m=3,n=3; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { draw((-0.5,-0.5)--(-0.5,1.5)); draw((0.5,-0.5)--(0.5,1.5)); draw((1.5,-0.5)--(1.5,0.5)); draw((-0.5,-0.5)--(1.5,-0.5)); draw((-0.5,0.5)--(1.5,0.5)); draw((-0.5,1.5)--(0.5,1.5)); } } draw((0,1)--(0,0)--(1,0),blue); draw((0.5,0.5)--(4.5,4.5),green); [/asy][/asy] Proof: Suppose for sake of contradiction that there was no endpoint on the green ray. Consider $a$ as shown in the figure below. [asy][asy] int m=8,n=8; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i < m-1) draw((i-0.5, j-0.5)--(i + 1 - 0.5, j-0.5)); if(j < n-1)draw((i-0.5, j-0.5)--(i-0.5, j + 1 - 0.5)); } } draw((1,3)--(1,2)--(2,2),blue); label("$a$",(2,3)); label("$b$",(3,3)); label("$c$",(2,4)); [/asy][/asy] If $a$ is not an endpoint, then $a$ must be connected to $b$ and $c$ as part of a (red) snake. By the same logic, there must be a blue snake turn stacked on this new red one, and a red one on top of that, and so on. Clearly this causes problems once these ``stacked Ls'' reach the outer rim of the grid. $\blacksquare$ The following claim is an important extension of the above one. Claim: Suppose we have two turns in snakes that share the same characteristic rays but in opposite orientations. Then, their shared portion (a segment) must in fact contain two endpoints. [asy][asy] int m=8,n=8; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i < m-1) draw((i-0.5, j-0.5)--(i + 1 - 0.5, j-0.5)); if(j < n-1)draw((i-0.5, j-0.5)--(i-0.5, j + 1 - 0.5)); } } draw((1,3)--(1,2)--(2,2),purple); draw((4,6)--(5,6)--(5,5),purple); draw((1.5,2.5)--(4.5,5.5),green); [/asy][/asy] Proof: Clearly there is at least one endpoint on the green segment, else both turns would be of the same orientation, which is false. Now assume for sake of contradiction that there is only one endpoint. Then, by the logic of the proof of the above claim, by extending both turns toward the endpoint, we get the following configuration. [asy][asy] int m=8,n=8; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i < m-1) draw((i-0.5, j-0.5)--(i + 1 - 0.5, j-0.5)); if(j < n-1)draw((i-0.5, j-0.5)--(i-0.5, j + 1 - 0.5)); } } draw((1,3)--(1,2)--(2,2),purple); draw((2,4)--(3,4)--(3,3),purple); label("$a$",(2,3)); [/asy][/asy] The issue is that no matter what color $a$ is, it will either be isolated, or form a cycle with one of the existing snake pieces surrounding it. This is the desired contradiction. $\blacksquare$ We are now ready to attack the problem. By the first claim, the blue part of the outer rim is one contiguous piece, as is the red part. Place a $\times$ at the endpoints of these contiguous outer rim pieces. Note that a $\times$ in a corner implies that it is an endpoint of the snake, since one of the two squares it is adjacent to must be a $\times$ from the opposite color snake. Furthermore, we cannot have two $\times$ from the same color, since that would violate the first claim. Thus, there are three cases. Case 1: We have two $\times$ in corners. In this case, we have two opposite color endpoints in the outer rim, so actually deleting the outer rim gives a valid snake configuration in the resulting $(n-2)\times(n-2)$, so we finish by induction on $n$. Case 2: We have at most one $\times$ in a corner. This means that there are two adjacent $\times$ (from opposite colors) that are not in corners. Assume for sake of contradiction that the center is not an endpoint. Then, we have the following claim. Claim: Let $\ell_1$ and $\ell_2$ be segments connecting opposite corners. Then, all endpoints lie on either $\ell_1$ or $\ell_2$. consider Proof: There are two cases. Case 1: Suppose that one of the corners has a $\times$. WLOG say that $\ell_1$ contains a $\times$. Then, by the second and third claims respectively, $\ell_1$ contains at least one more endpoint, and $\ell_2$ contains two endpoints. These can't be shared since the center is not an endpoint, so we have shown that there are $4$ endpoints in $\ell_1\cup\ell_2$, so these are all the endpoints. Case 2: Suppose that none of the corners have a $\times$. Then, by the third claim, $\ell_i$ has at least two endpoints, so as before, we are done. $\blacksquare$ Now the two adjacent $\times$s that are not in corners can't be endpoints by the above claim. Therefore, the snake must continue from them into the heart of the grid, as shown in the figure below. [asy][asy] int m=8,n=8; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i < m-1) draw((i-0.5, j-0.5)--(i + 1 - 0.5, j-0.5)); if(j < n-1)draw((i-0.5, j-0.5)--(i-0.5, j + 1 - 0.5)); } } label("$\times$",(0,6)); label("$\times$",(6,4)); label("$\times$",(6,3)); label("$\times$",(0,5)); draw((0,6)--(6,6)--(6,4)--(5,4),red); draw((5,3)--(6,3)--(6,0)--(0,0)--(0,5),blue); draw((0.5,5.5)--(5.5,0.5),green); draw((0.5,0.5)--(5.5,5.5),green); [/asy][/asy] Then, both turns from the adjacent $\times$s have characteristic rays that must contain an endpoint. However, by the above claim, those endpoints must be the intersection of the characteristic rays with the central $\ell_1$ and $\ell_2$. It is easy to see by parity that one of those intersections is not valid. Indeed in the figure above, the characteristic ray of the lower blue $\times$ intersects $\ell_1\cup\ell_2$ at a point that is not the center of some square. This is the desired contradiction, so the proof is complete. Remark: An alternate nicer finish from the last claim is given by Luke Robitaille. We have shown that all the endpoints must lie on $\ell_1\cup\ell_2$. If we checkerboard color the grid, this means that all the endpoints of the paths have the same color on the checkerboard coloring. This means that both snakes have odd length, which is a contradiction since the total area of the grid is odd.

Here is a more optimized version of the solution above. (It does not prove as many things about the ending configuration, however.) For convenience, replace black/white coloring with red/blue coloring. We define some terminology: An elbow is a set of three consecutive cells $C_1, C_2, C_3$ in a path that form a bend (i.e. are not collinear); we call $C_2$ the center of the elbow. The inside of an elbow is the cell that makes a $2\times 2$ square with the three squares of the elbow. Now the main observation is that: Claim: [Elbows force new elbows] If the inside of an elbow $E$ is not an endpoint, there must be another elbow $E'$, centered at the inside of $E$, which has the same orientation of $E$. Proof. WLOG $E$ is red, and let cell $C$ be the inside of $E$. If $C$ is red, then we have a red cycle, contradicting the path hypothesis. Thus $C$ is blue, and must have two blue neighbors. Now since $C$ already has two red neighbors, there is only one possibility for these blue neighbors, and they form an elbow with center $C$ in the correct orientation. $\blacksquare$ Note that each corner of the grid is either an endpoint on the center of an elbow. If a corner $C$ is the center of an elbow, it emits a death ray towards the center of the grid, consisting of a staircase of elbows as described in the claim. [asy][asy] size(150); void fillr(int x, int y){ fill((x, y)--(x+1, y)--(x+1, y+1)--(x, y+1)--cycle, red); } void fillb(int x, int y){ fill((x, y)--(x+1, y)--(x+1, y+1)--(x, y+1)--cycle, lightblue); } fillr(0, 0); fillr(1, 0); fillr(0, 1); fillb(1, 1); fillb(2, 1); fillb(1, 2); fillr(2, 2); fillr(2, 3); fillr(3, 2); for (int i = 0; i < 5; ++i) { draw((i, 0)--(i, 4.5), linewidth(0.9)); draw((0, i)--(4.5, i), linewidth(0.9)); } draw((3, 3)--(4, 4)^^(4, 3)--(3, 4), linewidth(1.5)); [/asy][/asy] Each death ray must be blocked by an endpoint. (So if a corner of the grid is an endpoint, we say that it is blocking the death ray from that corner. Thus every corner emits a death ray.) Claim: An endpoint cannot block two death rays from opposite corners. Proof. This is clear, since the endpoint would either form a cycle with one of the elbows or would have no neighbors if the same color. $\blacksquare$ Claim: There cannot be four endpoints on the main diagonals. Proof. Checkerboard color the grid, so that all four corners are black. Then if all four endpoints were on main diagonals, then both the red path and blue path would have one more black square than white square, contradiction. $\blacksquare$ Combining the last two claims, we see that some endpoint must block the death rays from adjacent corners; hence this endpoint must be the center of the grid.

Solved with Max Lu, Ryan Yang, Carlos Rodriguez, Kevin Zhao, Luke Robitaille, Raymond Feng Consider the four corners of the grid. Let the colors be red and green, and we work over odd $n$ by $n$ grids. There are a few possibilities: Case 1: The two opposite corners are the same color, and are distinct colors from each other. Let the bottom left and top right corners be green, and the other two red. Then, the path from the bottom left to the top right intersects the path from the top left to the bottom right at a square. This square must be both red and green, a contradiction. Case 2: Three corners have the same color. WLOG let these corners be green, and let them be the bottom left, top left, and top right. Then, consider labeling the grid from $(0,0)$ to $(n-1, n-1)$, with the top left being $(0,0)$. Now, the path (consisting of straight lines) from $(n-2, 1)$ to $(1,1)$ to $(1,n-2)$ must all be red, since they are adjacent to green squares which already have a path. Similarly, the path from $(n-3, 2)$ to $(2,2)$ to $(2,n-3)$ must be green, and in general, the path from $(n-i-1,i)$ to $(i,i)$ to $(i, n-i-1)$ must be red if $i$ is odd, green if $i$ is even. Denote these paths as "bands". Consider taking $i = \frac{n-1}{2}$. FTSOC, assume $(\frac{n-1}{2}, \frac{n-1}{2})$ was not an endpoint. Then, it must be adjacent to $(\frac{n-1}{2}, \frac{n+1}{2})$ and $(\frac{n+1}{2}, \frac{n-1}{2})$ (and let these be green wlog). Now, this would also mean that $(\frac{n-3}{2}, \frac{n+3}{2})$ will be red (if it was green, then the green cell $(\frac{n-5}{2}, \frac{n+3}{2})$ will be adjacent to 3 green cells). We can similarly show that $(\frac{n-2i-1}{2}, \frac{n+2i+1}{2})$ will be the same color as the band it is adjacent to. However, this means that $(1, n-1)$ and $(n-1, 1)$ are both red, so $(0,n-1)$ and $(n-1, 0)$ are endpoints of the green band. This is a contradiction since this green band is now not connected to the other green cells, thus the center is an endpoint. Case 3: Two adjacent corners have the same color, distinct from the other two corners. Let the bottom corners be green, top corners be red. Then, using the same coordinate system, we have paths from $(0,0)$ to $(0, n-1)$ are red, $(1,1)$ to $(1,n-2)$ green, and in general, from $(i,i)$ to $(i, n-i-1)$ are red if $i$ even, otherwise green. Similarly, starting from the bottom, we have paths from $(n-1, 0)$ to $(n-1, n-1)$ are green, from $(n-2, 1)$ to $(n-2, n-2)$ are red, and in general, from $(i, n-i-1)$, $(i,i)$ are red if $i$ is odd. However, now taking $i = \frac{n-1}{2}$ gives the cell $(\frac{n-1}{2}, \frac{n-1}{2})$ is both green and red, a contradiction. Thus, we have exhausted all $3$ cases of the corners. Each of these either give no solutions or that the center is an endpoint. We conclude the result.

Forget the centers of the cells, and instead just draw all of the shared edges of differently colored cells. This produces a graph on vertices of cells. Observe we have all edges on the border of the grid. Now, we claim that at each point in the center of the grid has exactly two edges; clearly by 2-colorable around that vertex this must be even, and it cannot be 0 as that would mean all four cells around that vertex were one color which would create a cycle among cells. Thus, we need to rule out 4: if 4 were possible, this means we would have a checkerboard pattern around that cell, this is impossible (just mark five points: the centers of each of the four cells and the vertex in question, and then connect all of them with straight line segments, and observe we almost have a planar $K_5$ except opposite centers are not connected, but if opposite centers were the same color we could connect both pairs at the same time without crosses, creating a planar $K_5$, contradiction). Thus, the degree of each central vertex is 2 (and in fact this obviously applies to coners as well; edge vertices on the other hand could have degree 2 or 3). We also note that each cell is surrounded by exactly two edges in the graph unless it is an endpoint (4 such cells) in which case it is surrounded by exactly 3 edges. Now, let S be the set of all 90 degree angles in the graph. Now, treat each of these angles as arrows pointing in the obvious directions. If we are at a central vertex, then go one unit horizontally and vertically to move in that direction to get to a new vertex; observe that the original vertex and the new vertex have exactly one shared cell, and this cell does not have edges in the graph coming from the original vertex so it must have both (two) edges coming from the new vertex, and these edges form an angle at the new vertex that is 90 degrees and points in the same direction. We can repeat this process until we reach an edge or corner vertex. Hence, we may define two angles to be equivalent if they point in the same direction and they have vertices lying on a line in that direction; what we have proven then guarantees that the equivalence classes will consist of angles at all vertices of a line segment in the line, starting with a vertex in the center and ending with one on the border (where we move along the line in the direction of the arrows). Now, we prove that we can actually go backwards along these line segments in most cases: if we have an angle on the segment, then considering what would be the previous angle, this is the previous angle if and only if the two would-be edges from this vertex shared by the cell shared by both vertices are not part of the graph, which is true if and only if the cell is not an endpoint. Hence, endpoints are the only place that line segments can start. Now, we specify each line segment more exactly: we let it end exactly at the last vertex, and we let it begin at the center of the endpoint (which is halfway between the first vertex and the would-be previous vertex). Now, observe that each endpoint then starts exactly two line segments as it has exactly two right angles among its edges in the graph. As there are 4 endpoints, there are 8 line segments. No two line segments can intersect in their interiors by the fact that each nonendpoint nonborder cell can have at most angle among its edges and each interior vertex can have at most one angle among its edges. Now, observe that each corner of the graph must be the endpoint of exactly one line segment. This leaves 4 line segments to terminate at the edges, and observe that at any edge vertex with one line segment terminating at it it must in fact have exactly two line segments terminating at it, going at right angles to one another. Hence, there are two edge vertices that are terminating points of line segments. Now, observe that the 8 line segments may be paired by which ones share their beginning point. Two line segments in a pair must have different slopes (note of course there are two options for the slope of each line segment) and must have opposite parities of the sums of the coordinates of each vertex lying on the line (this is because they do not intersect at a vertex). Now, observe that considering two opposite corners, the line segments ending at them have both the same direction and the same parities of coordinate sums of each vertex. On the other hand, two adjacent corners have different parities of coordinate sums of their line segments. On the other hand, two line segments terminating at the same edgepoint must have the same parity but different direction. Now, observe that if the pairing on line segments was to pair each segment ending at a corner with each segment ending at an edgepoint, then two of the segments ending at an edgepoint would be in one direction and have the same parity, whereas the other two would be in the opposite direction with the opposite parity. However, then the pairing based on shared endpoints for these line segments would be impossible, so this pairing based on shared beginning points cannot be such that each corner line segment gets assigned an edge line segment; hence two corner line segments must be paired, and these must be adjacent in order to be in different directions. Those line segments then intersect in the center of the gird which is the center of the central cell of the grid, and that cell then must be an endpoint, so in the original formulation of the problem its center, which is the center of the grid, must be an endpoint, as desired.

At every $90^{\circ}$ turn in a path, we emit a laser beam, which is a ray through the vertex at the turning point that makes a $45^{\circ}$ angle with both edges adjacent to the turn. Claim: Every laser beam $B$ passes through one of the four path endpoints. Proof. Assume otherwise. Consider an $L$-shaped monochromatic tromino (WLOG it is white) with laser beam $B$. Then ``stack" on it an $L$-shaped black tromino so that it has the same laser beam. Continue this process (which we can do by our assumption) until the tromino hits a side of the grid, at which point it is impossible to legally complete the snake containing that tromino, a contradiction. Claim: Suppose that two monochromatic trominoes $T_1$ and $T_2$ have a common laser beam $B$. If we do not allow $B$ to ``pass" through $T_1$ and $T_2$, then $B$ contains two of the four path endpoints. Proof. Assume for contradiction that there exists an endpoint that lies on the extension of $B$ but not on $B$. Then do some messy casework and show that it is impossible for the paths to be completed. Claim: If the center of the grid is not a path endpoint, then each of the four path endpoints lie on a diagonal of the grid. Proof: We do casework on the number of path endpoints at the corners of the grid. 0 endpoint in corners: Then there is a monochromatic tromino in every corner, so we finish by the second claim. 1 endpoint in corners: By annoying casework we figure that one diagonal has a path endpoint and a monochromatic tromino at its endpoints and the other has monochromatic trominoes at its endpoints. We finish by the first and second claims. 2 endpoints in corners: Induct on odd $n$ with base cases $n=1$, $n=3$ trivial. Then we can reduce the grid to an $(n-2) \times (n-2)$ configuration and induct down. 3-4 endpoints in corners: Impossible. Just impossible. And it is easy to see by slightly annoying casework. We conclude. We finish from the last claim using a parity argument. Assume for contradiction that the center of the grid is not a path endpoint; we will show that each path has odd length. Note that the length of any path from one square to another square has parity opposite of that of the sum of the displacements in the $x$- and $y$-coordinates of the two endpoints of that path. Thus we have that the lengths of both paths are odd, which is impossible since the total of the grid is consequently even. Hooray!

Here's an alternative construction for considering diagonal end cells. Split the $2017 \times 2017$ grid into $\frac{2017 + 1}{2}$ frames $F_1, \dots, F_{1009}$, where the frame $F_i$ has length $2i - 1$. Each frame has four corners $A_iB_iC_iD_i$ going counterclockwise where $A_i$ is the top right corner. Let $A_1 = B_1 = C_1 = D_1$. Call a direct line in a path between two corners a cornerline. Claim: There is no white and black $2 \times 2$ checkerboard. Proof. This contradicts connectivity. $\blacksquare$ Claim: A cornerline $A_iB_i$ implies that the cornerline $A_{i-1}B_{i-1}$ is of the opposite color. Proof. Must follow as our path is not tree. $\blacksquare$ Claim: At least three corners of $F_{1009}$ must be the same color. Proof. FTSOC suppose there are two of each color. If $A_{1009}, C_{1009}$ are the same color and $B_{1009}, D_{1009}$ are the other color, then their paths must intersect, which can't happen. If $A_{1009}, B_{1009}$ are one color and $C_{1009}, D_{1009}$ are the others, then by the previous claim the cornerlines $A_{1009}B_{1009}$ and $C_{1009}D_{1009}$ are always opposite colors. However, since $2017$ is odd, this means that the center must be colored in both colors, contradiction. $\blacksquare$ WLOG let $A_{1009}, B_{1009}, C_{1009}$ all be black. Then we get that $A_i, B_i, C_i$ alternates colors as $i$ decreases and that the center cell is black as well. If the two cells above and to the right of the center cell aren't also black we are done, so suppose they are. Now considering repeatedly when $A_i$ is extended upwards and $C_i$ is extended rightwards. When these processes terminate, we get that two corners lie on the main diagonal $A_i, C_i$. Likewise, since $D_{1009}$ is white, we get the squares below and to the left are also white. This forces $D_{1008}$ to be black. We can repeatedly repeat this while $D_{1009-i}$ is not a corner. The same holds for considering $D_2, D_3, \dots$. Due to parity these proceses can't meet up, which gives us two other corners on the other diagonal $D_i$. However, if we checkerboard color the grid such that the cells along the main diagonals are green, then both paths contain one more green cell than non-green cell, contradiction.