n x n square and strawberries

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

n x n square and strawberries

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2006, Combinatorics 4, AIMO 2007, TST 4, P2

The post below has been deleted. Click to close.

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

1145 posts

#1 h Jun 28, 2007, 6:11 PM • 5 Y

Y by artsolver, centslordm, Adventure10, ImSh95, and 1 other user

A cake has the form of an $n$ x $n$ square composed of $n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$ .

Let $\mathcal{B}$ be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement $\mathcal{B}$ than of arrangement $\mathcal{A}$ . Prove that arrangement $\mathcal{B}$ can be obtained from $\mathcal{A}$ by performing a number of switches, defined as follows:

A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

This post has been edited 1 time. Last edited by djmathman, Jun 27, 2015, 12:11 AM
Reason: slight wording changes

Z K Y

The post below has been deleted. Click to close.

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

481 posts

iura

#2 h Jul 3, 2007, 1:55 PM • 10 Y

Y by Giffunk, centslordm, ImSh95, Adventure10, bhan2025, and 5 other users

Let's change the condition to an analogous one: every grid rectangle with one vertex at the bottom right corner contains no fewer strawberries from $A$ than $B$ . We must prove we bring $A$ to $B$ by some switches.

Write $P\leq Q$ if every grid rectangle with one vertex at the bottom right corner contains no fewer strawberries from $Q$ than $P$ . Then $B\leq A$ . We prove that we can perform a switch such that $A$ goes to $C$ and $B\leq C$ and $C<A$ . We cannot perform infinitely many switches and thus we will end up with the arrangement $B$ of strawberries. Let's place $x$ instead of a strawberry on arrangement $A$ and an $o$ instead of a strawberry on arrangement $B$ . If $x$ coincides with $o$ we can remove the row and column containing them and reason by induction.

Note that if we have a rectangle $MNPQ$ with $M$ the lower-left corner and $x$ in $M,P$ then we can perform a switch in this rectangle unless there exists a point $K$ inside it (not on sides $NP,PQ$ ) such that the rectangle with one corner in $K$ and one in the bottom-left corner contains the same number of $x$ and $o$ .

Assume now that we cannot do any switch. We shall pick up a point $K$ containing an $x$ with the following property: the $o$ in the row of $K$ is to the left of $x$ and every $x$ or $o$ found in the row below $K$ . We prove that from each $K$ we may find a point $K'$ with the same property above $K$ . This will yield a contradiction, as we must stop. Note that to begin we just take the $x$ in the bottom row.

Let $O$ be the lower-left corner.

Pick up now such a point $K$ . Assume there is an $o$ in the point $L$ to the right of $K$ . Then the rectangle $R$ cornered in $O$ and with height $n$ and ending in the column of $L$ must contain the same number of $x$ as $o$ . It is easy to conclude from the property of $K$ that there exists an $o$ which is single in his row of rectangle $R$ , and it is above $K$ . Let it be the bottom one with this property. Say $o$ is in point $J$ . Then the $x$ in its row is to the right of $L$ . Say it is in point $H$ . We cannot exchange $K$ and $H$ . This means we can find a point $Z$ inside the rectangle cornered in $K$ and $H$ such that the rectangle cornered in $O$ and $Z$ contains an equal number of $x$ and $o$ . If this rectangle does not contain $L$ we might again choose an $o$ such that its row does not contain $x$ and thus repeat the step, only this time we will go down a row. So we cannot repeat this step indefinitely. Thus we can assume that the rectangle cornered in $O$ and $Z$ contains $L$ .
Let's then take the subrectangle of it whose top row contains $K$ . Start increasing the height of the rectangle. If we add an $x$ and no $o$ , then the position $x$ will be the desired position above $x$ . Thus we can add $x$ and $o$ or just an $o$ . If we would add an $o$ , we would contradict the assumption that $B<A$ . Thus we add an $x$ and an $o$ or no $x$ and no $o$ . If we add no $x$ and no $o$ it means the $x$ and $o$ in this row are farther to the right. Then $x$ is to the left of $o$ otherwise we would not have $B<A$ so we can take $x$ as the position we seek. So we add $x$ and $o$ every time. This is possible of course only then the rectangle has $n$ columns. But this is impossible, as the rectangle cornered in $Z$ must have stricly less columns than the rectangle cornered in $H$ , so less than $n$ . Contradiction.

QED

Z K Y

The post below has been deleted. Click to close.

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

827 posts

#3 h Dec 10, 2007, 2:18 AM • 6 Y

Y by a123, centslordm, Adventure10, ImSh95, khina, and 1 other user

Some background to this problem for those who are interested:

