Bariz - Problem

math154

30.07.2013 20:54

First, since $a_{n,k}\le\cdots\le a_{2,k}\le a_{1,k}$, the $i$th `1' in the $k$th row of $f(C)$ is at $(k,a_{n+1-i,k}-k+i)$. (a) $C\in\mathcal{F}$ iff the $i$th `0's of the columns are nonincreasing iff there are no more `0's in the first $\ell$ columns of row $k_1$ than in each row $k_2>k_1$ iff there are no fewer `0's in the first $\ell$ columns of row $k_1$ than in each row $k_2>k_1$ iff the $i$th `1's of the columns are nondecreasing. But for fixed $i$, $a_{n+1-i,k}$ is strictly increasing in $k$, so $a_{n+1-i,k}-k+i$ is nondecreasing in $k$, as desired. (b) We already know the $i$th `1' in the $k$th row of $f(C)$ lies at $(i,a_{n+1-i,k}-k+i)$, but we really want to find $a'_{k,i}$, the position of the $i$th `0' in the $k$th row (of $f(C)$). The key is the following Lemma. Given a sequence of $M$ `0's and $N$ `1's (in any order), let $x_1<\cdots<x_M$ denote the positions of the `0's and $y_1<\cdots<y_N$ denote the positions of the `1's. (Define $x_0=y_0=0$ and $x_{M+1}=y_{N+1}=M+N+1$ by convention.) Then for fixed $1\le i\le N$, $y_i = t$ iff $i\le t\le i+M$ and $x_{t-i}+1\le t\le x_{t-i+1}-1$. Proof. We have $y_i=t$ iff there are exactly $t-i$ `0's in positions $1,2,\ldots,t-1$ iff $0\le t-i\le M$ and $x_{t-i}+1\le t\le x_{t-i+1}-1$. $\blacksquare$ By the lemma, we have $a'_{k,i} = t$ iff $0\le t-i\le n$ and \[ a_{n+1-(t-i),k}-k+(t-i) + 1 \le t \le a_{n+1-(t-i+1),k}-k+(t-i+1) - 1. \] For convenience, define $b_{k,i} = a_{k,i}-i \in [0,n]$ for $1\le k,i\le n$, so $C\in\mathcal{F}$ iff $b_{k,0} \le b_{k,1}\le \cdots \le b_{k,n} \le b_{k,n+1}$ and $b_{n+1,i} \le b_{n,i} \le \cdots \le b_{1,i} \le b_{0,i}$, where $b_{k,0}=b_{n+1,i}=b_{n+1,0}=0$ and $b_{k,n+1}=b_{0,i}=b_{0,n+1}=n$ by convention. Then for $1\le k,i\le n$, $b'_{k,i} = j$ iff $a'_{k,i} = j+i$ iff $0\le j\le n$ and $b_{n+1-j,k}+1 \le i\le b_{n-j,k}$. It will be convenient to work with $b'_{k,i} \ge j$ and $b'_{k,i} \le j$ separately. From the previous paragraph, we easily deduce (1) If $k\in[0,n]$, $i\in[1,n+1]$, and $j\in[0,n]$, then $b'_{k,i} \ge j$ iff $b_{n+1-j,k} \le i-1$. (If $k=0$, this is equivalent to $n\ge j$ iff $0\le i-1$; if $i=n+1$, to $n\ge j$ iff $b_{n+1-j,k} \le n$. If $1\le k,i\le n$, just consider the possible values $j,j+1,\ldots,n$ of $b'_{k,i}$.) (2) If $k\in[1,n+1]$, $i\in[0,n]$, and $j\in [0,n]$, then $b'_{k,i} \le j$ iff $b_{n-j,k} \ge i$. (If $k=n+1$, this is equivalent to $0\le j$ iff $n\ge i$; if $i=0$, to $0\le j$ iff $b_{n-j,k} \ge i$. If $1\le k,i\le n$, just consider the possible values $j,j-1,\ldots,0$ of $b'_{k,i}$.) Thus for $k\in[0,n]$, $i\in[1,n+1]$, and $j\in[0,n]$, $b'''_{k,i}\ge j$ iff $b''_{n+1-j,k}\le i-1$ iff $b'_{n-(i-1),n+1-j}\ge k$ iff $b_{n+1-k,n-(i-1)}\le (n+1-j)-1$. Similarly, for $k\in[1,n+1]$, $i\in[0,n]$, and $j\in[0,n]$, $b'''_{k,i}\le j$ iff $b''_{n-j,k}\ge i$ iff $b'_{n+1-i,n-j}\le k-1$ iff $b_{n-(k-1),n+1-i}\ge n-j$. We conclude that for $k,i\in[1,n]$, $b'''_{n+1-k,n+1-i} = n - b_{k,i}$ for $1\le k,i\le n$ (which in fact holds as long as $0\le k,i\le n+1$ and $(k,i)\ne(0,0),(n+1,n+1)$). Hence $b^{(6)}_{k,i} = b_{k,i}$ for all $k,i$, as desired.

