# Arranging cards in rows

This question appeared in an old math contest, and I seem to remember that the answer I had back when I first saw it was unsatisfactory.

You have a deck of cards numbered from $$1$$ to $$60$$. First, you shuffle them, and deal them out into six rows of ten cards each. Then, you do the following two things:

1. You rearrange the cards in each row so that they are in increasing order from left to right.

2. Then, you rearrange the cards in each column so that they are in increasing order from top to bottom.

Are the cards still in increasing order from left to right after the second step?

• An interesting variant of this would be to try to figure out what the largest number of possible times you could do this without having the cards back in completely sorted order. Aug 4 '14 at 20:42
• @AJHenderson, 0? What does mean "completely" sorted order? Aug 5 '14 at 5:01
• @klm123 - numbered 1 through 60, in order from top left to bottom right. Aug 5 '14 at 5:09
• @AJHenderson, well, if they are not completely sorted after 1 and 2, repetitions of 1 and 2 changes nothing. Aug 5 '14 at 20:57

1. Let's chose any 2 columns: $J$ and $I$, $1 \le J < I \le 10$.
2. After 1-st rearranging for any chosen card $C_{xI}$ in the column $I$ we have one card (more specifically: $C_{xJ}$) in the column $J$, which is smaller (has smaller number) than the chosen card. And each chosen card has it's own smaller card - different from the smaller card for the other cards at the column $I$.
3. After 2-nd rearranging for any chosen card $C_{RI}$ in the column $I$ and row $R$ has exactly $R-1$ cards in the column $I$, which are smaller than the chosen card. As we remember from item 2, each of those $R-1$ cards has at least one smaller card in the column $J$. Plus the same is true for the chosen card itself. And all these $R$ cards are different. Therefore the chosen card $C_{RI}$ has at least $R$ cards in the column $J$, which are smaller then it is.
4. Since cards in the column $J$ are sorted and $R$ smallest cards are in the rows $1,..,R$, then clearly $C_{RI}$ must be bigger then $C_{RJ}$.
5. So we proved that for any $J<I$ and $R$: $C_{RJ} < C_{RI}$. This is exactly what we were required to do.