Subscribe via feed.

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


This post is under “Logic” and has 22 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

22 Responds so far- Add one»

  1. 1. Wizard of Oz Said:

    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?

  2. 2. slavy Said:

    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?

  3. 3. Wizard of Oz Said:

    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 . . .

  4. 4. DP Said:

    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.

  5. 5. DP Said:

    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?

  6. 6. cazayoux Said:

    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.

  7. 7. slavy Said:

    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?

  8. 8. Wizard of Oz Said:

    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.

  9. 9. slavy Said:

    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 :)

  10. 10. Wizard of Oz Said:

    Yes please.

  11. 11. slavy Said:

    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…

  12. 12. DP Said:

    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”.

  13. 13. Wizard of Oz Said:

    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.

  14. 14. slavy Said:

    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)!

  15. 15. Rajeev Singh Said:

    Hi,

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

  16. 16. DP Said:

    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”.

  17. 17. DP Said:

    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”.

  18. 18. slavy Said:

    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 :)

  19. 19. Wizard of Oz Said:

    Nice work in post # 14, Slavy!

  20. 20. DP Said:

    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.

  21. 21. Chris Said:

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

  22. 22. DP Said:

    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..

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0