rows are DERANGED and a SOCOURGE to usajmo .

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

812 posts

#1 h Mar 21, 2024, 4:00 AM • 13 Y

Y by sixoneeight, meth4life2020, Danielzh, AtharvNaphade, ex-center, OronSH, alsk, pikapika007, megarnie, KevinYang2.71, qwerty123456asdfgzxcvb, crazyeyemoody907, ihatemath123

Let $n \geq 3$ be an integer. Rowan and Colin play a game on an $n \times n$ grid of squares, where each square is colored either red or blue. Rowan is allowed to permute the rows of the grid and Colin is allowed to permute the columns. A grid coloring is orderly if:

no matter how Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and
no matter how Colin permutes the columns of the coloring, Rowan can then permute the rows to restore the original grid coloring.

In terms of $n$ , how many orderly colorings are there?

Proposed by Alec Sun

This post has been edited 3 times. Last edited by GrantStar, Mar 21, 2024, 7:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GrantStar

812 posts

GrantStar

#2 h Mar 21, 2024, 4:00 AM • 7 Y

Y by thinkcow, bachkieu, OronSH, Sagnik123Biswas, KevinYang2.71, ihatemath123, lelouchvigeo

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

KevinYang2.71

392 posts

KevinYang2.71

#3 h Mar 21, 2024, 4:02 AM • 9 Y

Y by GrantStar, EpicBird08, Orthogonal., LostDreams, OronSH, megarnie, bjump, deduck, qwerty123456asdfgzxcvb

@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$

This post has been edited 3 times. Last edited by KevinYang2.71, Mar 22, 2024, 7:19 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi_is_3.14

1437 posts

pi_is_3.14

#4 h Mar 21, 2024, 4:11 AM

Y by

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

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatCatHead

27 posts

CatCatHead

#5 h Mar 21, 2024, 4:16 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MY-2

380 posts

MY-2

#6 h Mar 21, 2024, 4:21 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatCatHead

27 posts

CatCatHead

#7 h Mar 21, 2024, 6:52 AM

Y by

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

beibeizhu

98 posts

beibeizhu

#8 h Mar 21, 2024, 7:27 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

A_MatheMagician

2251 posts

A_MatheMagician

#9 h Mar 21, 2024, 11:41 AM • 1 Y

Y by fantasticcrow

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Danielzh

476 posts

Danielzh

#10 h Mar 21, 2024, 12:04 PM

Y by

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).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bachkieu

113 posts

bachkieu

#11 h Mar 21, 2024, 12:09 PM • 1 Y

Y by Danielzh

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

meduh6849

354 posts

meduh6849

#12 h Mar 21, 2024, 12:14 PM

Y by

will it be 5 or 2 points if no proof that the $n!$ cases work is provided
somehow forgot that :wallbash_red:

anyways basically gave up on JMO for this year

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vsamc

3783 posts

vsamc

#13 h Mar 21, 2024, 12:18 PM

Y by

meduh6849 wrote:

will it be 5 or 2 points if no proof that the $n!$ cases work is provided
somehow forgot that :wallbash_red:

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)

This post has been edited 1 time. Last edited by vsamc, Mar 21, 2024, 12:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peace09

5409 posts

peace09

#14 h Mar 21, 2024, 2:05 PM • 1 Y

Y by OronSH

The answer is $2(n!+1)$ , attained by and only by grids which are either uniform or are a permutation of a ``Sudoku." Clearly these work.* 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:
$[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)); 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); [/asy]$
Next, swap these rows. To revert, it is necessary and sufficient to swap the columns with $R_1$ and $B_1$ , so that the solid sections are the same in both columns:
$[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)); 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)); [/asy]$
Finally, swap the columns with $R_2$ and $B_2$ . To revert, there should exist a third row*
specifically, at least one -- more accurately, there should be two such row, one for each of the already existing rows -- but I omitted that in my solution as it isn't necessary
as shown, where the dashed sections are the same in both rows (in order to match the first row):
$[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]$
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$

This post has been edited 1 time. Last edited by peace09, Mar 21, 2024, 2:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

KevinYang2.71

392 posts

KevinYang2.71

#15 h Mar 21, 2024, 3:05 PM • 2 Y

Y by megarnie, deduck

vsamc wrote:

meduh6849 wrote:

will it be 5 or 2 points if no proof that the $n!$ cases work is provided
somehow forgot that :wallbash_red:

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7578 posts

asdf334

#17 h Mar 25, 2024, 10:32 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1730 posts

EpicBird08

#18 h Mar 27, 2024, 7:29 PM • 1 Y

Y by a_smart_alecks

Video solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

a_smart_alecks

51 posts

a_smart_alecks

#19 h Mar 28, 2024, 12:35 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bronzetruck2016

87 posts

bronzetruck2016

#20 h Mar 28, 2024, 12:49 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6857 posts

v_Enhance

#21 h Apr 6, 2024, 1:13 AM

Y by

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] 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]$
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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

666 posts

Shreyasharma

#22 h Apr 24, 2024, 6:55 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeguy856

7255 posts

awesomeguy856

#23 h May 5, 2024, 8:41 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cakeiswaybetterthancookie

190 posts

cakeiswaybetterthancookie

#24 h Jul 8, 2024, 2:47 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

300 posts

blueprimes

#25 h Aug 12, 2024, 9:57 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

somebodyyouusedtoknow

255 posts

somebodyyouusedtoknow

#26 h Dec 5, 2024, 9:16 PM

Y by

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

o1's response
Its argument for no other solutions is not acceptable, though.

o1's thinking process

Just curious what score would this solution obtain.

This post has been edited 2 times. Last edited by somebodyyouusedtoknow, Dec 5, 2024, 9:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

598 posts

eg4334

#27 h Mar 7, 2025, 4:44 AM

Y by

The answer is $2n!+2$ , which counts the two configurations of the same color, those with exactly one blue cell in each row/column, and those with exactly one red cell in each row/column. The latter two each have $n!$ clearly. The $n=3$ case can easily be manualyl checked so for the rest of this solution assume $n \geq 4$ .
Claim: Each row/column cannot have two or more of both colors.
Proof: Assume there was. Then its clear that when looking at some particular row there are at least $\binom{n}{2}$ conigurations that must appear in our original grid. But this exceeds $n$ always, which finishes.

These easily imply our originally mentioned constructions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#28 h Saturday at 6:00 AM

Y by

for no reason, i struggled to write a proper solution for this problem both in contest and right now :oops:

The answer is $\boxed{2 \cdot n!+2}$ achieved in the following configurations:

All squares are red or blue.
Each row and each column has exactly one red square.
Each row and each column has exactly one blue square.

All four of these colorings can easily be check to be orderly.

Let $R = (r_1, r_2, \dots, r_n)$ denote the number of red squares in each of the rows. It is easy to see that Colin cannot permute any of the values in $R$ . Hence, if any $r_i \neq r_j$ , Rowan could simply switch those two rows, and Colin would not be able to return the grid back to its original state. Hence, in any orderly coloring, the number of red squares in each row is equal, and an analogous argument shows that the number of blue squares in each column is equal as well. Suppose that there are exactly $k$ red squares in each row and column.

Consider an arbitrary column. Rowan can shuffle the rows of that column in $\tbinom{n}{k}$ ways. In order for Colin to be able to return the grid to its original coloring, this new permuation of the column must be equivalent to another column. Thus, Rowan can shuffle the rows in at most $n$ ways, which gives us $\tbinom{n}{k} \le n$ . It is clear that this is satisfied if and only if $k \le 1$ or $k \ge n-1$ , which provide all of the above constructions.

Z K Y