All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
A grid of people (Posted on 2002-07-09) Difficulty: 3 of 5
Imagine a "grid" of people: some number of people arranged in a number of rows and columns in a rectangular formation.

We designate person A as the shortest person in the group of the tallest people of each row. We then designate person B as the tallest person in the group of shortest people in each column.

Who is taller, A or B?

See The Solution Submitted by levik    
Rating: 3.5833 (12 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Four line proof: | Comment 4 of 15 |
Answer: height(A) ≥ height(B)

Notation:
If the people are arranged in a grid consisting of i rows and j columns, then define the matrix M as the "height" matrix composed of i rows and j columns where the elements of the matrix, denoted by m(a,b), record the height of the person in the a_th row and the b_th column.


Proof:

1) Choose A and B from the matrix according to the rules and denote A=m(a,b) and B=m(c,d).

2) Since A is by definition bigger than any other element in it's row, m(a,b) ≥ m(a,d).

3) Since B is by definition smaller than any other element in it's column, m(a,d) ≥ m(c,d).

4) Stringing together the inequalities:
height(A)=m(a,b) ≥ ;m(a,d) ≥ m(c,d)=height(B).

Q.E.D.

Notes: This may seem like trickery, but it's not. Because of the way the 'tallest of row' and 'shortest of column' groups are chosen, they can be related throught the matrix element where the row A is in and the column B is in intersect.

The elements of the the part about the shortest of the tallest and the tallest of the shortest is there to confuse you a bit. in fact, I've proven that is that all the tallest elements of the rows are taller than all the shortest people in the columns - a more general result.


  Posted by G. Steve Arnold on 2002-07-09 08:18:59
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (3)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information