Who is the tallest?
(guys, this one drives me crazy ... and it was a fairly short trip ... :) )
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
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 Zaux at
9:50 PM
38 Comments:
just from reading this,Knightmare's brain broke again,and he sits slumped over the keyboard,drooling in a coma.
Knightmare ... this one boggles my imagination
I;m so glad you are able to post ... lots better than emailing them in ... right? .. :)
This post has been removed by the author.
Ragknot ...
I'm confused ... but it does ask which option is taller in the array
This post has been removed by the author.
the shortest of the tallest people in each row >= the tallest of the shortest people in each column
Cam
aha .. I see Ragknot ... you are right
Quick example, Imagine all rows and columns filled with 0 and 1.
Max of each row is 1. Min of all the 1s is still 1.
Min of each column is 0. Max of all the 0s is still 0.
1>0 thus min of max, is greater than max of min.
we can produce degenerate case where they are equal. i.e. set one column to be all of the same element.
Cam
Hi Cam ...
that is absolutely correct ....
are you going to explain your logic?
If I get time tomorrow .. or later today, that is ... I will post a logical solution
nice logical solution, Cam ... you continuously amaze me
I actually did it with a spreadsheet containing random numbers.
The shortest of the tallest is always greater than or equal to the tallest of the shortest.
I've posted the spreadsheet here on Google Docs, with three random examples.
unless someone really wants it, I will not post the published solution, because Cam's is so much more concise and definitely lots clearer
This post has been removed by the author.
I had to make a table of random numbers and examine it. It certainty looks like I was mixed up when I first read it.
See
http://ragknot.blogspot.com/2010/02/shortest-of-tallest-people-in-each-row.html
Oh, I know, I was thinking that two people were being selected from a random row and column. But after I began making a random table, I changed my mind, I had to two selections, one of rows and one of columns, then compare one from each group.
Ragknot ...
looked at your table... nice methodical approach
Hi Ross....
looked at your spreadsheet ... nice work man... you and Ragknot took a very similiar approach
I get the feeling that the question may have originally been posed in such a fashion that the shortest and tallest person in rows/columns is the same person.
For a x rows*y column table, the largest min. column value that could be achieved is the xth largest value. This can be constructed by having one column with the x largest elements in one column. The corresponding max values are the values in this column. The minimum of which is the xth largest element i.e. the largest min value possible is to equal the smallest max value.
For a x rows*y column table, the smallest max row value that could be achieved is the yth smallest value. This can be constructed by having one row with the y smallest elements in one row. The corresponding min values are the values in this row. The maximum of which is the yth largest element i.e. the smallest max value possible is equal to the largest min value.
As such the smallest max row value can never be less than largest column min value.(but they can be equal)
Cam
2nd paragraph "yth largest" should be "yth smallest"
Cam
My understanding is that e.g. in a given row, "the shortest" is
all the heights except the tallest one.
_1 _2 _3 _4
_5 _6 _7 _8
_9 10 11 12
13 14 15 16
Cols, tallest of shortest: 9,10,11,12
Rows, shortest of tallest: 2,6,10,14
In this case the tallest is the shortest of the tallest (14).
Now swap rows with columns (equivalent to swapping the words).
Rows, tallest of shortest: 3,7,11,15
Cols, shortest of tallest: 5,6,7,8
In this case the tallest is the tallest of the shortest (15).
The answer is that it depends on the values and the arrangement.
What have I misunderstood?
Chris,
The way I understand this is...
The taller of two guys.
1 Find the shortest in each column.
2 Find the tallest of this group.
This will be the first person
3 Find the tallest of each row
4 Find the shortest of this group.
This will be the second person.
The person found in #4 will be taller than the person found in #2
See my blog for a demo
http://ragknot.blogspot.com/
* the tallest of the shortest people in each column
(Steps 1 and 2)
or
* the shortest of the tallest people in each row
(steps 3 and 4)
Lets look at like this. We have an array of giants and drawfs. They are all mixed well enough that each row and each column have a few of each.
1. For each column (up and down) find the shortest person.
..... each will be a dwarf.
2. Find the tallest of these. He will still be a dwarf.
3. Find the tallest person in each row (left to right).
.... each of these will be a giant.
4. Find the shortest of these. He will be a giant.
Now compare the two people, which is taller, the giant or the dwarf.
The same will be true, even when the whole array is close to the average. The person found in step 4 will always be taller than the one found at step 2.
I found an exception.
It is possible that one person can be both the shortest person in a column, AND the tallest person in a row.
In this instance he can't be taller than himself. This possibility might easily happen in a small group, but could happen in even a large group, but the probability goes down with bigger groups.
I deliberately avoided random tables. I wanted to find a failing case. I succeeded on my first try. If I got it wrong, then please show me where.
In a special case like this, you have an exception.
This is like the exception I found.
_1 _2 _3 _4
_5 _6 _7 _8
_9 10 11 12
13 14 15 16
You will be comparing number 4 to himself.
He is both the tallest of his row and the shortest of his column.
He can not be taller than himself.
I don't think the maker of this thought about that.
Chris,
not sure what method you are trying but it should look like this
_1 _2 _3 _4
_5 _6 _7 _8
_9 10 11 12
13 14 15 16
Assume it is 1 to 16 shortest to tallest
shortest in each column
1,2,3,4
tallest of these=4
tallest in each row
4,8,12,16
shortest of these =4
4=4
tallest of shortest has not exceeded shortest of tallest.
Cam
The numbers are the heights. I've got to visit a customer. So won't post for at least 2 hours. I may be misunderstanding the question. (Which I secretly suspected all along).
This post has been removed by the author.
think the trick here is that you have rows and columns that will make two groups.
Group One is of columns, each column will have a shortest. Of these short people, one is the tallest, Let's call him the tallest dwarf.
Group Two is of rows, each row will have a tallest. Of these tall people, one is the shortest, Let's call him the shortest giant.
The person from group Two, will the short giant, and will be taller than the tall dwarf (unless he is the same person).
In my first post, I had looked at T of S and S of T over all rows and cols.
If is only one row/col.
_1 _2 _3 _4
_5 _6 _7 _8
_9 10 11 12
13 14 15 16
Using 9 as col/row definer.
Col: T of S is 9, Row: S of T is 10
So S of T > T of S
Swapping row/col =>
Row: T of S is 11, Col: S of T is 5.
So T of S > S of T
Again, no definite relation.
I can't think of any other interpretations of the question. So I conclude that there is no rule like T of S >= S of T or vice versa.
There are two distinct groups mentioned...Rows and Columns
1 "the tallest of the shortest people in each column"
2 "the shortest of the tallest people in each row"
For #1 the group is "the shortest in each column". After finding the shortest in each column, the tallest of these is the Person 1.
For #2 the group is "the tallest in each row". After finding the tallest in each row, the shortest of these is the Person 2.
The the final question is "which is taller".
The word that gave me a clue was taller, not tallest.
Although it's not definite, it did give me a clue that maybe it was comparing two people that was not the tallest or shortest, but a comparison of two people from two different groups.
The shortest of the tallest becuase he is still considered in the taller group
Ragknot. Re your 9:52 AM post. Thanks, I see what you mean. So using my table, the S group (by column) is 1,2,3,4 so 4 is the T of S. The T group (by row) is 4,8,12,16 and so the S of T is 4. So here S of T = T of S.
Swapping row/col => S = 1,5,9,13 and T of S = 13, and T = 13,14,15,16 so S of T is 13. Again have S of T = T of S.
OK I know accept that S of T >= T of S (having failed to find a counter example).
Methinks this was another English comprehension test. I may try for a proof now that I've understood the question.
I don't think you can get far with this question until you realize the difference in rows and columns. Rows have to be left to right and columns have to be up to down. If you try to swap rows with columns, there will be no distinct solution.
I think we all owe Chris a big hand of applause. Chris is almost always right in his first post. For him to change his mind, takes him up a notch in my mind.
Hi Ragknot, it's not the first time I've retracted, nor will it be the last. But thanks for the sentiments.
Of course you can swap rows and columns: it's just a quick way of producing a different table to examine. Obviously you mustn't compare the results between the swapped and non-swapped tables.
The rows and columns do not have read in any particular direction.
(I'll add that they don't have to be sorted either).
Post a Comment
Links to this post:
Create a Link
<< Home