A Flag Problem!!

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

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

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

Determine the Smallest Possible integer mm such that among any mm distinct flags,there exist nn Flags forming a Diverse Set.

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

#Combinatorics

Note by Vraj Mehta
6 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

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

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

Is this question from a Maths Magazine for JEE? (Can't remember the name).

Siddhartha Srivastava - 6 years, 3 months ago

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

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

Vraj Mehta - 6 years, 3 months ago

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) (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 MM is going to be, and explain why M−1M - 1 doesn't work. That's the easy part.

We then have to show that given MM flags, we can always find NN 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 - 6 years, 3 months ago
×

Problem Loading...

Note Loading...

Set Loading...