The answer is $2n!+2$. This achieved by The one configuration that's all red and the one configuration that's all blue The $n!$ configurations that have exactly $1$ blue in each row and column The $n!$ configurations that have exactly $1$ blue in each row and column It is easy to see that all of these work. Now, we show only these work. Claim: The amount of red cells in any row and column must be at most $1$ or at least $n-1$. Proof. The claim is clearly true for $n=3$. If $n>3$, then say there are $2\leq k \leq n-2$ red cells in some column. Rowan can then mix up the $n$ cells in that column in $\binom n k$ ways, each of which must appear as a column in the original coloring. But for $\binom n k\geq \binom n2 >n$ for $n>3$, a contradiction. $\blacksquare$ This means each column has $0,1,n-1,n$ red cells. If a column is fully red or fully blue, then Colin can move this column where ever he wants. No matter how Rowan permutes the rows now, this column is always a solid color. As Colin can move the original column any where, we conclude the whole grid is one color. Else, without loss of generality assume there is a column with exactly $1$ red square in it. Colin can then move this column anywhere, so like before, we conclude all columns have exactly $1$ red square. We easily eliminate the case of one all red row and one row with $n-1$ red squares as we can move the large row to any other row and get a contradiction. Thus each row and column has exactly $1$ red square in it as desired.

@above solution so simple why did i not think of that (i actually wrote this in contest) Let $G=(V,E)$ be the bipartite graph with bipartition $V=R\sqcup C$ where $R$ and $C$ are the set of rows and columns of the $n\times n$ grid, and $e=rc$ (with $(r,c)\in R\times C$) is an edge if and only if square $(r,c)$ of the grid is red. Assume $G$ is orderly. Then $\mathrm{Aut}(G)$ acts transitively on $R$ and $C$. Thus the degree of each vertex in $R$ is the same and the degree of each vertex in $C$ is the same. Since $|R|=|C|=n$, $G$ is regular, say $d$-regular. For all $r_1,r_2,r_3\in R$, we must have $|N(r_1)\cap N(r_2)|=|N(r_1)\cap N(r_3)|$ due to the transposition switching $r_2$ and $r_3$. It follows that $|N(r_1)\cap N(r_2)|$ is constant over all $r_1,r_2\in R$. Let this constant be $k_r$. Similarly, let $k_c$ be the constant such that $|N(c_1)\cap N(c_2)|=k_c$ for all $c_1,c_2\in C$. Fix a vertex $r\in R$. We double count $|E(N(r),R\setminus\{r\})|$. On one hand, each vertex in $N(r)$ has degree $d$ so $|E(N(r),R\setminus\{r\})|=d(d-1)$. On the other hand, each vertex in $R\setminus\{r\}$ has $k_r$ common neighbors with $r$ so $|E(N(r),R\setminus\{r\})|=k_r(n-1)$. Thus $k_r(n-1)=d(d-1)$. Similarly, $k_c(n-1)=d(d-1)$ so $k_r=k_c=:k$. Fix $r_1,r_2\in R$. Let \begin{align*} C_1&:=N(r_1)\setminus N(r_2)\\ C_2&:=N(r_2)\setminus N(r_1). \end{align*}In order to recover $G$, Colin's permutation $\sigma$ must map $C_1$ to $C_2$ and $C_2$ to $C_1$. If $k\ge d-1$ then $k=d-1$ or $k=d$ so $d\in\{0,1,n-1,n\}$. If $d=0$ or $d=n$ then $G$ is $\overline{K_{2n}}$ or $K_{n,n}$. Clearly these are orderly. If $d=1$ then $G$ is a matching of size $n$, which is orderly. There are $n!$ such matchings. If $d=n-1$ then $G$ is $K_{n,n}$ with the edges of a matching of size $n$ removed, which is orderly. There are $n!$ such graphs. So we may assume $k<d-1$. It follows that $C_1$ and $C_2$ are nonempty. Pick $v\in C_1$ and let $u:=\sigma(v)$. Since $R\setminus\{r_1,r_2\}$ is untouched, $N(v)\cap(R\setminus\{r_1,r_2\})=N(u)\cap(R\setminus\{r_1,r_2\})$. Thus $|N(v)\cap N(u)|=d-1>k$, contradicting the definition of $k$. Thus there are no orderly graphs in this case. Combining the above, there are $\boxed{2+2n!}$ orderly graphs. $\square$

