1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

Arbitrary array of numbers, proof

  1. Oct 9, 2015 #1
    1. The problem statement, all variables and given/known data
    The numbers 1 to 25 are arranged in a square array of five rows and five columns in an arbitrary way. The greatest number in each row is determined, and then the least number of these five is taken; call that number s. Next, the least number in each column is determined, and then the greatest number of these five is taken; this number is called t.
    Prove that s is equal to or greater than t for all possible arrangements.

    2. Relevant equations

    3. The attempt at a solution
    I see intuitively that this is the case but have no idea where to start with a proof.
  2. jcsd
  3. Oct 9, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    2017 Award

    How about reversing the problem ? assume t > s and show that it leads to a contradiction ....
  4. Oct 9, 2015 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Suppose it is false, i.e. s<t. What can you say about other numbers in the same row as s?
  5. Oct 9, 2015 #4
    I don't know except that they're all less than s. What more can I deduce assuming s<t?
  6. Oct 9, 2015 #5


    User Avatar
    Homework Helper

    s is the least of the biggers and t is the greatest of the smallers, right?
    Say, ## s = \min( s_1, s_2, s_3, s_4, s_5) ## where ##s_n ## denotes the largest member in row n.
    Similarly, ## t= \max( t_1, t_2, t_3, t_4, t_5) ## where ##t_m ## denotes the smallest member in column m.
    You know something about row n where ##s = s_n##.
    Use this knowledge to contradict the assumption that s<t.
    Each of the t_m terms are the minimums from their columns.
  7. Oct 9, 2015 #6
    Okay, I'm an idiot...

    Suppose s<t. Then t is not in the same row as s since none of its members is greater than s. But then t can never be the least in its column since every column has a member that is less than or equal to s. However, t is by definition the least in its column. Contradiction. Hence s is greater than or equal to t.

    Something like that? Maybe the contradiction is that t both is and isn't a member of the same row as s.
  8. Oct 9, 2015 #7


    User Avatar
    Homework Helper

    You've got it. The best you can hope for is t=s.
  9. Oct 9, 2015 #8
    Yep, thank you all :)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted