Who is the tallest, the smallest of the tallest or the tallest of the smallest?

[DaxInvader]

Hi, I am a french Student in pures sciences. so its a bit hard for me to express myself in english, but I will do my best.

Homework Statement

Three hundred (300) persons are placed in thirty (3) rows and ten (10) columns. We choose the tallest person of each ROW. Then, we take the smallest person of those thirty (30) persons. On the other hand, we take the smallest person of each columns. Then we take the tallest person of those ten (10) persons.

Who is the tallest, the smallest of the tallest or the tallest of the smallest?

Homework Equations

There are none. i just started my course and, except the logic fonctions, we didn't see any formrulas or equations.

The Attempt at a Solution

I drawed a table and tried to do a formula.. but i don't even know where to start! its my 3th course and i never saw logic problem like this before. I guess we suppose that the tallests are the smallest of the tallest, and, with the principle of the locomotive (this means that if it work for V=1, than i should work for V=2 and so on..) prove that it works for everything..

Min(MAX) > (or equal than) Max(MIN)

What do you think?

Sorry for my english, I hope I am being understood.

 

[dlgoff]

Since you have all the tallest from each row, doesn't that mean there aren't any more that are taller than these?
edit: No. This isn't true. Sorry

 

[DaxInvader]

I found the solution! Well Now i have to "explain" it!

I went to excel and I made a table 10 * 30 with organized numbers (1,2,3,4...300)

It gave me the same.

Since the smallest of the tallest is the ONLY one in his row, the 9 remaining numbers are necessarly lower or equal then him. When we take the tallest of the smallest number of each column, it in in the same row than the number befor ebecause he is the smallest of the highest, and the highest of the row.

Im I right?

 

[HallsofIvy]

First, congratulations on using a fundamental "problem solving" method: if you get stuck on a problem, look at a simpler version. In this case you swapped 300 people in arbitrary order for 300 numbers in numerical order. When I first looked at this problem I used 10 by 10 with 1 to 100. Yes, the "Max(Min)= Min(Max)".

 

[DaxInvader]

So I'm right? Yess! i tried different combination but I came up with the same results..
Thank you!

 

[HallsofIvy]

But one or two specific cases is not enough to prove this statement. Can you show that you must always have max(min)= min(max)?

 

[DaxInvader]

Well, even with my table of 10 * 30 with organized numbers (1,2,3,4...300)... It was still too hard to see .. So I only choose ONE row and ONE colomn. The "representative one" . we can scrap the other becaus i SUPPOSE that the 2 number I'm looking for are In those 2... And from there.. I am still searching for the proof..

 

[DaxInvader]

here we go

...100...*...*...1 ->100
a..a..a..a..a..a..a..a..a..3 ->3
...

300 * * *




lets say 1<a<3

and the stars are random numbers * > 3

in this case, we have the smallest of the highest or each row is 3.

The tallest of the smallest of each colomn would be "a"

but he is smaller than 3.

in that case : Min(max) > Max(Min)

 

[DaxInvader]

COuld it be that we just can't know? or my Min(MAX) > (or equal than) Max(MIN) hypothesis is true? so If i find a order that contractics this hypothesis, than there is no solution.

 

[Dick]

You want to show min(max in row)>=max(min in column). Suppose A is the value that is the minimum of ANY column. That means every other value in the column is greater than or equal to A. That means max of ANY row is also greater than or equal to A (since every row also includes a value in that column. So if P is the set {max in row} and Q is the set {min in column}, every element of P is greater than every element of Q.

 

[DaxInvader]

Mmm... I think I understood.. But could you explain it again? with other words?

 

[Dick]

I'm saying (max in row)>=(min in column). For any row or column. Do you not see why?

 

[DaxInvader]

not quite.. I tried With the proprety of the matrices.. i mean i cannot prove it oraly.. I have to do a concrete proof..

 

[Dick]

"Suppose A is the value that is the minimum of column n. That means every other value in the column is greater than or equal to A. That means max of ANY row is also greater than or equal to A (since every row also includes a value in that column)." (I rephrased it a little). You don't buy that? What's wrong with it? This problem is a lot less complicated than you think. And once you realize that, it isn't really worth simulating numerically. You are taking the min over a bunch of numbers and comparing with the max over a second bunch of numbers. But every member of the first bunch of numbers is greater than any member of the second bunch of numbers. That's the point.