Min of max and max of min

In how many ways can 9 distinct real numbers be arranged into an 3 × 3 3\times 3 array ( a i j ) (a_{ij}) such that max j min i a i j = min i max j a i j \displaystyle \max_j \min_i a_{ij} = \min_i \max_j a_{ij} ?


The answer is 108864.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Arturo Presa
Oct 10, 2015

There is no loss of generality in assuming that the numbers are 1 , 2 , 3 , . . . , 9. 1, 2, 3, ..., 9. It is easy to prove that for a given arrangement of the numbers into the 3 × 3 3\times 3 - array the condition max j min i a i j = min i max j a i j = b \max_j \min_i a_{ij} = \min_i \max_j a_{ij}=b is true if and only if the number b b is the maximum number of its row and the minimum of it column. The number b b is called the saddle point of the corresponding array or matrix. Whenever b b is the saddle point there are going to be two other numbers less than it on the same row and two other numbers greater than it on the same column. So the only possible saddle points are 3, 4, 5, 6, 7. Additionally, the way in which the 4 numbers that are not in the same row or column as the number b b can be placed does not change the fact that b b is going to be the saddle point. Then to form such an array we have to pick a place where the saddle point will be located, this can be done in 9 forms. When the saddle point is 3, the numbers in the same column and in the same row can be selected in P [ 2 , 2 ] P [ 6 , 2 ] P[2, 2]*P[6, 2] ways and the other 4 numbers in 4! When the saddle point is 4, using a similar reasoning, the other 8 numbers can be placed in P [ 3 , 2 ] P [ 5 , 2 ] 4 ! P[3, 2]*P[5, 2]*4! ways. When the saddle point is 5, the other 8 numbers can be located in P [ 4 , 2 ] P [ 4 , 2 ] 4 ! P[4, 2]*P[4, 2]*4! ways. When the saddle point is 6, there are going to be P [ 5 , 2 ] P [ 3 , 2 ] 4 ! P[5, 2]*P[3, 2]*4! ways of placing the other 8 numbers. Finally, when the saddle point is 7, there are going to be P [ 6 , 2 ] P [ 2 , 2 ] 4 ! P[6, 2]*P[2, 2]*4! ways of placing the other 8 numbers. Therefore the total number of possible arrangements will be 9 4 ! ( P [ 2 , 2 ] P [ 6 , 2 ] + P [ 3 , 2 ] P [ 5 , 2 ] + P [ 4 , 2 ] P [ 4 , 2 ] + P [ 5 , 2 ] P [ 3 , 2 ] + P [ 6 , 2 ] P [ 2 , 2 ] ) 9*4!*(P[2, 2]*P[6, 2]+P[3, 2]*P[5, 2]+P[4, 2]*P[4, 2]+P[5, 2]*P[3, 2]+P[6, 2]*P[2, 2]) = 108864. =108864.

Joe Mansley
Jun 5, 2021

Let's say that a number is mm iff it is the max-min and the min-max.

Call the number in the center x. x will be mm iff its horizontal neighbours <x and its vertical neighbours>x.

The probability of this is 1 / 5 2 / 4 1 / 3 = 1 / 30 1/5 \cdot 2/4 \cdot 1/3 =1/30

We can rearrange the rows/columns without changing the existence of an mm. So the probability of there being an mm is 9*1/30=3/10.

So the answer is (3/10)*9!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...