Sung-yoon Kim

31.07.2013 21:30

JuanOrtiz

16.01.2014 20:53

I bashed this problem. I'm very sure there is an easier, nicer solution, but I couldn't find it. Here is my ugly solution.

(b) Notice that we know the location of 0s in each row of $C$, but we know the location of 1s in each row of $f(C)$. We want to know the location of 0s (not 1s) in each row of $f(C)$. This is the basic idea behind my solution of (b). We know the $i$-th 0 in the $k$-th row of $C$ is in column $a_{k,i}$. We also know that the $i$-th 1 in the $k$-th row of $f(C)$ is in column $a_{n+1-i,k}-k+i$. Therefore, considering the $k$-th row of $f(C)$, we will determine the location of the $j$-th 0. Before the first 1 there are $a_{n,k}-k$ 0s, between the first and the second there are $a_{n-1,k}-a_{n,k}$ 0s, ..., between the $(n+1-i)$-th and the $(n-i)$-th there are $a_{i,k} - a_{i+1,k}$ 0s. So if the $j$-th 0 is between the $(n+1-i)$-th 1 and the $(n-i)$-th 1, then $i$ is the maximum number such that $a_{i,k}-k \ge j$, and the $j$-th 0 is in column $n+j-i$. Therefore, the $j$-th zero of the $k$-th zero of $f(C)$ is in column $n+j-l$ where $l$ is the maximum number such that $a_{l,k}\ge j+k$. We use the notation: “max $l$ s.t. $a_{l,k}\ge j+k$”. We also denote $b_{k,i}=a_{k,i}-i$ for all $k,i$. Finally, we denote $f(b_{k,i})$ as $b_{k,i}$ but taken in $f(C)$ (we use $f(f(b))$ when referring to $f(f(C))$, $f(f(f(b)))$ when referring to $f(f(f(C)))$, and so on). We get a very important formula: $f(b_{k,j}) =$ min $l$ s.t. $b_{n-l,k} \ge j$. Now, using the formula two more times, we get $f(f(b_{k,j}))=$ min $l$ s.t. min $x$ s.t. $b_{n-x,n-l} \ge k$ satisfies $x \ge j$ $f(f(f(b_{k,j})))=$ min $l$ s.t. min $x$ s.t. min $y$ s.t. $b_{n-y,n-x} \ge n-l$ satisfies $y \ge k$ satisfies $x \ge j$ Now, we prove $f(f(f(b_{k,j})))=n-b_{n+1-k,n+1-j}$. First, we prove $f(f(f(b_{k,j})))= A$ is impossible if $A \le n-1-b_{n+1-k,n+1-j}$. To do this, consider any $l \le A$ and take $x=j-1$. Clearly min $y$ s.t. $b_{n-y,n-x} \ge n-l$ satisfies $y \ge k$ is impossible, since this would make $x$ work but also $x \textless j$. So there exists a $y \textless k$ such that $b_{n-y,n-x} \ge n-l$. But since $b_{a,c}$ does not decrease as $a$ decreases, clearly $y=k-1$ must satisfy $b_{n-y,n-x} \ge n-l$. This implies $b_{n+1-k, n+1-j} \ge n-l \ge n-A \ge 1+ b_{n+1-k,n+1-j}$ which is impossible. Now we prove $l= n-b_{n+1-k,n+1-j}$ works. This will guarantee $f(f(f(b_{k,j})))=n-b_{n+1-k,n+1-j}$. To do this, we must prove min $x$ s.t. min $y$ s.t. $b_{n-y,n-x} \ge n-l$ satisfies $y \ge k$ satisfies $x \ge j$ Suppose not. Then $x \le j-1$ exists such that min $y$ s.t. $b_{n-y,n-x} \ge n-l$ satisfies $y \ge k$ But taking $y=k-1$ gives $b_{n-y,n-x} \ge b_{n+1-k, n+1-j} = n-l$ since $b_{a,c}$ does not increase as $c$ decreases. We therefore get a contradiction. Finally, we have proved $\boxed{f(f(f(b_{k,j})))=n-b_{n+1-k,n+1-j}}$. This implies $f^3(C)$ equals $C$ reflected across its center. Therefore $f^6(C)$ equals $C$ itself, and we’re done.

