Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  AJ Henderson Aug 4 at 20:42
    
@AJHenderson, 0? What does mean "completely" sorted order? –  klm123 Aug 5 at 5:01
    
@klm123 - numbered 1 through 60, in order from top left to bottom right. –  AJ Henderson Aug 5 at 5:09
1  
@AJHenderson, well, if they are not completely sorted after 1 and 2, repetitions of 1 and 2 changes nothing. –  klm123 Aug 5 at 20:57

1 Answer 1

up vote 7 down vote accepted

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.