is this right? way harder than the 2 above sol but I think should still work

I also get 2(n!+1) for n not equal 4, but I think when n=4, there will be more kinds, so I get 74 for n=4, different from others. Like brbb/rbbb/rrrb/rrbr for n=4

CatCatHead wrote: I also get 2(n!+1) for n not equal 4, but I think when n=4, there will be more kinds, so I get 74 for n=4, different from others. Like brbb/rbbb/rrrb/rrbr for n=4 If Rowan swaps the first and fourth rows this breaks I believe.

MY-2 wrote: CatCatHead wrote: I also get 2(n!+1) for n not equal 4, but I think when n=4, there will be more kinds, so I get 74 for n=4, different from others. Like brbb/rbbb/rrrb/rrbr for n=4 If Rowan swaps the first and fourth rows this breaks I believe. yeah, i mistake at this condition, so the answer is still 2(n!+1)

GrantStar wrote: It is easy to see that all of these work. if they take that, i dearly hope they'll take my "hurr durr bijection hurr durr use strings to tie exactly one row to exactly one column hurr durr it's obvious" - i had no idea how to rigorously prove it for the case where there's 1 red or 1 blue because it's so obvious

beibeizhu wrote: GrantStar wrote: It is easy to see that all of these work. if they take that, i dearly hope they'll take my "hurr durr bijection hurr durr use strings to tie exactly one row to exactly one column hurr durr it's obvious" - i had no idea how to rigorously prove it for the case where there's 1 red or 1 blue because it's so obvious here's the proof i put in my solution: For the all blue and all red coloring, the grid cannot change from its original coloring. WLOG, assume there is $1$ red square in each row/column (the proof for $1$ blue square is similar). No matter how Rowan permutes the rows, there will still always be $1$ red square in each row/column. Colin can take the column with the red square in the same row as the red square in the first row of the original coloring and move that column to the position of the first column. He then takes the column with the red square in the row that the red square in the second column of the original coloring and moves that column to the position of the second column, and so on. Thus, Colin can always restore the original coloring.

Will there be any deductions for just writing $1+n!+n!+1=2n!+2$ in terms of calculation for the number of coloring? No explanation for how there is only $1$ way or $n!$ ways (e.g. $n$ ways for the first column, $n-1$ ways for the second column, ..., $1$ way for the $n$th column).

@above probably not if you clearly state what you're counting. fun question tho

will it be 5 or 2 points if no proof that the $n!$ cases work is provided somehow forgot that anyways basically gave up on JMO for this year

