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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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 - 3 years, 6 months ago

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

Thanks,I got the meaning now,Perphaps now everyone can solve it.

- 3 years, 6 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).

- 3 years, 6 months ago

Any Ideas?

- 3 years, 6 months ago