1. Limited time only! Sign up for a free 30min personal 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!

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

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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

    RUber

    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

    RUber

    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



Similar Discussions: Arbitrary array of numbers, proof
  1. Basic real number proof (Replies: 10)

  2. Prime number proof (Replies: 3)

Loading...