meduh6849 wrote: will it be 5 or 2 points if no proof that the $n!$ cases work is provided somehow forgot that anyways basically gave up on JMO for this year I think that's a 5 or maybe a 6 if the graders are generous, that's not really the main idea of the problem and it's kind of easy to see that they all work, but it is a significant detail that shouldn't be glossed over (and it's not like completely trivial that all the n! configs work, although it is very easy to verify)

Necessity hinges on the following: Claim. No row or column can have both $\ge2$ $R$s and $\ge2$ $B$s. Proof. Suppose otherwise, and WLOG arrange them in a row in the order $R_1B_1R_2B_2$. We build up the grid as follows: First, swap the columns with $R_1$ and $B_1$. To revert, there should exist a second row as shown, where the dashed sections are the same in both rows:

as shown, where the dashed sections are the same in both rows (in order to match the first row): [asy][asy] label("$R_1$",(-3,1)); label("$B_1$",(-1,1)); label("$R_2$",(1,1)); label("$B_2$",(3,1)); label("$B$",(-3,-1)); label("$R$",(-1,-1)); label("$R$",(1,-1)); label("$B$",(3,-1)); label("$R$",(-3,-3)); label("$B$",(-1,-3)); label("$B$",(1,-3)); label("$R$",(3,-3)); draw((-4,1)--(-3.3,1),dashed); draw((-2.5,1)--(-1.5,1),dashed); draw((-0.5,1)--(0.5,1),dashed); draw((1.5,1)--(2.5,1),dashed); draw((3.5,1)--(4,1),dashed); draw((-4,-1)--(-3.3,-1),dashed); draw((-2.5,-1)--(-1.5,-1),dashed); draw((-0.5,-1)--(0.5,-1),dashed); draw((1.5,-1)--(2.5,-1),dashed); draw((3.5,-1)--(4,-1),dashed); draw((-3,-4)--(-3,-1.5)); draw((-3,-0.5)--(-3,0.5)); draw((-3,1.5)--(-3,2)); draw((-1,-4)--(-1,-1.5)); draw((-1,-0.5)--(-1,0.5)); draw((-1,1.5)--(-1,2)); draw((-4,-3)--(-3.3,-3),dashed); draw((-2.5,-3)--(-1.5,-3),dashed); draw((-0.5,-3)--(0.5,-3),dashed); draw((1.5,-3)--(2.5,-3),dashed); draw((3.5,-3)--(4,-3),dashed); [/asy][/asy] The $R$ and $B$ in corresponding sections of the solid sections give us a contradiction. $\square$ To finish, clearly there number of $R$'s in each of the rows and columns is a constant $c$, and the above claim implies that $c\in\{0,1,n-1,n\}$, which produces those and only those mentioned at the beginning. $\blacksquare$

vsamc wrote: meduh6849 wrote: will it be 5 or 2 points if no proof that the $n!$ cases work is provided somehow forgot that anyways basically gave up on JMO for this year I think that's a 5 or maybe a 6 if the graders are generous, that's not really the main idea of the problem and it's kind of easy to see that they all work, but it is a significant detail that shouldn't be glossed over (and it's not like completely trivial that all the n! configs work, although it is very easy to verify) If I used the graph theoretic solution, it is obvious matchings are orderly. Will i get a point deducted? (my sol is above)

me when i should have taken jmo 1) Notice that any column has at most $n$ permutations; otherwise, Rowan permutes column $c$ to $c'$ where $c'$ was not a column-coloring in the original figure. 2) Do the same for rows, do some basic logic since now your search space is hugely decreased, and finish.

Video solution

woah, i could've saved a lot of time with the epic inspirational $n\choose k$ bound instead of stumbling over my words with a worse and more verbose version of peace's solution... but at least i think my sol was correct and thats what matters!!!!! and even an hour of extra time probably wouldn't get me a single point on j6 btw as alec(ks) sun, i can confirm that i intentionally made the wording unclear to troll half of the jmo contestants

spent a page proving the n choose k bound because I and a bit silly and the graders probably wouldn't like it if I just said that it's obvious

Solution from Twitch Solves ISL: The answer is $2n!+2$. In fact, we can describe all the orderly colorings as follows: The all-blue coloring. The all-red coloring. Each of the $n!$ colorings where every row/column has exactly one red cell. Each of the $n!$ colorings where every row/column has exactly one blue cell. These obviously work; we turn our attention to proving these are the only ones. For the other direction, fix a orderly coloring $\mathcal A$. Consider any particular column $C$ in $\mathcal A$ and let $m$ denote the number of red cells that $C$ has. Any row permutation (say $\sigma$) that Rowan chooses will transform $C$ into some column $\sigma(C)$, and our assumption requires $\sigma(C)$ has to appear somewhere in the original assignment $\mathcal A$. An example for $n = 7$, $m = 2$, and a random $\sigma$ is shown below. [asy][asy] defaultpen(fontsize(14pt)); pen bo = black + 1.4; filldraw(shift(0,0)*unitsquare, lightcyan, bo); filldraw(shift(0,1)*unitsquare, lightred, bo); filldraw(shift(0,2)*unitsquare, lightcyan, bo); filldraw(shift(0,3)*unitsquare, lightcyan, bo); filldraw(shift(0,4)*unitsquare, lightred, bo); filldraw(shift(0,5)*unitsquare, lightcyan, bo); filldraw(shift(0,6)*unitsquare, lightcyan, bo); label("$C$", (0.5,0), dir(-90)); pen gr = deepgreen; real h = 8; draw((1,1.5)--(h,4.5), gr, EndArrow, Margins); draw((1,4.5)--(h,3.5), gr, EndArrow, Margins); draw((1,2.5)--(h,1.5), gr, EndArrow, Margins); draw((1,0.5)--(h,0.5), gr, EndArrow, Margins); draw((1,3.5)--(h,6.5), gr, EndArrow, Margins); draw((1,6.5)--(h,5.5), gr, EndArrow, Margins); draw((1,5.5)--(h,2.5), gr, EndArrow, Margins); filldraw(shift(h,0)*unitsquare, lightcyan, bo); filldraw(shift(h,1)*unitsquare, lightcyan, bo); filldraw(shift(h,2)*unitsquare, lightcyan, bo); filldraw(shift(h,3)*unitsquare, lightred, bo); filldraw(shift(h,4)*unitsquare, lightred, bo); filldraw(shift(h,5)*unitsquare, lightcyan, bo); filldraw(shift(h,6)*unitsquare, lightcyan, bo); label("$\sigma(C)$", (h+0.5,0), dir(-90)); label("$\sigma$", ((1+h)/2, 0), dir(-90), gr); [/asy][/asy] On the other hand, the number of possible patterns of $\sigma(C)$ is easily seen to be exactly $\binom{n}{m}$ --- and they must all appear. In particular, if $m \notin \{0, 1, n-1, n\}$, then we immediately get a contradiction because $\mathcal A$ would need too many columns (there are only $n$ columns in $\mathcal A$, which is fewer than $\binom{n}{m}$). Moreover, if either $m=1$ or $m=n-1$, these columns are all the columns of $\mathcal A$; these lead to the $2n!$ main cases we found before. The only remaining case is when $m \in \{0,n\}$ for every column, i.e.\ every column is monochromatic. It's easy to see in that case the columns must all be the same color.

