×

# 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
2 years, 2 months ago

Sort by:

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. Staff · 2 years, 2 months ago

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

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

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). · 2 years, 2 months ago