ISL 2010 C2

For discussing Olympiad Level Combinatorics problems
User avatar
Abdullah Al Tanzim
Posts: 20
Joined: Tue Apr 11, 2017 12:03 am
Location: Dhaka, Bangladesh.

ISL 2010 C2

Unread post by Abdullah Al Tanzim » Sat Jan 19, 2019 8:46 pm

On some planet, there are $2^N$ countries $(N\geq 4)$.Each country has a flag $N$ units wide and $1$ unit high composed of $N$ fields of size $1\times1$, 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 into an $N\times N$ square so that all $N$ fields on its main diagonal will have the same color.Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a $DIVERSE$ set.
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

User avatar
Abdullah Al Tanzim
Posts: 20
Joined: Tue Apr 11, 2017 12:03 am
Location: Dhaka, Bangladesh.

Re: ISL 2010 C2

Unread post by Abdullah Al Tanzim » Sat Jan 19, 2019 9:17 pm

Solution:
We claim that the smallest positive integer $M$ is $2^{N-2}+1$.
We will prove that the highest positive integer $K$ such that we will not find a $DIVERSE$ set of $K$ flags is $2^{N-2}$.
A set of $K$ flags is not $DIVERSE$ if and only if there exist two positive integers $m$ and $n$ such that there is $Yellow$ color in $m^{th}$ field and $Blue$ color in $n^{th}$ field of every flag in the set.Then we have $N-2$ fields left and the maximum number of flags we can get fron this is $2^{N-2}$

So, the highest value of $K$ is $2^{N-2}$ which is necessary and sufficient.
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

Post Reply