Super lost on how to start with this problem It is a question in my math book but there are no explanation or an answer to the problem
In a $3$ $×$ $7$ office landscape, one person sits at each desk.
Prove that there must be a single-sex rectangle, which means four people of the same sex who sit in the corners of one and the same rectangle (for example, at the tables marked with rings in the image).
Prove first that there must be two people of the same gender for each column
Then prove for a $3$ $×$ $9$ landscape that there must be a single-sex rectangle, by proving that in such a landscape there must be two columns of identical gender placement
Now divide the task of the $3$ $×$ $7$ office landscape into two cases. Start with the case that there is a column where everyone has the same gender and show that there is surely a unisexed rectangle
Then proceed with the case that there is no column in which three have the same gender (count the number of different possible columns where not all have the same gender) and show that then there is also definitely a single-gender rectangle
Conclude that each $3$ $×$ $7$ landscape must have a single-gender triangle. Finally, give an example of a $3$ $×$ $6$ landscape that does not have an ever-gendered rectangle.
Because we have 2 genders and we have 3 options it will allways have 2 of the same gender in a column
So if I place them I get 8 uniqe placment: if Man=M and Woman=k
m k m k k m k m
k m m m k k k m
m k k m m k k m
if we add one more row we are bound to have dublicate and if we remove one we still get condition for the rectangular so the limit is 7 and below that we cant find the condition.
Notes: this question is a classical and you may find it somewhere else in the form of lattice points colored red or blue on a $2 \times 6$ rectangle.
Solution
Consider all the possibilities of the 3 people sitting in a column from top to bottom, which are: (M,M,M),(M,M,F),(M,F,M),(M,F,F),(F,M,M),(F,M,F),(F,F,M),(F,F,F) where M stands for Male, F stands for Female.
Now if there are 9 or more columns then it is easy to show that by Pigeonhole Principle there must be two columns of the same kind and therefore there is a rectangle by same-sex individuals.
Now if there are 7 columns, then consider the following two possibilities.
Case I: One of the column includes (M,M,M) or (F,F,F)
Then because each column has at least two people of the same sex, and there is at most 4 columns that may consists of the same couple (M,M) or (F,F), thus there is a rectangle.
Case II: None of the column includes (M,M,M) or (F,F,F)
Then there are 6 possibilities left, which by Pigeonhole Principle yields the Q.E.D