1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Logic and proof method.

  1. Sep 15, 2008 #1
    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.

    1. The problem statement, all variables and given/known data

    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?


    2. Relevant equations

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

    3. 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.
     
    Last edited: Sep 15, 2008
  2. jcsd
  3. Sep 15, 2008 #2

    dlgoff

    User Avatar
    Science Advisor
    Gold Member

    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
     
  4. Sep 15, 2008 #3
    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?
     
  5. Sep 16, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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)".
     
  6. Sep 16, 2008 #5
    So I'm right? Yess!! i tried different combination but I came up with the same results..
    Thank you!
     
  7. Sep 17, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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)?
     
  8. Sep 17, 2008 #7
    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.. im still searching for the proof..
     
  9. Sep 17, 2008 #8
    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)
     
  10. Sep 17, 2008 #9
    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.
     
    Last edited: Sep 17, 2008
  11. Sep 17, 2008 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Sep 17, 2008 #11
    Mmm... I think I understood.. But could you explain it again? with other words?
     
  13. Sep 17, 2008 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm saying (max in row)>=(min in column). For any row or column. Do you not see why?
     
  14. Sep 19, 2008 #13
    not quite.. I tried With the proprety of the matrices.. i mean i cannot prove it oraly.. I have to do a concrete proof..
     
  15. Sep 19, 2008 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    "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.
     
    Last edited: Sep 19, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Logic and proof method.
  1. Logic: Proofs (Replies: 3)

Loading...