On Some Planet,there are \(2^n\) Countries (\(n \geq 4 \) ).

Each Country Has a Flag \(n\) units wide and one unit high composed of \(n\) Fields of size \(1 \times 1\),each field being either yellow or blue.No two countries have the same flag.

We say that a set of \(n\) flags is diverse if these flags can be Arranged in \(n \times n\) square so that all \(n\) fields on its Main Diagonal will have the same colour.

Determine the Smallest Possible integer \(m\) such that among any \(m\) distinct flags,there exist \(n\) Flags forming a Diverse Set.

I Need A bit of help In Understanding the Last Part of the Problem.

## Comments

Sort by:

TopNewestThey should also clarify if "main diagonal" refers to just 1 diagonal, or both. As it turns out, it's just 1 diagonal, ie. squares of the form \( (i,i) \).

This is IMO Shortlist 2010 C2, which I believe is the primary source.

This is essentially a construction problem and there are 2 main parts to it.

We have have to guess what \(M\) is going to be, and explain why \(M - 1 \) doesn't work. That's the easy part.

We then have to show that given \(M \) flags, we can always find \(N\) that satisfy the condition. There is a solution using the "backward induction" approach, but the base case requires quite a bit of work.

There is another solution using the Hall Marriage Theorem, but that would require more understanding. – Calvin Lin Staff · 2 years, 2 months ago

Log in to reply

Yes,Its from that Magazine,"Mathematics Today"..

Thanks,I got the meaning now,Perphaps now everyone can solve it. – Vraj Mehta · 2 years, 2 months ago

Log in to reply

The last part of the question is asking the value of the smallest possible value of \( m \) such that if you take any \( m \) flags from the \( 2^n \) flags, you can always find \( n \) flags from those \( m \) flags such that those \( n \) flags form a "diverse" set.

\( m \geq n \) is implicit, otherwise we wouldn't be able to take \( n \) flags from the \( m \) flags.

Is this question from a Maths Magazine for JEE? (Can't remember the name). – Siddhartha Srivastava · 2 years, 2 months ago

Log in to reply

@Calvin Lin @Jon Haussmann @Pratik Shastri @Raghav Vaidyanathan @Deepanshu Gupta @Brian Charlesworth @Sandeep Bhardwaj @Pranjal Jain @Ronak Agarwal @Azhaghu Roopesh M

Any Ideas? – Vraj Mehta · 2 years, 2 months ago

Log in to reply