This setup given the problems gives a partial order on the symmetric group $S_n$ (the set of permutation of $n$ elements). This is in fact a well known order called the Bruhat order, which can be defined in general for Coxeter groups. The problem, then, is equivalent to a classic criterion for comparing two permutations in the Bruhat order of the symmetric group. For more information, see Combinatorics of Coxeter Groups by Björner and Brenti (in particular, the criterion appears as Theorem 2.1.5)

Z K Y

The post below has been deleted. Click to close.

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

16123 posts

JBL

#4 h Dec 10, 2007, 1:45 PM • 4 Y

Y by centslordm, Adventure10, ImSh95, and 1 other user

Someone's been doing his homework for Stanley's class

. (Unlike me ... bother!)

Z K Y

The post below has been deleted. Click to close.

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

4302 posts

#5 h Oct 24, 2011, 11:05 PM • 3 Y

Y by centslordm, ImSh95, Adventure10

Sorry if this is just equivalent to the stuff above, but...

Define the permutations $\sigma_A$ and $\sigma_B$ so that the strawberries in $A$ lie in squares $(i,\sigma_A(i))$ and those in $B$ lie in squares $(i,\sigma_B(i))$ (for $1\le i\le n$ ). (We use the matrix convention here for coordinates. Edit for clarification: $(x,y)$ is in the $x^{th}$ row and $y^{th}$ column, where $(1,1)$ is the upper left corner.) Let $[m]=\{1,2,\ldots,m\}$ for positive integers $m$ .

Noting that we can only perform finitely many operations on $A$ (the first row can only be finitely operated on, so after the first has been used up the second can only be finitely operated on, etc.), consider the following algorithm:

1. If $\sigma_A(i)\ge \sigma_B(i)$ for $1\le i\le n$ , then $\sigma_A=\sigma_B\implies A=B$ , so stop. Otherwise, take the smallest $1\le k\le n$ such that $\sigma_B(k)>\sigma_A(k)$ .

2. Because $\sigma_B(k)>\sigma_A(k)$ , the rectangle $[k]\times[\sigma_A(k)]$ , which contains at least as many strawberries in $B$ as in $A$ , must contain some $(j,\sigma_B(j))$ (where $1\le j\le k-1$ ) such that $\sigma_B(j)\le \sigma_A(k)<\sigma_A(j)$ (by the minimality of $k$ , $\sigma_B(i)\le \sigma_A(i)$ for all $1\le i\le k-1$ , so we need at least one $i$ to negate the effects of $\sigma_B(k)>\sigma_A(k)$ ).