Claim: All rows have the same number of red tiles. Proof. Obvious, as otherwise if Rowan permutes rows $i$ and $j$ with different numbers of red tiles, Colin can never return to the original configuration, because no matter how he moves row $j$ will always have a different number of tiles than it's starting configuration. $\square$ The same bound works for columns, so each row and column has the same number of elements from an easy double count. Now note that after any given move that Rowan makes, we require the columns to simply be a permutation of the original grid coloring. This occurs if and only if upon swapping any two rows, The two columns ``swap" upon such a switch The two rows are identical. If the first scenario occurs then each row can have at most $1$ colored tile, or at least $n - 1$ colored tiles, and this expands to the columns. In the second, this forces all rows to be identical, and all column's to be identical, which forces the entire grid to be colored. This is exactly the claimed solution set which can easily be observed to work by thinking of it as moving individual blocks. We are done.

My proof that the $k=1$ case works: There are $n!$ ways to permute either the rows or columns, each permutation being distinct There are $n!$ ways to color the grid such that each row and each column has exactly one red square Thus the original coloring is always achievable from any new coloring

I think this works???.... sombody please let me know. Answer: 2n!+2. Here is how we found the answer: An all-blue coloring An all-red coloring n! ways for there to be exactly 1 blue in each row/column n! ways for there to be exactly 1 blue in each row/column (I think) this is pretty easy to see and will not get explained further in the proof Now, lets prove these are the only cases that are possible. Claim : There is at most 1 red chip per row or at least n-1 red chips Supose that the claim is false and that there are other possbilities. Let's define k to the number of red chips in a row. k will be between 2 and n-2 chips(since we are assuming the claim is false and that indeed there are other possibles). There are n choose k ways to permute the chips in a given row. We know that n choose k is greater than or equal to n choose 2 which is greater than n for values of n greater than or equal to 3. So, there are not enough room to fit all the chips. Therefore, we are complete with the proof.

We claim the answer is $2n! + 2$, which counts the number of configurations where: All cells are red/blue, which counts $2$ configurations. Exactly one cell in each row/column are red/blue, which counts $2n!$ configurations. It can be verified that these work. Now we show these are the only ones. Since every row and column have an equal number of red cells, denote it by $k$. For $n = 3$, note that any value of $k$ is already classified in the configurations listed earlier, so we assume $n \ge 4$. For the sake of contradiction assume an orderly coloring satisfies $2 \le k \le n - 2$. Note that for a particular column, there are $\binom{n}{k}$ ways to change it, for which it must be a column in the original coloring. This implies the bound $$\binom{n}{k} \le n \implies n - 1 \le 2 \implies n \le 3$$which is a contradiction. Then we must have $k = 0, 1, n - 1, n$. These imply the constructions we described, so we are done.

o1 could actually get the right number for this problem. Runtime: 1m 2s

Its argument for no other solutions is not acceptable, though.

Just curious what score would this solution obtain.