EDIT: Author of the problem, I have read your hint. I will try to find the nice solution and post it here.

McTeague

23.07.2016 15:23

Some of this may be less rigorous. We will be concerned with lattice cubes in $[0,n]^3$. For $x,y \in \{0,1,\ldots, n-1\}$, let $s(x,y)$ denote the lattice square in the $xy$-plane with vertices $(x,y), (x+1,y), (x,y+1), (x+1,y+1)$. Define $c(x,y,z)$ analogously for lattice cubes. Define an $\bold{n-slope}$ $M$ to be a collection of lattice cubes in $[0,n]^3$ together with the intersection of $[0,n]^3$ with the planes $x=n, y=n, z=0$ such that: if $c(x,y,z) \in M$ with $z \ge 1$, then $c(x,y,k) \in M$ as well for all $k \in \{0,\ldots,z-1\}$ if $c(x,y,z) \in M$ with $z \le m-2$, then $c(x+1,y,z) \in M$ (if $x \le n-2$) and $c(x,y+1,z) \in M$ (if $y \le n-2$).

Lemma $1$: There is a $1$-to-$1$ correspondence between tables $C \in \mathcal{F}$ and $n$-slopes.

We can "flatten" a $3D$ $n$-slope to a $2D$ tessellation of rhombuses forming a hexagon in a natural way (less rigorous again -- sorry). From such an $n$-slope, we can also color the faces parallel to the $xy$-plane in green, to the $yz$-plane in yellow, and to the $zx$-plane in blue (as in the AoPS logo). From such a hexagon in $2D$, we can "pull" it to an $n$-slope using the same convention of colors for rhombuses. (It's a bit of an optical illusion giving different $3D$ structures depending on which color appears on the tops of the cubes. Again, see the AoPS logo.) Lemma $2$: If $M$ is the $n$-slope corresponding to a table $C$, then the $n$-slope corresponding to $f(C)$ is is obtained by flattening $M$, rotating clockwise by $60^{\circ}$, and pulling back to an $n$-slope such that, instead of the above description, blue corresponds to faces parallel to the $xy$-plane, green to the $yz$-plane, and yellow to the $zx$-plane.

From the lemmas and the geometry of $n$-slopes, it becomes clear that $f(C) \in \mathcal{F}$ as well. As said in the intuition, the bijection and this interpretation of $f$ then imply that $f^{(6)}(C) = C$, as a rotation by $360^\circ$. (There may be a way of using the rotation idea without dealing with $3D$ structures, but I had trouble fitting in the condition $a_{1,i} \ge a_{2,i} \ge \cdots a_{n,i}$.)

v_Enhance

01.01.2019 09:30

Six years belated, here is a picture of the solution mentioned by the problem proposer and McTeague above. [asy][asy]size(11cm); pair O = (0,0); defaultpen(fontsize(7pt)); pair T(real x, real y, real z) { return x * dir(90) + y * dir(210) + z * dir(330); } real M = 10.5; transform t = shift(11,0)*rotate(-60); pair[] yrs = { // lower left corner of yellow rhombi // help T(0, 5, 0), T(0, 5, 1), T(0, 5, 2), T(0, 5, 3), T(0, 2, 4), T(1, 4, 0), T(1, 4, 1), T(1, 3, 2), T(2, 4, 0), T(2, 2, 1), T(2, 1, 2), T(3, 3, 0), T(3, 1, 1), T(3, 1, 2), T(4, 2, 0), T(4, 1, 1), // argh T(1, 0, 3), T(1, 0, 4), T(2, 0, 3), T(2, 0, 4), T(3, 0, 3), T(3, 0, 4), T(4, 0, 2), T(4, 0, 3), T(4, 0, 4), }; path yellow_rhombus = O--dir(90)--dir(30)--dir(-30)--cycle; for (int i=0; i<yrs.length; ++i) { filldraw(shift(yrs[i])*yellow_rhombus, paleyellow, black); filldraw(t*shift(yrs[i])*yellow_rhombus, paleyellow, black); label("$0$", t*shift(yrs[i])*(0.5*dir(30))); } pair[] grs = { // upper corner of green rhombi // help T(0, 2, 4), T(0, 3, 4), T(0, 4, 4), T(1, 4, 0), T(1, 4, 1), T(1, 4, 2), T(1, 3, 2), T(1, 4, 3), T(1, 3, 3), T(1, 2, 3), T(1, 1, 3), T(1, 0, 3), T(1, 1, 4), T(1, 0, 4), T(2, 3, 1), T(2, 2, 1), T(2, 2, 2), T(2, 1, 2), T(3, 3, 0), T(3, 1, 1), T(4, 2, 0), T(4, 0, 2), T(5, 1, 0), T(5, 0, 1), T(5, 0, 0), }; path green_rhombus = O--dir(210)--dir(270)--dir(330)--cycle; for (int i=0; i<grs.length; ++i) { filldraw(shift(grs[i])*green_rhombus, palegreen, black); filldraw(t*shift(grs[i])*green_rhombus, palegreen, black); label("$1$", shift(grs[i])*(0.5*dir(-90))); } pair[] brs = { // upper left corner of blue rhombi T(5, 3, 0), T(5, 4, 0), T(5, 5, 0), T(4, 4, 0), T(4, 5, 0), T(3, 5, 0), T(2, 5, 0), T(4, 1, 0), T(3, 1, 0), T(3, 2, 0), T(2, 2, 0), T(2, 3, 0), T(0, 2, 0), T(1, 0, 0), T(4, 0, 1), T(3, 0, 2), T(2, 0, 2), T(1, 0, 2), T(0, 0, 1), T(0, 1, 1), T(0, 4, 3), T(0, 3, 3), T(0, 2, 3), T(0, 1, 4), T(0, 0, 4), }; path blue_rhombus = O--dir(270)--dir(330)--dir(30)--cycle; for (int i=0; i<brs.length; ++i) { filldraw(shift(brs[i])*blue_rhombus, palecyan, black); filldraw(t*shift(brs[i])*blue_rhombus, palecyan, black); label("$0$", shift(brs[i])*(0.5*dir(-30))); label("$1$", t*shift(brs[i])*(0.5*dir(-30))); } label("Row $1$", T(5, 0.2, 0), dir(160)); label("Row $2$", T(5, 1.2, 0), dir(160)); label("Row $3$", T(5, 2.2, 0), dir(160)); label("Row $4$", T(5, 3.2, 0), dir(160)); label("Row $5$", T(5, 4.2, 0), dir(160)); label("Row $1$", shift(M+0.5,0)*T(5, 0.2, 0), dir(160)); label("Row $2$", shift(M+0.5,0)*T(5, 1.2, 0), dir(160)); label("Row $3$", shift(M+0.5,0)*T(5, 2.2, 0), dir(160)); label("Row $4$", shift(M+0.5,0)*T(5, 3.2, 0), dir(160)); label("Row $5$", shift(M+0.5,0)*T(5, 4.2, 0), dir(160)); label(scale(2)*"$C$", T(0, 5, 5), dir(-90)); label(scale(2)*"$f(C)$", shift(M+0.5,0)*T(0, 5, 5), dir(-90)); path ar = shift(2,-0.5)*T(0,5,5)--shift(M-1.5,-0.5)*T(0,5,5); draw(ar, EndArrow); label("Rotate cubes $60^{\circ}$", ar, dir(-90)); [/asy][/asy]

stroller

10.05.2020 04:30

took the word bash route instead of the algebra bash Generalization: Suppose we have a $m\times n$ rectangular grid of unit squares, in each square a $0$ or a $1$ is written such that the number of $0$ in every row is the same (say equal to $k$). Let $a_{ij}$ denote the $j$th square (counting from the left) containing $0$ in row $i$. Then make chains $C_j = (a_{mj} \to a_{m-1,j} \to a_{m-2,j} \to ... \to a_{2j} \to a_{1j})$ of $0$'s. We say that the table $C$ has property $\mathcal{F}$ if the arrows connecting adjacent members of $C_j$ never point leftwards and suppose $C\in \mathcal F$. $k$ bugs called $B_1,...,B_k$ initially rest in row $m$ and $B_i$ would move through all members of $C_i$. The bugs move for a total of $m+(n-k)$ times, each time moving simultaneously. A bug goes up when hitting $0$'s and go right when hitting $1$'s on the grid. All bugs start at $(0,0)$. The bug labelled $i$ ignores all $0$'s to the left of the member of $C_i$ in row $m$ but cares about $1$'s, in each step jumping to the closest $1$ to its right until reaching the first member of $C_i$, then going up. Thereafter, bug $B_i$ ignores any $0$ that is in any other chain and pretends they are $1$'s instead of skipping over them. After $B_i$ moves up from the final member in $C_i$, suppose there is still time left (i.e. $\le m+(n-k)$ moves have been made), then for the remainder of the time, the bug moves right as if it is on a $1$, despite being above row $1$ and outside the grid. Next we form $f(C)$ as an $m+(n-k) \times k$ table. Consider the sequence $s_i$ of Up/Right directions of moves made by $B_i$, there are $m+(n-k)$ such moves. In row $i$ and column $j$, write $0$ if the $j$th element of $s_i$ is Right and $1$ if it is Up. Prove that (a)' No two bugs ever collide on any $C\in \mathcal F$ (except at the beginning where they are all gathered somewhere to the left of the grid but on row $m$) (b)' $f^3(M)$ is the grid obtained by rotating $M$ around its center 180 degrees. We observe that $f(C) \in \mathcal F\iff$ (a)' is true, and (b)' would imply (b). The original problem is the case when $m=n/2=k$. In view of the process (a)' is pretty much by definition. We will prove (b)' by induction on the number of rows, $m$. When $k = 0$ there is nothing to prove. Suppose $k \ge 1$. For $m=1$ the verification is direct for any $k$ by the formula approach, say there are $t_i$ $1$'s between the $i-1$th and $i$th $0$, we can pin down the paths directly. Now suppose $m \ge 2$. Before we find the $f(C)$'s we will duplicate $C$ and delete its bottommost row, reducing the row by one. The bugs get bumped up to row $m-1$ and they move still according to the rules before. Call this new grid $C'$. After the first round of bug movements, $f(C')$ is the grid obtained by deleting the first $1$ in each row of $f(C)$ then aligning to the left (because deletion of first row results only in the removal of the first element from each of the direction sequences $s_i$). Thus $f(f(C'))$ is the grid obtained by deleting the first $0$ (since removal of the first $1$ in each row is equivalent to removal of the first right turn in each $s_i$ of $f(C)$), so $f^3(C')$ only loses the first row of $f^3(C)$. By induction hypothesis $f^3(C')$ is $C'$ rotated 180 degrees, so the rows $2\sim m$ of $f^3(C)$ are exactly the rows $1\sim m-1$ of $C$ flipped through the center. Likewise the rows $1\sim m-1$ of $f^3(C)$ are exactly rows $2\sim m$ of $C$ flipped through the center, from which (b)' follows. $\blacksquare$

YaoAOPS

25.04.2024 04:15

LOCAL SPAM. This sol is probably incomprehensible to someone who isn't me so here's an attached diagram. We can interpret $f$ as the following operation. Take diagonals $a_{1,i}, a_{2,i}, \dots, a_{n,i}$. For each element of the diagonal, map $a_{k,i} \to a_{k,i} - i + (n+1-k)$. This corresponds to fixing $a_{k,n+1-k}$ and "shearing" the other elements of the column based off their distance from this element. Then project this shifted diagonal into the $i$th row, and turn it all into $1$s. Claim: $f(C) \in \mathcal{F}$. Proof. For each $a_{i,j}$, write its elements in a grid to form a young tableaux which increases left to right and bottom to up. Then $f$ corresponds to following operations: first, adding \[ \begin{bmatrix} n-1 & \dots & 0 \\ \vdots & 0 & \vdots \\ 0 & \dots 0 & -(n-1) \end{bmatrix} \]to the young tableaux, which preserves the fact that it is a young tableaux. Then, it rotates the young tableaux, (so now it increases left to right and up to down), and replaces each row with the elements of $\{1, \dots, 2n\}$ not in that row preserving the left to right order. This fixes the up to down ordering, because the mex of the first $k$ elements of a higher row is higher. $\blacksquare$ Claim: $f(f(f(C)))$ rotates $C$ around its center $180^\circ$. Proof. We now induct on starting with $C$ having all zeros in a $n \times n$ right most, and moving them leftward, whic. Consider $f(C)$. Call each row of $f(C)$ a main controller. Call zeros in each main controller a main input, and the ones main controls. Order the main controllers such that the bottom one is first. Then consider $f(f(C))$, which we call based off colors. Initially, color each row of $f(f(C))$ a specific color $c_1, \dots, c_n$. Call these rows color rows. Color each main input based off its image in the rows (so the rightmost one has color $c_n$). Color the image of the zeros in $f(f(C))$ in these color rows in $f(f(f(C)))$ the same color (these would be columns, so from left to the right colors are $c_n, \dots, c_1$). Now, have each main input's image be called a color control. Call the zeros in $f(f(C))$ the color inputs, and call their images the color outputs. Also order the color inputs so the leftmost one is the "first" one. Note that this also orders the color outputs so the "first" one is in the first row. Order the zeros as $a_{n,1}, a_{n-1,1} \dots$ based off the earlier the diagonal and larger the row is. This is the order in which we will move them. Now, suppose what happens when we move $a_{n,1}$ to the left. This makes its image in the first main controller to move left, which moves the $c_n$ main input to the right. This main input corresponds to the $c_n$ color control in the $n$th row, moving that to the right. This moves the first color input to the left in the bottom row, which finally moves the top row $c_n$ color output in $f(f(f(C)))$ to the left, which means that the flipping of $a_{n,1}$ moves to the right as desired. Now, note that this changes the complete state in two ways: The next time we move the $c_n$ color control to the right, it actually moves the 2nd color input, which moves the 2nd color output. Mark this main input/color control as prepared. Now, suppose that we move $a_{n,1}$ again. This time, we end up moving the $c_{n-1}$ color controller, which at the end moves the top row $c_{n-1}$ color output to the left as desired. This means that we can move $a_{n,1}$ as many times as necessary, all in the first controller. Now consider moving $a_{n-1,1}$. As the condition has that $a_{n,1} \le a_{n-1,1}$, this means that we can only move $a_{n-1,1}$ at most the same number of times we moved $a_{n,1}$. This means that all the main inputs that $a_{n,1}$'s main control could swap with are prepared, which means that it all functions the same. We likewise can redefine the prepared controls to be the ones that $a_{n-1,1}$ interacted with so forth. At the end of all this, we've finished moving all of the $a_{i,1}$. Now consider moving the 2nd diagonal $a_{i,2}$. We can only move $a_{k,2}$ at most the same number of times we moved $a_{k,1}$. This guarentees that the color controls don't collide, and also means that the colors are likewise prepared for all elements of the second diagonal and all swaps. Repeating this for all $a_{i,j}$, we win. $\blacksquare$ Now, note that this implies applying $f^3$ twice finishes.

Attachments: