## Who’s the tallest?

Posted by Chris on November 12, 2011 – 5:26 pm

In a rectangular array of people, who is taller?

the tallest of the shortest people in each column

or

the shortest of the tallest people in each row

Posted by Chris on November 12, 2011 – 5:26 pm

In a rectangular array of people, who is taller?

the tallest of the shortest people in each column

or

the shortest of the tallest people in each row

November 12th, 2011 at 11:35 pm

Line up each column in height order so that the shortest comes first and the tallest comes last. Then arrange the columns from left to right by height order of the first (i.e. shortest) member of each column.

Then the tallest of the shortest people in each column will be the tallest in the front row, i.e. the guy standing at the front of the rightmost column. The shortest of the tallest people in each row will be the shortest person in the rightmost column, i.e. the same guy.

So, the answer to the question is that it’s the same person each time. Neat, eh?

November 13th, 2011 at 2:53 pm

Even though there is a Yiddish saying “Better the best of the worst than the worst of the best” (just googled it – didn’t know it before), strictly mathematically speaking it is always the other way round – better be the worst in the city than the best in the village Sometimes the two levels coincide, as Wiz showed us on an example, but not that often. I think Wiz was actually provoking us to find his mistake, but instead of doing so, I would like to spice up the problem a bit. I noticed I had missed lots of probability fun, so let me ask a question I don’t know the answer of (haven’t thought about it so it could be easy or evil) – given a square array NxN of people of different height, what is the probability that the tallest of the shortest people in each column is also the shortest of the tallest people in each row?

November 14th, 2011 at 12:51 am

Thanks, Slavy. No need to point out my mistake. I found it all by myself.

By rearranging each column in height order the rows are no longer the same as they were at the start. So the tallest in each row will no longer necessarily be the same people as they were originally.

No problem with changing the order of whole rows or whole columns, but not individual elements within each column or row.

So, to address Slavy’s problem, I would say that his probability is the same as the probability of each column being in height order at the outset. That is 1 in N! for each of the N columns, or 1 in NxN! overall.

Just a guess . . .

November 14th, 2011 at 9:02 am

To answer the posted question, the tallest of the shortest people in each column is taller than (or possibly the same person as) the shortest of the tallest people in each row.

Responding to Wiz’s response to slavy’s probability problem:

The columns and/or rows don’t necessarily have to be arranged in the order you described. Here is an example where I put their “Heights” (1 through 16) “randomly” into a 4×4 table. The sums of each row and column are also shown.

04 01 05 06 – 16

09 02 08 07 – 26

11 10 16 15 – 52

13 03 12 14 – 42

__ __ __ __

37 16 41 42

In this situation, the Shortest column is the second. The tallest person is 10 units tall. The tallest row is the third. The shortest person is still 10 units tall…the same person.

November 14th, 2011 at 9:09 am

Wiz, you yourself said that it wouldn’t matter if you rearranged the rows or columns. Take my example table above and flip columns 2&3. Now flip rows 1&3……

You still get the same result.

Also, chris only said rectangular array, not the special square case. Should we maybe consider looking at NxM?

November 14th, 2011 at 9:36 am

The taller would be the shortest of the tallest people in each row.

Scenario 1, population 1 is each column

Scneario 1, population 2 is the shortest of each column

In other words, we’ve ignored the tallest X number of people from each column.

Scenario 2, population 1 is each row.

Scenario 2, population 2 is the tallest of each row.

In other words, we’ve ignored the shortest X number of people from each row.

If I’ve got to choose anyone from each scenario’s population 2, I’d rather it be from the second scenario.

November 14th, 2011 at 10:28 am

Hi DP. You can look at NxM matrices as well if you wish. I believe (at least hope) that I have the answer, and to generalize it from NxN to NxM is straightforward The solution is really elegant (maybe I am slightly biased here), so most probably the problem has been formulated long long time before me. Perhaps Chris knows better?

November 14th, 2011 at 12:52 pm

Yes, DP, I agree. If whole rows and whole columns can be moved around then that exposes my attempted “solution” to Slavy’s problem for the wild guess that it was . . .

I look forward to his real answer.

November 15th, 2011 at 1:49 pm

I don’t know if somebody is thinking on my problem, at all. I hope there is some interest, and it is too early to reveal the mystery. In case you need hints – let me know and I’ll provide them

November 15th, 2011 at 3:07 pm

Yes please.

November 15th, 2011 at 3:25 pm

The first hint won’t be a direct one. Try to realize that, since all the people have different heights (this is a crucial part of the problem) the tallest of the shortest people in each column is the same person as the shortest of the tallest people in each row IF AND ONLY IF there exists a column j and a row i, such that their intersection, the element a(i,j) is in the same time the tallest in the row i and the shortest in row j. Moreover, this element a(i,j) is exactly the person we are looking for.

Once understanding this, you have to see how to count all these matrices that possess such quality. Here the key observation comes again from the “if and only if” statement above. Once filling in the row i and the column j we don’t care about the rest of the matrix! No matter what happens there we already know we have equality and that the “special” person is on position a(i,j). The rest is not so deep combinatorics…

November 15th, 2011 at 4:02 pm

I think I’ve been thinking of Chris’s problem all wrong.

In my table (see post #4) I said that “10″ was the tallest of the shortest people in each column and the shortest of the tallest people in each row. That’s not really true.

the tallest of the shortest people in each column in my example is “6″.

the shortest of the tallest people in each row in my example is “6″.

So it still worked out that it is the same person. But I thought I was looking for the “shortest column” and then finding the tallest person in that column. We are instead finding the shortest people in each column, and then finding the tallest of all of them.

Becaues of this, I now change my answer to be “The shortest of the tallest people in each row is taller than the tallest of the shortest people in each column”.

November 16th, 2011 at 12:38 am

Hi Slavy,

What you seem to be saying is that having found the column that contains the tallest of the shortest people then somewhere in the matrix is the row that contains the shortest of the tallest people. There are N possible candidates in each column and in each row so you would think that the chances of a hit would be 1 in N^2.

That sounds a bit too simple.

November 16th, 2011 at 3:04 am

Hi Wiz,

no, it is definitely not that simple I don’t always look for the two “optimal” people and then check if they coincide. Such an approach is extremely hard computationally and I don’t think I am able to properly count the “good” cases there (i.e., those that give equality). What I did was to introduce a new property, that is easier to check and to “translate” the problem into its language. Now, the computations are straightforward:

I have an NxN matrix of people and let us denote their heights from 1 to N^2, respectively. Without taking into account any symmetries, we have N^2! different orderings of the people in the rows and columns of the matrix. Now, how to count the “good” cases? I need to fix the i-th row and the j-th column and just to fill them in appropriately. First of all I choose the entries of that row and column: we need N elements for the row, N elements for the column and since the person a(i,j) belongs to both of them we have 2N-1 elements in total. Those elements can be arbitrary among all the given ones, so we choose them via C(N^2,2N-1), where C(n,m)=n!/(m!(n-m)!) is the standard Newton binomial for computing the number of different m-tuples from a given n-tuple. Now, due to our criteria, we order those 2N-1 from the smallest to the biggest, so that the first N form the i-th row, and the last N form the j-th column. Each of the two groups can be permuted independently within themselves, leading to (N!)^2 different orderings. The position of the tallest element in the row is exactly j (the column we want to fix), while the position of the smallest element in the column is exactly i (the row we want to fix), and those two elements coincide and are the N-th tallest element among the chosen 2N-1. Hence, so far we fixed the i-th row, the j-th column and their elements. The rest N^2-2N+1 elements can be placed arbitrary at the remaining N^2-2N+1 still empty cells of the matrix, leading to (N^2-2N+1)! different outcomes each time the pair (i,j) has been fixed.

The previous paragraph gives rise to the following formula:

“Good” orderings = C(N^2,2N-1)*(N!)^2*(N^2-2N+1)!

= ((N^2)!*(N!)^2)/(2N-1)!.

Thus, the probability is “good”/”all” and equals to (N!)^2)/(2N-1)!

If the matrix was rectangular NxM, the answer is just N!M!/(N+M-1)!

November 16th, 2011 at 3:23 am

Hi,

This depends on situation that how the people stand in queue. In all cases shortest of tallest will be the taller or equal.

November 16th, 2011 at 8:54 am

Another note: In slavy’s NxN matrix, given no duplicate heights, the tallest that the “shortest of the tallest” could be is (N^2)-(N-1), and the shortest they could be is N. The shortest that the “tallest of the shortest” could be is N, and the tallest they could be is (N^2)-(N-1).

In an example, say we have a matrix where N=3. Number the elements 1 through 9 (where 1 through 9 represent their heights from shortest to tallest).

1 2 3

4 5 6

7 8 9

I don’t really care if we’re talking rows or columns, since you can just rotate this table 90 degrees and talk about it that way.

The tallest that the “shortest of the tallest” can be is (3^2)-(3-1) = 9-2 = 7. The shortest they can be is 3. And the shortest that the “tallest of the shortest” can be is 3, but the tallest they can be is 7.

So maybe I now switch my answer yet again. For Chris’s posted problem, it DOES matter if you are talking about columns or rows. Depending on how you rotate my table above, the answer will change. You can also rearrange the eolements in the matrix so that “the tallest of the shortest people in each column” is “the shortest of the tallest people in each row”.

November 16th, 2011 at 8:59 am

Well…that didn’t work very well. In my table above, the “3″ is both “the tallest of the shortest people in each column” and “the shortest of the tallest people in each row”. If you were to rotate my table, the “7″ would be the person we’re looking for.

Therefore, I go back to my last answer, with a small change:

“The shortest of the tallest people in each row is taller than or the same person as the tallest of the shortest people in each column”.

November 16th, 2011 at 9:30 am

Hi DP,

working with examples here just confuses you (I think). Let me give a very simple argument: denote by R(i) the tallest person in the i-th row, and by C(j) the shortest person in the j-th column. We have to compare min(over i) R(i) with max(over j) C(j). But for any pair (i,j), the i-th row and the j-th column intersect at some element a(i,j) and we have R(i) greater or equal to a(i,j) (since R(i) is the tallest guy in the row of a(i,j)), which in turn is greater or equal to C(j). Hence R(i) is always greater or equal to C(j) for arbitrary i and j, implying that the same holds for the minimum of the R(i) compared to the maximum of C(j). Moreover, in case of equality there is a certain i and j, such that R(i)=C(j) and this is possible iff R(i)=C(j)=a(i,j). This actually completes also the proof of the first part of my hint

November 16th, 2011 at 5:22 pm

Nice work in post # 14, Slavy!

November 18th, 2011 at 12:03 pm

This is strange. Usually Chris posts several times a day on all of the active problems. He especially like to post on his own threads, and will typically give away the answer quickly to discuss deeper items further. Like slavy has done.

It’s been several days and we haven’t heard from him. In fact, it has been since he posted this problem almost a week ago. I hope all is well.

November 18th, 2011 at 3:04 pm

Hi DP. I’ve been too busy. I’ll probably start posting tomorrow.

November 23rd, 2011 at 10:26 am

Any updates on this one?

I’m guessing slavy had it all along (post #2) that the shortest of the tallest will be the taller of the options.

I also tried out his ((N!)^2)/((2N-1)!) on a 2×2 grid, thinking I may be able to break it for small integers.

There are 24 arrangements, 16 of which meet the criteria stated in the problem. 16/24 = 2/3.

Using the formula: 2!^2/(2*2-1)! = 2^2/3! = 4/6 = 2/3.

It worked! Dang..