Waste less time on Facebook — follow Brilliant.

A Flag Problem!!

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.

Note by Vraj Mehta
1 year, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

They 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 · 1 year, 7 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 · 1 year, 7 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 · 1 year, 7 months ago

Log in to reply

Log in to reply


Problem Loading...

Note Loading...

Set Loading...