City Square

Lemma For a Graph whose edges is directed.If every vertex‘s out-degree is not more than $k$ ,then we can use $2k+1$ colors to color all vertices,such that adjacent vertices are colored with different colors.

We use induction on the total number of vertices $n$ .

When $n≤2k+1$ ,let all vertices are colored with different colors.

If the conclusion of the $n-1$ was established, the following prove that it was also set up for $n$ .

∵Total number of edges is $nk$ and the sum of in-degree and out degree is $2nk$ at most.

∴Select the vertex $A$ with the minimum degree.Its degree is $2k$ at most.

For the remaining n-1 vertices,use the induction hypothesis.We can use 2k-1 colors to color them.

For vertex $A$ ,there are $2k$ points adjacenting to it.So there must be a color that is different from those of the adjacent points.

Color $A$ in this color.

Induction propositions are proved.

∴The conclusion is tenable for arbitrary $n$ .

Place the square in the problem as a point;place the one-way traffic as directed edge.Get graph $G$

We construct $G'$ :The points in $G'$ and the poionts in $G$ is one one correspondence.When and only when the two points in the $G$ have path whose length is no more than 2 to the connection,these two points are connected in the $G'$ and are directed.

So,each point's out-degree in $G'$ is $6$ at most.

For the lemma,we can ues $2 \times 6+1=13$ colors to color every points in $G'$ such that adjacent vertices are colored with different colors.

Put the same color point in a set,we get $A_{1},A_{2}…,A_{13}$

Then,for the point in $A_{i}$ ,starting from it to reach another point in the G with a step or two steps is not in $A_{i}$ .

For each set $A_{i}$ ,in accordance with the two "out" direction adjacent vertices to each point of the set to group.

Two "out" direction adjacent vertices in $A_{j}$ , $j≠i$ , in the same time, there are 12 kinds. Two "out" direction adjacent vertices respectively in $A_{j}$ and $A_{k}$ , $i,j,k$ being not equal to each other,there are $\binom{12}{2}$ $=66$ kinds.

So get $13 \times (12+66)=\boxed{1014}$ kinds.

The following verify that this combination is satisfied.

①Two groups in $A_{i}$ at the same time.(May wish to assume $i=1$ )

No edge between any two points in this two group.It is satisfied.

②Two groups respectively in $A_{j}$ and $A_{k}$

If it is not satisfied,then $∃A,B∈A_{I},C,D∈A_{j},s.t.A→C,D→B$ .

Because $A,B$ in the same group, $B$ also points to point $E$ in $A_{j}$ .Then the length of path $D→B→E$ is 2,from $A_{j}$ to $A_{j}$ .Paradoxical!

∴The path between $A_{i},A_{j}$ is one-way.

Q.E.D