3. We can now go back to step 1 with $\sigma_{A'}=\sigma_{A}\begin{pmatrix}j&k\end{pmatrix}$ , since each rectangle with a vertex at $(1,1)$ contains at least as many strawberries in $B$ as in $A'$ .

Indeed, suppose to the contrary that there exists a rectangle $[u]\times[v]$ that contains more strawberries in $A'$ than in $B$ . Since we simply moved strawberries from $(j,\sigma_A(j)),(k,\sigma_A(k))$ to $(j,\sigma_A(k)),(k,\sigma_A(j))$ , we cannot have $u\not\in[j,k)$ or $v\not\in[\sigma_A(k),\sigma_A(j))=[\sigma_A(k),\sigma_{A'}(k))=[\sigma_{A'}(j),\sigma_A(j))$ or else $A'$ and $A$ have the same number of strawberries in $[u]\times[v]$ (i.e. either neither exchange matters in the first place, or the exchanges cancel out), which is of course no more than the number $B$ has. On the other hand, if $j\le u<k$ and $\sigma_A(k)\le v<\sigma_A(j)$ , then by the minimality of $k$ (for all $1\le r\le k-1$ , $|A\cap\{r\}\times[v]|\le|B\cap\{r\}\times[v]|$ since $\sigma_A(r)\ge\sigma_B(r)$ ) and the fact that $\sigma_B(j)\le \sigma_A(k)=\sigma_{A'}(j)<\sigma_A(j)\le v$ ,
$\begin{align*} 0 &< |A'\cap[u]\times[v]|-|B\cap[u]\times[v]| \\ &=\sum_{r=1}^{u}|A'\cap\{r\}\times[v]|-|B\cap\{r\}\times[v]| \\ &=|A'\cap\{j\}\times[v]|-|B\cap\{j\}\times[v]|+\sum_{1\le r\ne j\le u}|A\cap\{r\}\times[v]|-|B\cap\{r\}\times[v]| \\ &\le|A'\cap\{j\}\times[v]|-|B\cap\{j\}\times[v]| \\ &= 1-1 \\ &= 0, \end{align*}$ a contradiction.

Because the algorithm cannot go on forever (as noted above, we can only perform finitely many operations on $A$ ), we're done.

This post has been edited 1 time. Last edited by math154, Dec 31, 2011, 12:23 AM

Z K Y

The post below has been deleted. Click to close.

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

148 posts

cwein3

#6 h Dec 30, 2011, 11:04 PM • 4 Y

Y by centslordm, ImSh95, Adventure10, Mango247

math154 wrote:

the rectangle [k]\times[\sigma_A(k)], which contains at least as many strawberries in B as in A, must contain some (j,\sigma_B(j)) (where 1\le j\le k-1) such that \sigma_B(j)\le \sigma_A(k)<\sigma_A(j) (by the minimality of k, \sigma_B(i)\le \sigma_A(i) for all 1\le i\le k-1, so we need at least one i to negate the effects of \sigma_B(k)>\sigma_A(k)).

It might just be me reading this incorrectly, but isn't $\sigma_{A}(k)>\sigma_{A}(j)$ necessary for a switch to occur if $k > j$ ?

Z K Y

The post below has been deleted. Click to close.

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

49 posts

Stens

#7 h Mar 29, 2017, 7:28 PM • 4 Y

Y by centslordm, ImSh95, PROA200, Adventure10

I think this is slightly different: Let row number $i$ counted from the bottom have height $i$ . Given an arrangement $\mathcal{C}$ , we define the height of each column as the height of the row that the strawberry in that column lies in. For example, if strawberries cover the bottom left-top right diagonal, the columns read from left to right have heights $1,2,3,\dotsc,n$ respectively. If we label the columns from left to right as $1,2,3,\dotsc,n$ , we see that the allowed operation is equivalent to exchanging two columns, where the first one has lower height than the second, and such that there are no strawberries in the rectangled formed by the strawberries.

We now show that you can place the columns in the correct place one by one: Take the first column in $\mathcal{B}$ , with height $h$ . If the first column in $\mathcal{A}$ also has height $h$ - then great, we can go on to the next column in $\mathcal{B}$ . If not, there is some column $i>1$ in $\mathcal{A}$ with height $h$ . We want to move this to the first column by using the operation: If column $i-1$ in $\mathcal{A}$ has lower height than column $i$ , we can just swap these two columns. If the height of $i-1$ is greater than that of $i$ , we consider column $i-2$ (in $\mathcal{A}$ ), and then $i-3,i-4$ and so on, until we find a column $k<i$ with height smaller than $i$ (why is this guaranteed to happen?

). Then we can just swap columns $i$ and $k$ since there are no strawberries inside the rectangle their strawberries form. Repeat until we have brought the column that was in position $i$ to the first position.

Now just apply the same algorithm to the second column in $\mathcal{B}$ , and so on, until we have made $\mathcal{A}$ into $\mathcal{B}$ .

This post has been edited 1 time. Last edited by Stens, Mar 29, 2017, 7:28 PM

Z K Y

The post below has been deleted. Click to close.

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

Generic_Username

1088 posts

Generic_Username

#8 h Sep 21, 2017, 6:24 PM • 3 Y

Y by centslordm, ImSh95, Adventure10

We proceed by induction on $n,$ the base case $n=1$ being trivial. Call a rectangle good if it's top left vertex corresponds to the top left vertex of the cake, and say a cake $X$ majorizes $Y$ if every good rectangle in $X$ has at least many strawberries as in $Y.$

Let the strawberry in the first column of $\mathcal{A}$ have coordinate $y_A,$ and define $y_B$ similarly. Assuming that coordinates increase from left to right and from down to up, it is evident that $y_B \geq y_A,$ since otherwise the $1 \times y_A$ good rectangle in $\mathcal{B}$ contains no strawberries while the one in $\mathcal{A}$ does.

If $y_A=y_B,$ we may simply remove the first column and row $y_A$ and finish by the inductive hypothesis in the remaining $n-1\times n-1$ matrix. The premises still hold, as each row/column has exactly one strawberry and every good rectangle in $\mathcal{B}$ still majorizes its counterpart in $\mathcal{A}$ (the strawberry in the removed row/column is in both good rectangles or neither).

Now assume $y_A < y_B.$ Consider the rectangle with corners $(1,y_A), (n,y_B)$ and the following algorithm:
- Let $(x, y_C)$ be a strawberry such that $y_A < y_C \leq y_B$ and $x$ is minimal.
- Perform a switch on $(1,y_A), (x,y_C).$ Now the strawberry in the first column is at $(1,y_C).$
- Repeat in the rectangle with corners $(1,y_C), (n,y_B).$

Clearly such a strawberry $(x,y_C)$ exists since there must be a strawberry in every row + well ordering principle. Furthermore, by minimality of $x,$ there is no strawberry in the rectangle with corners $(1,y_A), (x, y_C).$ Thus a switch is always possible. Finally, this algorithm clearly terminates, as $\{y_C\}_i$ is an increasing sequence bounded by $y_B.$ We have shown that this algorithm successfully moves the strawberry in the first column to its desired location in $\mathcal{B}.$ Let $\mathcal{A}'$ be the resulting cake after this algorithm. It remains to show that the matrix obtained by removing column $1$ and row $y_B$ in $\mathcal{A}'$ is majorized by its counterpart in $\mathcal{B}$ by the inductive hypothesis.

Evidently, majorization is transitive. Thus, since $\mathcal{B}$ majorizes $\mathcal{A}$ after deletion, it suffices to show that $\mathcal{A}$ majorizes $\mathcal{A}'$ after deletion. Indeed, note that the $y$ coordinate of an arbitrary strawberry that undergoes a switch can only decrease in the new configuration, which can, in turn, only decrease the number of strawberries in each good rectangle. We may now conclude.

This post has been edited 1 time. Last edited by Generic_Username, Sep 21, 2017, 6:25 PM

Z K Y

The post below has been deleted. Click to close.

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

39 posts

#9 h Nov 11, 2017, 8:37 PM • 4 Y

Y by centslordm, ImSh95, Adventure10, Mango247

I am not sure but I think that there exist a stronger problem.We have a matrix A n*n and we have 0,1,-1.We know that in every line and column is a uniquely 1,-1.A switch is defined as permutation of 2 lines or columns.Prove that we can make finitely switches such as we arrive at a matrix -A.
Sorry for bad English.

Z K Y

The post below has been deleted. Click to close.

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

571 posts

#11 h Nov 12, 2017, 8:45 AM • 3 Y

Y by centslordm, ImSh95, Adventure10

Solution :

Consider the smallest (on inclusion) grid rectangle $P$ with one vertex on the top left corner and such that the number of strawberries in $P$ of $B$ $>$ then number of strawberries in $P$ of $A$ . So easy to check that there is a strawberrie in the bottom right vertex of $P$ in $B$ and no such strawberry in $A$ . Now there exist and a unique switch of $A$ such that a resulting matrix $A'$ will have a strawberry in the bottom right vertex of $P$ . Not hard to check that $A<A'\leq B$ . So reapiting this procedure we finally will get matrix $B$ . Done

This post has been edited 1 time. Last edited by Mosquitall, Nov 12, 2017, 8:46 AM

Z K Y

The post below has been deleted. Click to close.

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

571 posts

#12 h Nov 13, 2017, 1:43 PM • 4 Y

Y by centslordm, ImSh95, Adventure10, Mango247

I think that in my proof we also need to use next

$\textbf{Lemma :}$

A cake has the form of an $n$ x $n$ square composed of $n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$ .

A switch of $\textbf{type 1}$ consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Also define a switch of type $\textbf{type 2}$ that consists in selecting a grid rectangle with two strawberries (maybe not unique), situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Then for any switch $\sigma$ of $\textbf{type 2}$ there exist some switches $\sigma_1, \ldots ,\sigma_k$ of $\textbf{type 1}$ so that $\sigma = \sigma_1\sigma_2\ldots\sigma_k$ .

Z K Y

The post below has been deleted. Click to close.

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

1963 posts

ABCDE

#13 h Apr 1, 2018, 3:44 AM • 4 Y

Y by centslordm, ImSh95, Adventure10, Mango247

Put $A$ 's and $B$ 's in an $n\times n$ table to represent the locations of the strawberries. Note that if a cell contains both $A$ and $B$ , we can remove the row and column it is in and induct down. Hence, suppose that every cell contains at most one letter. We will describe a series of switches that will bring the $A$ in the first column to the $B$ in the first column, after which we may remove these strawberries and their row and column and induct down. Number the rows and columns from $1$ to $n$ , with $(1,1)$ at the top left corner. Suppose that the $A$ and $B$ in the first column are at $(i,1)$ and $(j,1)$ . By plugging in a cell $(x,y)$ , we mean to check the condition that the rectangle with top left $(1,1)$ and bottom right $(x,y)$ has at least as many $B$ 's as $A$ 's. Plugging in $(i,1)$ , tells us that $i>j$ . Define the shortcake zone of the cake as the cells $(x,y)$ with $j\le x<i$ . Let $(p,q)$ be a cell labeled with an $A$ in the shortcake zone with $q$ minimal. Then, we claim that performing a switch on $(i,1)$ and $(p,q)$ preserves the condition in the problem statement. Notably, any such switch decreases the size of the shortcake zone, so we eventually get $A$ and $B$ to coincide, as desired.

Now, let's prove the claim. Consider the function $f:\{1,2,\ldots,n\}^2\rightarrow\mathbb Z_{\ge0}$ with $f(x,y)$ defined as the number of $B$ 's minus the number of $A$ 's in the rectangle with top left corner $(1,1)$ and bottom right corner $(x,y)$ . Performing a switch on $(u_1,v_1)$ and $(u_2,v_2)$ with $u_1>u_2$ and $v_1<v_2$ decrements $f(x,y)$ by 1 if $u_2\le x<u_1$ and $v_1\le y<v_2$ and does not change $f(x,y)$ otherwise. The condition is equivalent to $f(x,y)\ge0$ for all $(x,y)$ , so it suffices to show that $f(x,y)\ge1$ for all $i\le x<p$ and $1\le y<q$ . Suppose that $f(x,y)=0$ for some $x,y$ in those intervals. In the first column of the rectangle with top left $(1,1)$ and bottom right $(x,y)$ , there is one $B$ . Hence, in order for $f(x,y)=0$ , there must be some column in the rectangle with an $A$ . This $A$ cannot be in the shortcake zone, as that contradicts the minimality of $q$ . Hence, there is at least one row above the shortcake zone. Now, let's check the condition for $(i-1,y)$ . We lose at least one $B$ going from the $(x,y)$ rectangle to the $(i-1,y)$ rectangle, namely $(i,1)$ . But we only lose cells in a part of the shortcake zone which by assumption has no $A$ 's, so $f(i-1,y)<0$ , contradiction. Hence, our algorithm works and we can match our strawberries.

Z K Y

The post below has been deleted. Click to close.

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

1298 posts

Kayak

#14 h Apr 23, 2018, 12:31 PM • 4 Y

Y by centslordm, ImSh95, Adventure10, Mango247

Please check my solution

(This is most probably similar to the solution of Stens or G_U)
Solution

Nubmer the rows $1, \cdots, n$ from up to down and the columsn $1, \cdots, n$ from left to right. Let $A[i][j]$ donote the cell at i-th column and j-th row. Also, if the rectangle condition holds, say $B$ muggawuggamugga's $A$ .

Claim - 1: Let the strawberry at $n$ th column of $A$ be at $i$ -th row, add the strawberry at $n$ -th column of $B$ be at $j$ -th row. Then $i \leq j$
Proof

Now, for a $n$ by $n$ grid $A$ , let $\text{Squeeze}(A)$ denote the $(n-1)$ by $(n-1)$ grid obtained by taking all the squares spanned by $[1][1]$ from the top left to the $[n-1][n]$ to the bottom right, and deleting the row having no strawberry.

Claim - 2 If $C$ muggawuggamugga's $D$ , then $\text{Squeeze}(C)$ muggawuggamugga's $\text{Squeeze}(D)$ .
(The proof is simple and a contradiction can't hold followsjust by taking cases on the squares above the deleted row in squares below the deleted row in both grids, and noticing where they maps when they're squeezed)

We proceed the final proof by induction on $n$ , the base case $n= 1, 2$ being trivial to check by hand. Assume it's true for all good (i.e satisfies the sudoku like stawberry distribution) $n-1$ by $n-1$ grids. We prove that it's true for all good $n$ by $n$ grids. Pick two $n$ by $n$ grids $A$ and $B$ where $B$ muggawuggamugga's $A$ .

First we need to change $A$ to a grid $A'$ such that $\text{Squeeze}(A) = \text{Squeeze}(A')$ and strawberry position at last column of $A'$ is the strawberry position at last column of $B$ . This following algorithm clearly works: (Let $i$ , $j$ denote the strawberry row position at last column of $A$ and $B$ respectively) (sorry this is more clear to write in this way rather than to write in words)

while (i <= j):
  switch A[n][i] and A[m_{i+1}][i+1] //the strawberry at (i+1)th row is at m_{i+1}th column 
  i += 1

Now, by the inductive hypothesis, there exists a sequence of switch which transforms $\text{Squeeze}(A')$ to $\text{Squeeze}(B)$ . Perform the sequence of moves, but if needed skip over the deleted row which was excluded in squeezing $A'$ (adding the deleted row back doesn't makes switching invalid, so this works). So we're done !

Z K Y

The post below has been deleted. Click to close.

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

1576 posts

#15 h Apr 24, 2019, 2:01 AM • 3 Y

Y by centslordm, ImSh95, Adventure10

First, we will represent each cake as a sequence of $n$ numbers, such that the $i$ th number represents the row in which the strawberry at column $i$ is in. Let the sequences of $\mathcal{A}$ and $\mathcal{B}$ be $S_A$ and $S_B$ respectively. The precondition of the problem implies that the $j$ th smallest number of the first $i$ numbers in $S_A$ is no less than that in $S_B$ , for all $1\le i\le n$ and $1\le j\le i$ . Furthermore, a swap can be interpreted as interchanging two originally inverted elements of $S_A$ , as long as there exists no numbers between them which are numerically between them as well. This implies that we can swap two consecutive elements which are originally inverted - a move which we will refer to as bubbling. Finally, note that swapping preserves the precondition.

Now, as the validity of the problem's statement only depends on the relative magnitudes of the numbers in the sequence, we can actually induct on $n$ . Our base case of $n=1$ is trivial, so go immediately to the inductive step.

Suppose that $1$ is at position $a_1$ in $S_A$ and $b_1$ in $S_B$ . Now, by the precondition applied at $i=a_1$ , note that $b_1\le a_1$ , so we can just bubble $1$ up in $S_A$ to get it to the correct location. Now, as $1$ is in the correct position after the bubbling, there is no need to move it anymore. Also, there are no remaining elements which define intervals which include $1$ , so we can effectively ignore it for the remaining swaps. Finally, note that if we ignore the $1$ in both sequences, the remaining sequences of size $n-1$ still satisfy the precondition, so we can use the inductive hypothesis to swap the remaining elements to be in the same order as $S_B$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

308 posts

#17 h Jul 1, 2021, 12:23 PM • 2 Y

Y by centslordm, ImSh95

Let the coordinate of the top left, top right, bottom left corner be $(1,1),(1,n),(n,1)$ respectively.
Let the coordinates of the strawberries in $\mathcal A$ be $(1,a_1),(2,a_2),...,(n,a_n)$ and the coordinates of the strawberries in $\mathcal B$ be $(1,b_1),(2,b_2),...,(n,b_n)$ .

For any numbers $x_1,x_2,...,x_j$ and $i\leq j$ we let $\text{min}_i\{x_1,x_2,...,x_j\}$ be the $i^{th}$ smallest number among them.

Notice that
$\text{min}_i\{a_1,...,a_j\}\geq\text{min}_i\{b_1,...,b_j\}\hspace{20pt}(1)$ for all $1\leq i\leq j\leq n$ . Otherwise we can pick the rectangle with opposite vertices $(1,1),(j,\text{min}_i\{a_1,...,a_j\})$ , it contains $i$ strawberries in $\mathcal A$ but at most $i-1$ strawberries in $B$ , contradiction.

Moreover, notice that the switching condition just means switching $a_{m_1},a_{m_2}$ where $a_{m_1}<a_{m_2}$ and $m_1>m_2$ . We will prove by induction on $n$ that every two permutations $a_1,...,a_n$ and $b_1,...,b_n$ of a set $\{x_1,...,x_n\}$ satisfying $(1)$ , will satisfy the condition stated, that is $(b_1,...,b_n)$ can be obtained from $(a_1,...,a_n)$ through switching.

Indeed, obviously $a_1\geq b_1$ . Let $k$ be the smallest indices such that $a_k<b_k$ .
Now suppose $a_k$ is the $p^{th}$ smallest number among $a_1,...,a_k$ . Let
$A_1=\{\text{min}_i\{a_1,...,a_k\}:i> p\}$ and $A_2=\{\text{min}_i\{a_1,...,a_k\}:i\leq p\}$ define $B_1,B_2$ similarly.

Now, notice that $b_k\in B_1$ , therefore by pigeonhole principle there exists some $j$ such that $a_j\in A_1$ while $b_j\in B_2$ . We swap $a_k$ and $a_j$ . Let the sequence be $c_1,...,c_n$ .

Claim. $(1)$ still holds for the new sequence, that is
$\text{min}_i\{c_1,...,c_m\}\geq \text{min}_i\{b_1,...,b_m\}$ for all $1\leq i\leq m\leq n$
Proof.
Notice that $\{c_1,...,c_m\}=\{a_1,...,a_m\}$ unless $k\leq m<j$ . If $k\leq m<j$ then notice that $a_q\geq b_q$ for all $1\leq q\leq m$ , so it is obvious. $\blacksquare$

Therefore, we can continue to carry out this procedure, it is easy to see that it must end, and in that situation, the two sequences must be equal, so we are done.

This post has been edited 1 time. Last edited by mathaddiction, Jul 2, 2021, 10:37 AM

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#18 h Jul 1, 2021, 3:17 PM • 2 Y

Y by centslordm, ImSh95

Impose a coordinate system on the cake, with the top left corner square being $(1,1)$ , the bottom left being $(1,n)$ and the top right being $(n,1)$ . Refer to a rectangle with one vertex at the top left corner and the bottom right corner at the bottom right corner of square $(x,y)$ the " $(x,y)$ -rectangle". Now consider the position of the strawberry in each column in $A$ and $B$ . Call a strawberry an "up-berry" if the position in $B$ is higher than $A$ , a "down-berry" if the position is lower, and a "stay-berry" if the position is the same.
Now, I will present an algorithm for decreasing the number of down-berries, supposing that at least one exists. Suppose there exists some down-berry $S$ (for strawberry) that is at $(x,a)$ in $A$ and $(x,b)$ in $B$ , with $b>a$ . By considering the $(x,a)$ -rectangle and the $(x,a-1)$ -rectangle, it follows that there exists some up-berry to the left of $S$ that goes from $(x_1,a_1)$ in $A$ and $(x_1,b_1)$ for $B$ , where $a_1\leq b$ and $b_1\geq a$ . If $b_1<a$ , by considering the $(x,b_1)$ -rectangle and $(x,b_1-1)$ -rectangle, it then follows that there exists some up-berry located in a column to the left of $x_1$ that goes from $(x_2,a_2)$ to $(x_2,b_2)$ with $a_2\leq b_1$ and $b_2> b_1$ . Repeating this, we can come up with some sequence $s_1,s_2,\ldots,s_k$ of up-berries
$(x_1,a_1)\to (x_1,b_1),(x_2,a_2)\to (x_2,b_2),\ldots, (x_k,a_k)\to (x_k,b_k)$ such that $a_1\leq b,b_1\geq a,x_1<x$ and for $1<n\leq k$ , we have $a_n\leq b_{n-1}$ , $b_n>b_{n-1}$ , and $x_n<x_{n-1}$ . Then we can perform the swapping operation on $s_1,s_2$ , $s_2,s_3$ , and so on until we swap $s_{k-1}$ and $s_k$ . Then we swap $s_k$ and the down-berry $S$ . By the inequality chain, all these operations are legal, and in the resulting cake $s_1,s_2,\ldots,s_k$ remain up-berries whereas $S$ becomes either an up-berry or a stay-berry. This concludes the algorithm.

Now note that if there are no down-berries, there are clearly no up-berries either (since the sum of the "movements" up and down between $A$ and $B$ must be zero), so once we run the above algorithm enough times to arrive at no down-berries, there will be no up-berries either and we will have reached $B$ from $A$ . $\blacksquare$

This writeup is kinda bad because I rushed it. I don't think all of my inequalities are right but I'm too lazy to check. :maybe:

:maybe:

Hopefully you get the idea.

Z K Y

The post below has been deleted. Click to close.

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

170 posts

#19 h Apr 19, 2022, 4:37 PM • 2 Y

Y by ImSh95, Mango247

Mosquitall wrote:

I think that in my proof we also need to use next

$\textbf{Lemma :}$

A cake has the form of an $n$ x $n$ square composed of $n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$ .

A switch of $\textbf{type 1}$ consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Also define a switch of type $\textbf{type 2}$ that consists in selecting a grid rectangle with two strawberries (maybe not unique), situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Then for any switch $\sigma$ of $\textbf{type 2}$ there exist some switches $\sigma_1, \ldots ,\sigma_k$ of $\textbf{type 1}$ so that $\sigma = \sigma_1\sigma_2\ldots\sigma_k$ .

After we have this we can put the strawberry in the first row in it's correct position and induct down.

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1699 posts

awesomeming327.

#20 h Jun 1, 2023, 12:39 AM

Y by

There is a bijection from strawberry arrangements to permutations of $[n]$ . We biject in the following manner: Let $\sigma_i$ be one more than the number of cake squares above the strawberry on the $i$ th column from the left. For example, in the following arrangement, $\sigma=(\sigma_1,\sigma_2,\sigma_3,\sigma_4)$ is $(4,1,2,3)$ .

https://media.discordapp.net/attachments/986049049834713139/1113627762343813140/ISL2006C4.png?width=884&height=888

Call $\sigma$ the characteristic permutation of the arrangement. Let $\sigma(\mathcal{A}), \sigma(\mathcal{B})$ denote the characteristic permutations of $\mathcal{A}$ and $\mathcal{B}$ , and let $\sigma_i(A)$ be the $i$ th term of that sequence.

Let $f_{\mathcal{C}}(x,y)$ where $1\le x,y\le n$ and $\mathcal{C}$ is a strawberry arrangement be the number of strawberries in the rectangle that is $x$ long and $y$ tall. We see that $f_{\mathcal{C}}(x,y)$ is the number of values $i\le x$ such that $\sigma_i(\mathcal{C})\le y$ .

Suppose for some $i$ that $M=\text{max}(\sigma_1(\mathcal{A}),\sigma_2(\mathcal{A}),\dots, \sigma_i(\mathcal{A}))<\text{max}(\sigma_1(\mathcal{B}),\sigma_2(\mathcal{B}),\dots, \sigma_i(\mathcal{B}))$ then $f_{\mathcal{B}}(i,M)\le i-1$ because there's at least one that's greater than $M$ , and $f_{\mathcal{A}}(i,M)=i$ . This is a contradiction since the $x$ by $y$ rectangle then contains less strawberries of $\mathcal{B}$ than $\mathcal{A}$ . Therefore, we have $\text{max}(\sigma_1(\mathcal{A}),\sigma_2(\mathcal{A}),\dots, \sigma_i(\mathcal{A}))\ge \text{max}(\sigma_1(\mathcal{B}),\sigma_2(\mathcal{B}),\dots, \sigma_i(\mathcal{B}))$ for all $i$ .

A switch is taking two indices $i\le j$ such that $\omega_i\ge \omega_j$ and switching the values $\omega_i$ and $\omega_j$ . We claim that the above condition is sufficient to show that from $\omega(\mathcal{A})$ we can reach $\omega(\mathcal{B})$ from a series of such switches. We proceed by induction on $n$ . Clearly, the result is true for $n=1$ .

If there exists $i$ such that $\omega_i(\mathcal{A})=\omega_i(\mathcal{B})$ then we can ignore the index $i$ and subtract $1$ from each index $j>i$ and subtract $1$ from each value $x>\omega_i(\mathcal{A})$ and we are done by the induction hypothesis. Otherwise, there are no fixed points from $\omega_i(\mathcal{A})$ to $\omega_i(\mathcal{B})$ .

We have $\omega_1(\mathcal{A})>\omega_1(\mathcal{B})$ so we can switch $\omega_1(\mathcal{A})$ and $\omega_1(\mathcal{B})$ in $\omega_1(\mathcal{A})$ . The condition is still fulfilled since $\omega_i(\mathcal{A})$ only increases for $i\ge 2$ and there is a fixed point. We are done.

This post has been edited 1 time. Last edited by awesomeming327., Jun 1, 2023, 1:00 AM

Z K Y

The post below has been deleted. Click to close.

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

155 posts

#21 h Apr 3, 2025, 2:02 PM

Y by

It seems that my solution is different from others above, I’m not sure whether I fake-solve or not…….
Anyway, here is my solution, hope someone can. help me to check it

First, if arrangement $\mathcal{A},\mathcal{B}$ satisfies “every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement $\mathcal{B}$ than of arrangement \mathcal{A}”, then I’ll say arrangement $\mathcal{B}$ majorizes $\mathcal{A}$
Notice that when we conduct a “switch”, the new arrangement is always marized by the original arrangement

Back to the original problem, let’s induct on $n$ to show that for an arrangement $\mathcal{A}$ of strawberry in $n\times n$ square, we can perform a number of “switch” to obtain any arrangement majorizes it
For $n=1$ it is trivial. Now suppose the statement is true for $n=k$ where $k\geq 1$ is an integer, and we consider the case when $n=k+1$ :
In arrangement $\mathcal{A}$ , color the strawberry on the first row green
Notice that if an arrangement $\mathcal{B}$ majorizes $\mathcal{A}$ , the strawberry on the first row of $\mathcal{B}$ must to the left of the green strawberry in $\mathcal{A}$
So we “switch” the strawberry with the strawberry on left column one by one in $\mathcal{A}$ , until the green one has the same position as in the arrangement $\mathcal{B}$ .
Then, ignore the grids that are in the same row or same column with the green strawberry, and get a new $k\times k$ arrangement $\mathcal{A}’$
Notice that since every row or column only one strawberry so our “ignore” won’t affect our switch on $\mathcal{A}’$
Now from the induction hypothesis, we can perform a number of “switch” to obtain any arrangement which majorizes $\mathcal{A}’$ . After switching, add back the grids and strawberry we ignored.
Therefore, we can obtain any $(k+1)\times (k+1)$ arrangements which majorizes $\mathcal{A}$ , finish the induction step.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a