Arbitrary array of numbers, proof

In summary, the homework statement states that 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. The Attempt at a Solution assumes that s<t and proves that s is greater than or equal to t.
  • #1
Daltohn
30
0

Homework Statement


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.

Homework Equations

The Attempt at a Solution


I see intuitively that this is the case but have no idea where to start with a proof.
 
Physics news on Phys.org
  • #2
How about reversing the problem ? assume t > s and show that it leads to a contradiction ...
 
  • #3
Suppose it is false, i.e. s<t. What can you say about other numbers in the same row as s?
 
  • Like
Likes BvU
  • #4
haruspex said:
Suppose it is false, i.e. s<t. What can you say about other numbers in the same row as s?
I don't know except that they're all less than s. What more can I deduce assuming s<t?
 
  • #5
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##.
Daltohn said:
I don't know except that they're all less than s.
Use this knowledge to contradict the assumption that s<t.
Each of the t_m terms are the minimums from their columns.
 
  • #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.
 
  • #7
You've got it. The best you can hope for is t=s.
 
  • #8
Yep, thank you all :)
 

Related to Arbitrary array of numbers, proof

1. What is an arbitrary array of numbers?

An arbitrary array of numbers is a collection of data in the form of numbers that are arranged in a specific order. This order can be random or predetermined, and the numbers can be of any type, such as integers, decimals, or fractions.

2. How is an arbitrary array of numbers different from a regular array?

An arbitrary array of numbers differs from a regular array in that it does not follow a specific pattern or rule. Regular arrays usually have a fixed size and a specific way of arranging the numbers, while arbitrary arrays can be of any size and have no specific arrangement.

3. What is the purpose of an arbitrary array of numbers in scientific research?

An arbitrary array of numbers is often used in scientific research to represent and analyze data. The numbers in the array can be used to identify patterns, trends, and relationships, which can then be used to draw conclusions and make predictions.

4. How can you prove the validity of an arbitrary array of numbers?

To prove the validity of an arbitrary array of numbers, scientists often use statistical analysis and data visualization techniques. This involves calculating measures of central tendency and variability, such as mean, median, and standard deviation, and creating graphs or charts to visually represent the data.

5. Can an arbitrary array of numbers be manipulated or altered?

Yes, an arbitrary array of numbers can be manipulated or altered. This can be done by adding, removing, or rearranging numbers in the array. However, any changes made to the array should be carefully considered and documented to ensure the integrity of the data.

Similar threads

Perfect Stategy -- Placing picked numbers on two rows of a game
    • Precalculus Mathematics Homework Help
Replies
6
Views
2K
Why does this sorting algorithm properly sort the array?
    • Precalculus Mathematics Homework Help
Replies
12
Views
2K
B Is it invalid to redefine the sgn function in this way in a proof?
    • Linear and Abstract Algebra
Replies
15
Views
4K
I Can New Theorems Predict Incomplete 5x5 Magic Square Solutions?
    • General Math
2
Replies
68
Views
9K
B Combinatorics and Magic squares
    • General Math
Replies
2
Views
1K
My first proof ever - Linear algebra
    • Precalculus Mathematics Homework Help
Replies
4
Views
1K
Tricky Math Problems: Solving Square and Rectangle Challenges
    • Precalculus Mathematics Homework Help
Replies
2
Views
4K
Technique for proving Inclusion-Exclusion principle combinatorically
    • Math Proof Training and Practice
Replies
5
Views
987
Proving least upper bound property implies greatest lower bound property
    • Precalculus Mathematics Homework Help
Replies
22
Views
11K
Minor question about solution to Dedekind-Cut proof
    • Precalculus Mathematics Homework Help
Replies
13
Views
4K

Hot Threads

Recent Insights

Back
Top