A problem in combinatorics

  • #1

Homework Statement



Let A be a 100x100 matrix such that each number from the set {1,2,...,100} appears exactly 100 times. Prove that there exists a row or column with at least 10 different numbers.

Homework Equations




The Attempt at a Solution



I suspect that I should use the pigeonhole principle, but I can't think of a way to do so.
 

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
so as a start could you look for a contradiction by assuming every row & column can have 9 or less distinct numbers
 
  • #3
Solved it, thanks :)
 

Related Threads on A problem in combinatorics

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
845
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
V
  • Last Post
Replies
1
Views
2K
Top