2

The numbers from 1 to 50 are printed on cards. The cards are shuffled and then laid out face up in 5 rows of 10 cards each. The cards in each row are rearranged to make them increase from left to right. The cards in each column are then rearranged to make them increase from top to bottom. In the final arrangement, do the cards in the rows still increase from left to right?

-From Canadian Math Olympiad 1980

I played around with a few cases and the final arrangement did seem to increase from left to right, but is there any way to prove/disprove whether this will always be the case? I looked online but could not find any solutions.

1110101001
  • 4,188

1 Answers1

2

For $r=1,2,3,4,5$ and $c=1,2,\ldots,10$ let $n_{r,c}$ be the number in row $r$, column $c$ after the first rearrangement, so that $n_{r,c}<n_{r,c+1}$ for $r=1,\ldots,5$ and $c=1,\ldots,9$. Without loss of generality we may assume that the first column is in ascending order from top to bottom, so that $n_{r,1}<n_{r+1,1}$ for $r=1,2,3,4$: if not, swap whole rows until it is.

Now suppose that $n_{r,2}>n_{s,2}$, for some $r,s$ such that $r>s$. For $c=2,\ldots,10$ swap the cards $n_{r,c}$ and $n_{s,c}$; $n_{r,1}<n_{s,1}<n_{s,2}$, and $n_{s,1}<n_{s,2}<n_{r,2}$, so each row of the array still increases from left to right. Repeat this manoeuvre as often as necessary to bring column $2$ into ascending order from top to bottom.

Continue in similar fashion repairing one column at a time, working from left to right, making sure that when you swap two elements in a column, you swap the corresponding elements in every column to the right. After each such swap each row still increases from left to right, so this will still be the case at the end, when each column has been sorted into increasing order from top to bottom.

Brian M. Scott
  • 616,228
  • What happens if there is no $n_{r,2}$ that is $>n_{s,2}$ – 1110101001 Dec 23 '14 at 20:23
  • Also how can you guarantee that the result will hold even when the cards are not sorted in the manner described? The problem never specifies what technique is used to sort the cards, so don't you have to prove without relying on a specific sorting order? – 1110101001 Dec 23 '14 at 20:28
  • @1110101001: If there is no such pair, then the second column is already sorted correctly, and you move on to the third. \ Once the cards in each row are arranged to increase from left to right, there is only one arrangement in which each column increases from top to bottom. It makes no difference how you get there. – Brian M. Scott Dec 23 '14 at 22:13