Arranging cards in rows

Question

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?

Answer 1

Yes. They are.

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.

Answer 2

Yes, the cards are still in increasing order from left to right after the second step.

Here is the proof : We basically need to prove that after the 2 rearrangements have taken place, for all values of x and y,

For any row x , card in column y+1 >card in column y.

That is, for example, card in row 5 column 4 > card in row 5 column 3,etc.

I will prove this by the following example to make it easier to understand .

Example : Let us look at row 3 column 1 and 2 after the first rearrangement. Let us call the card in row 3 column 1 as m and card in row 3 column 2 as n . clearly n > m.

Now,let us do the second rearrangement. Let us say that m is in row 4 after the second rearrangement. If we can prove that no matter what, the card in row 4 column 2 now, is still greater than m, then we are done.

Case1 : n is also in row 4: Since , n> m , it is proved.

Case 2: n is above row 4: This means that the cards in row 4 column 2 ( let's call it o) will be greater than n. So o>m and hence, proved .

Case 3: n is below row 4:

Now, let us look at the cards in column 1. Let the card in column 1's row 1 be called A1, in row 2 be called A2, etc .

Also, let us look at these cards after the first rearrangement but before the second rearrangement. Let us call the corresponding cards of these cards present in column 2 as A1', A2', A3'...A10'. What this means is that after the first rearrangement but before the second rearrangement, A1 and A1' were present in the same row and in columns 1 and 2 respectively and so on.

Now, after the second rearrangement , at most 3 of A1',A2' and A3' can be present in column 2 in the first 4 rows. We also know that n ( also called A4') is not present in the top 4 rows. This means that one of A5',A6', A7'...A10' has to be present in the top 4 rows in column 2. Now m ( also called A4) is smaller than A5, A6...A10 . This means that m is also smaller than A5',A6'...A10' . Let us assume that it is A5' that is present in these top 4 rows .

Case a) A5' is present in row 4(the same row as m ). We already know that A5' is greater than m . Hence, proved.

Case b) A5' is present in a row above row 4 . This means that the card in row 4 column 2 will be even bigger than A5'(let's call this card p) . p> A5'> m. Hence, proved .

We have, therefore, proved that for all the possible scenarios, the card in row 4 column 2 is greater than the card in row 4 column 1. We can generalise this to prove that, after the second step, for all x and y, card in row x column y+1 > card in row x column y.