There exist N flags forming a diverse set

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Jul 17, 2011, 1:54 PM • 9 Y

Y by bartle-doo, Davi-8191, nmd27082001, anantmudgal09, tenplusten, Adventure10, kiyoras_2001, and 2 other users

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 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.

Proposed by Tonći Kokan, Croatia

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

m.candales

186 posts

m.candales

#2 h Jul 17, 2011, 11:14 PM • 3 Y

Y by Bassiskicking, Adventure10, and 1 other user

The answer is $M=2^{N-2}+1$
Let's represent yellow by 0, blue by 1; and the flags by binary strings.

Notation: If s is a binary string of length N, we will refer to the suffix of length N-1 of s just as: the suffix of s.
If m binary strings of length m can be rearranged in a matrix such that all the entries in the main diagonal are equal, we will just say that we can nicely arrange the m strings. The common value of the entries in the main diagonal will be just called the common value

Let $S$ be the set of binary strings of length $N$ starting with 10. Then $|S|=2^{N-2}$ . We can see that it is not possible to nicely arrange N strings of S, since the first entry of the diagonal will be a 1, and the second entry of the diagonal will be a 0.
Therefore $M\ge 2^{N-2}+1$

Now let's prove by induction, that if we have $2^{N-2}+1$ different binary strings of length $N$ , it is always possible nicely arrange $N$ of them

Suppose this is true for $N-1\ge 4$ .
Now, let $S$ be a set of $2^{N-2}+1$ binary strings of length $N$ . Consider the set $K$ of suffixes of the strings in $S$ . Then $|S|\le 2|K|$ , since for every string $k$ in $K$ there at most two strings in $S$ with suffix $k$ . Then $|K|\ge 2^{N-3}+1$ . Then by the induction hypotesis we can nicely arrange $N-1$ strings of $K$ . Assume WLOG that the common value in this arrangement is 1. Consider a set of $N-1$ strings of S such that their suffixes are the strings in $K$ , and call this set $H$ ( $H$ has $N-1$ strings, and the suffix of each of them is a different element of $K$ ). If there is a string $w\in S/H$ that starts with 1, then we are done (we would be able to nicely arrange the $N$ strings of $H\cup{w}$ . If not, then all the strings of $S/H$ start with $0$ . Then they all have different suffixes. $|S/H| = 2^{N-2}+1-(N-1)\ge 2^{N-3}+1$ (this holds for every $N\ge 5$ ). Then we can select $N-1$ strings in $S/H$ , such that we can nicely arrange their suffixes Let's call $T$ the set of those $N-1$ strings of S/H. Now notice that $|S/H| - (N-1) \ge 2^{N-3}+1-(N-1)\ge 1$ , then there is at least another string in $S/H$ , say $s0$ , not included in $T$ . $s0$ starts with $0$ since it belongs to $S/H$ . Also, $|S|\ge 2^{N-2}+1$ implies that there is a string in $S$ that starts with $1$ ; say $s1$ . All strings in $S/H$ start with 0, then $s1\in H$ . Then $s0$ and $s1$ are not in $T$ , and start with different digits. Then we can nicely arrange the strings of $T$ together with one of $s0$ or $s1$ . So, we are done.

It only remains to prove the base case for the induction. It remains to show that for any set of 5 binary strings of length 4, we can nicely arrange 4 of them.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgrozev

2463 posts

dgrozev

#3 h Jul 18, 2011, 5:01 AM • 2 Y

Y by Adventure10, Mango247

... , sorry, my bad, actually $M= 2^{N-2} + 1$ is right.

This post has been edited 1 time. Last edited by dgrozev, May 7, 2013, 7:50 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowEverywhere

801 posts

SnowEverywhere

#4 h Jul 20, 2011, 8:22 PM • 2 Y

Y by Adventure10, Mango247

In the problem it says that $N \ge 4$ . I misread this too.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

antimonyarsenide

875 posts

antimonyarsenide

#5 h Feb 13, 2013, 8:14 PM • 6 Y

Y by MathbugAOPS, Adventure10, Mango247, and 3 other users

Proving the base case N=4, which is actually not completely trivial

This post has been edited 1 time. Last edited by MellowMelon, Aug 29, 2015, 6:21 PM
Reason: fix latex broken by the site upgrade

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#6 h Jul 10, 2014, 2:27 PM • 3 Y

Y by Al-Handasa, Adventure10, Mango247

I claim that for all $N \geq 4,$ given any $2^{N-2}+1$ distinct flags with length $N,$ we can find any $N$ of them forming a diverse set. We induct on $N.$ The base case $N=4$ is just some boring casework and has been posted above. Suppose that for some $j \geq 4,$ given any $2^{j-2}+1$ distinct flags of length $j$ there must be $j$ of them which form a diverse set.

Consider a selection of $2^{j-1}+1$ distinct flags each of length $j+1.$ We need to show that there exists a $j+1$ -element subset of these flags forming a diverse set. Each flag can be represented as a binary string, where a 0 stands for white and a 1 stands for black. For example, the flag WHITE BLACK WHITE BLACK WHITE corresponds to the binary string 01010.

Let $S_1, S_2, \cdots , S_{2^{j-1}+1}$ be the associated binary strings of the flags. Remove the last digit from each of the binary strings, resulting in the strings $R_1, R_2, \cdots , R_{2^{j-1}+1}$ respectively.

Claim: The $R_i$ 's take in at least $2^{j-2}+1$ distinct possibilities.
Proof: Suppose there are less than $2^{j-2}+1$ distinct possibilities of the $R_i$ 's. Note that each $S_i$ can be obtained from $R_i$ by appending either a 0 or a 1 to its end, so given a $R_i,$ there are two possibilities for $S_i.$ Hence, the number of distinct possibilities the $S_i$ 's can take in is at most $2 \cdot 2^{j-2} = 2^{j-1},$ contradiction. $\blacksquare$

Combined with our inductive hypothesis, the claim implies that there exists a $j$ element subset of the $R_i$ 's which can be arranged to form a diverse set. WLOG suppose the $j$ elements are $R_1, R_2, \cdots , R_j$ , which, when arranged from bottom to top in that order, form a diverse set. WLOG assume the diagonal of this set is white. If there exists a $S_i$ with $i>j$ whole last entry is also 0, the strings $S_1, S_2, \cdots , S_j, S_i$ when arranged bottom to top in that order form a diverse set. So we assume all $S_i$ 's with $i>j$ have their last entry 1.

Note that there are exactly $2^{j-1}+1-j$ distinct strings in the set $\{S_{j+1}, S_{j+2}, \cdots , S_{2^{j-1}+1}\}.$ Since for all $i>j,$ string $S_i$ is obtained from $R_i$ by simply appending a 1 at the end, there are exactly $2^{j-1}+1-j$ distinct strings in the set $\{R_{j+1}, R_{j+2}, \cdots , R_{2^{j-1}+1}\}.$ This is strictly larger than $2^{j-2}+1$ for $j \geq 4,$ so some $j$ elements from this set can be arranged to form a diverse set. WLOG suppose the strings $\{R_{j+1}, R_{j+2}, \cdots , R_{2j-1}, R_{2j}\}$ , when arranged from bottom to top in that order, form a diverse set.

Case 1: The diagonal of this diverse set is colored black.
Since $S_{2j+1}$ also has its last entry 1, when arranged from bottom to top, the set $\{S_{j+1}, S_{j+2}, \cdots , S_{2j}, S_{2j+1} \}$ forms a diverse set with size $j+1.$

Case 2: The diagonal of this diverse set is colored white.
Take a $S_i$ with $i<j$ whose last entry is 0 (Such a $S_i$ must exist since if all $S_i$ 's had their last entry 1, we could just apply the inductive hypothesis on the $R_i$ 's and arrange them in such a way that the diagonals share the same color. If the diagonal was colored black, appending a 1 to each of the $R_i$ 's we'd be done. So the diagonal had to be white, implying the $j$ th digit of $R_j$ had to be white, which would imply there are no more than $2^{j-1}$ possibilities for the $S_i$ 's.) Then, the set $\{S_{j+1}, S_{j+2}, \cdots , S_{2j-1} , S_{2j} , S_i\}$ forms a diverse set.

In both cases, we're done. $\blacksquare$

Now we need to construct a counterexample for $2^{n-2}.$ Just consider the set of strings all of whose first two digits are 01 (or 10). At least one of the colors in the diagonal has to be white and at least one of them has to be black, so this is our required counterexample.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#7 h Aug 21, 2015, 11:49 PM • 11 Y

Y by va2010, LJQ, PWuSinaisGod, MathbugAOPS, TinTin028, Atpar, Adventure10, vrondoS, Mango247, iamnotgentle, MS_asdfgzxcvb

The answer is $M = 2^{N-2}+1$ ; interpret as binary strings. To show $M > 2^{N-2}$ , we simply take a set of flags with all $0$ in first column and all $1$ in second column (thus using the fact that $N \ge 4$ ).

Now, we show that any bad sets of $m$ flags satisfies $m \le 2^{N-2}$ .
Since it's impossible to align $0$ 's on the diagonal, by Hall's Marriage Theorem there is a set of $1 \le a < N$ indices so that almost all (i.e. all but $a-1$ ) strings have all $1$ 's in these positions; call these strings $0$ -deficient. Define the $1$ -deficient strings over a set of $1 \le b < N$ indices similarly.
If the two sets of indices overlap, then no string can be both $0$ and $1$ deficient, so $m \le (a-1) + (b-1) \le 2N-4 \le 2^{N-2}$ .
Otherwise, there can be up to $2^{N-(a+b)}$ strings which are both $0$ and $1$ -deficient, so we deduce $m \le (a-1) + (b-1) + 2^{N-(a+b)} \le 2^{N-2}$ with equality when $a+b=2$ .
In both cases we're done. $\blacksquare$

(Example: if $N=6$ , $a=3$ and the indices are $\{1,2,3\}$ , then in the set of strings $\{111010, 111011, 111100, 111001, 111111, 101010, 000001 \}$ , the first five strings are $0$ -deficient; since there fewer than $3$ other strings, it's impossible to align $0$ 's on the main digonal.)

Somehow the construction for $M = 2^{N-2}$ took me twice as long as the Hall's theorem? That's what I get for using $N \le 3$ to guide myself

This post has been edited 4 times. Last edited by v_Enhance, Aug 30, 2015, 1:59 PM
Reason: this positions -> these positions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Gibby

718 posts

Gibby

#8 h Oct 26, 2015, 11:24 PM • 1 Y

Y by Adventure10

Can you explain what we're pairing with what when you apply Hall's marriage theorem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rah4927

62 posts

rah4927

#9 h Dec 7, 2015, 4:13 PM • 4 Y

Y by Davi-8191, tenplusten, Adventure10, Mango247

After proving the case $N=4$ which has been proven above (indeed it is the hardest part of the proof), we induct on $N$ .

Suppose that if we take $2^{k-2}+1$ strings of length $k$ , we can always find a diverse set. Now let $N=k+1$ . Take any $2^{k-1}+1$ strings of length $k$ . Assume that there is no diverse set among these. Then erase the last digit of each string. Now take any random $2^{k-2}+1$ strings from the $2^{k-1}+1$ strings . Applying the induction hypothesis, we get a diverse set $D$ containing $k$ strings. Suppose WLOG that the number that appears in the diagonal of the diverse set is $0$ . Now put back the last digits of each string. Note that every other string apart from the ones in $D$ must end with $1$ since otherwise we would have a contradiction. So at least $2^{k-1}+1-k$ strings end with a $1$ . Now erasing the first digit of every string, and taking $2^{k-2}+1$ strings that all end in $1$ (This is possible since $2^{k-1}+1-k\ge 2^{k-2}+1$ for $k\ge 4$ ), we similarly find that the number of strings that start with a $0$ is at least $2^{k-1}+1-k$ . Hence the number of strings that start with a $0$ and end with a $1$ is $2^{k-1}+1-2k$ . But the number of strings that start with a $0$ and end with a $1$ is $2^{k-2}$ , which is smaller than $2^{k-1}+1-2k$ for $k\ge 4$ . This is a contradiction, thus ending the proof.

This post has been edited 1 time. Last edited by rah4927, Dec 10, 2015, 10:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rah4927

62 posts

rah4927

#10 h Dec 7, 2015, 4:17 PM • 2 Y

Y by Adventure10, Mango247

Gibby wrote:

Can you explain what we're pairing with what when you apply Hall's marriage theorem?

We are considering the rows as boys and the columns as girls. In the first case, we say a row and a column are acquainted iff their intersection contains a $0$ and in the second case a $1$ .

It is very common to consider the rows as boys and the columns as girls. The question would scream Hall's marriage theorem if one has sufficient experience with it. For more on this, you can see Math Olympiad Treasures by Titu Andreescu. It's got a nice chapter on it(it doesn't have too difficult problems though).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AdithyaBhaskar

652 posts

AdithyaBhaskar

#11 h Mar 15, 2016, 8:45 AM • 2 Y

Y by Adventure10, Mango247

Here is my solution.
Lemma 1. We have $M \geq 2^{N-2} +1.$
Proof. Take $2^{N-2}$ flags, each with the first field is yellow, and the last field is blue. Then clearly these do not form a diverse set, hence the bound.

Lemma 2. There exists a diverse set with among any $2^{N-2}+1$ of the flags.
Proof. We proceed by strong induction on $N.$ Let this result be true for some $N.$ Now we prove the result for $N+1.$ Choose two flags, such that it is not the case that both of them have both the first and the last fields of the same color (such a pair must exist by PHP). Assume w.l.o.g that they have the first fields of different color. Call them flags $A,B.$ Now among the rest of the flags, ignore the first field and consider the rest. Then we have at least $\lceil \frac{2^{N-1}-1}{2} \rceil = 2^{N-2} -1$ distinct 'sub-flags'. By the induction hypothesis there exists a diverse set (diverse for the last $n$ fields) among these. Now, exactly one of $A,B$ when added to the 'bottom' of these flags will make a diverse set (diverse for $n+1$ fields). We still require a base case. Any small value, say $n=4$ will do.

The above lemmas imply our claim.

I don't think we require this, but:
Motivation. We try small values. Also we note that if we isolate two fields as in Lemma 2, then we are able to do this. This leads us to thinking in powers of $2.$
Comments. This was a very easy problem by all standards, took like $15$ seconds. However, its a C2, and without doubt it is pretty so I have nothing to complain about

.

This post has been edited 1 time. Last edited by AdithyaBhaskar, Mar 15, 2016, 1:39 PM
Reason: See next post

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rah4927

62 posts

rah4927

#12 h Mar 15, 2016, 12:38 PM • 2 Y

Y by Adventure10, Mango247

AdithyaBhaskar wrote:

We still require a base case. Any small value, say $n=2$ will do.

I should probably read the whole post before I comment, but I don't think the base case $n=2$ would work (the question specifically states that $n$ is at least $4$ ).

This post has been edited 1 time. Last edited by rah4927, Mar 15, 2016, 12:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AdithyaBhaskar

652 posts

AdithyaBhaskar

#13 h Mar 15, 2016, 1:39 PM • 2 Y

Y by Adventure10, Mango247

rah4927 wrote:

AdithyaBhaskar wrote:

We still require a base case. Any small value, say $n=2$ will do.

I should probably read the whole post before I comment, but I don't think the base case $n=2$ would work (the question specifically states that $n$ is at least $4$ ).

Ah okay, I edited...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rah4927

62 posts

rah4927

#14 h Mar 16, 2016, 9:53 AM • 2 Y

Y by Adventure10, Mango247

AdithyaBhaskar wrote:

rah4927 wrote:

AdithyaBhaskar wrote:

We still require a base case. Any small value, say $n=2$ will do.

I should probably read the whole post before I comment, but I don't think the base case $n=2$ would work (the question specifically states that $n$ is at least $4$ ).

Ah okay, I edited...

But there's the main problem. The base case $n=4$ is the main part of the problem. Proving the base case is actually the core of the induction and I haven't found a trivial/easy solution to that particular case yet.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AdithyaBhaskar

652 posts

AdithyaBhaskar

#15 h Mar 16, 2016, 12:17 PM • 2 Y

Y by Adventure10, Mango247

Well, let's do this then, we take the base case as $N=2.$ Note that this implies the result for all $N \geq 2$ , which includes all the $N \geq 4.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#16 h Dec 15, 2016, 7:22 PM • 2 Y

Y by Adventure10, Mango247

solution but I got lazy at the end

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#17 h May 8, 2017, 2:10 AM • 3 Y

Y by laegolas, Adventure10, Mango247

This seems to be the only solution that does not involve induction. It would be appreciate it if someone could check it.

We claim that $m=2^{n-2}+1.$ For any binary string $s,$ define $s[j]$ to be the $j$ 'th entry in $s.$

With this notation, it is easy to see that a set $S=\{s_1,s_2,\cdots, s_n\}$ of strings is diverse iff for some permutation $\pi$ on $\{1,2,\cdots,n\},$ $s_{\pi(i)}[i]$ are all equal to each other (where $\pi$ is the ordering of the strings.)

We first show that $m=2^{n-2}$ fails. Indeed, consider the set of strings of the form $"01"+x$ where $x$ is a string with $n-2$ entries. Clearly there are $2^{n-2}$ such strings. Consider an arbitrary subset $S$ of these strings. Then regardless of how we order the strings, $s_{\pi(1)}[1]=0\neq 1=s_{\pi(2)}[2],$ so no diverse set exists.

Now consider an arbitrary set of $2^{n-2}+1$ strings, denoted by $X.$ The crucial claim is that either there does not exist a position $j$ such that $s_i[j]=0$ for all $i$ or there does not exist $j$ such that $s_i[j]=1$ for all $i.$ Assume this claim is false, then both parts of the disjunction is false and there must exist $j_1\neq j_2$ with $s_i[j_1]=0$ for all $i$ and $s_i[j_2]=1$ for all $i.$ But then two entries of each string in $X$ are constant, meaning there can only exist at most $2^{n-2}$ strings in $X,$ a contradiction. Hence the claim is true, and we may WLOG assume that for all $j,$ there exists $i$ such that $s_i[j]=1.$

If there exists a choice of $i_j$ such that $s_{i_j}[j]=1$ is distinct for all $j,$ we may simply pick $s_{i_j}$ for $1\leq j\leq n$ and produce our desired diverse set. Otherwise, there exists $j_1,j_2$ such that $i$ is the only value in $\{1,2,\cdots,2^{n-2}+1\}$ for which $s_i[j_1]=s_i[j_2]=1.$ It follows that for any string in $X$ distinct from $s_i,$ $s_i[j_1]=s_i[j_2]=0.$ There are only $2^{n-2}$ distinct strings with this property, and since $X-\{s_i\}$ has cardinality $2^{n-2},$ it follows that $X-\{s_i\}$ must consist of every string $s$ with $s[j_1]=s[j_2]=0.$ Now taking the strings $s_i\ (i\neq j_1,i\neq j_2)$ such that $s_i[i]=0$ and $s_i[k]=1$ for all $k\neq i,j_1,j_2,$ along with two arbitrary strings for $i=j_1,j_2,$ we get a diverse set ( $s_i[i]=0$ for all $i$ ) and we may conclude.

This post has been edited 1 time. Last edited by Generic_Username, May 8, 2017, 2:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

laegolas

984 posts

laegolas

#18 h May 8, 2017, 4:35 PM • 2 Y

Y by Generic_Username, Adventure10

Generic_Username wrote:

Otherwise, there exists $j_1,j_2$ such that $i$ is the only value in $\{1,2,\cdots,2^{n-2}+1\}$ for which $s_i[j_1]=s_i[j_2]=1.$

Unless I'm missing something obvious this is a nontrivial step, and in fact holds only with the crucial $M\ge 2^{n-2}+1$ . I think some explanation there would help, but otherwise the proof looks good.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#19 h May 8, 2017, 9:08 PM • 2 Y

Y by Adventure10, Mango247

laegolas wrote:

Generic_Username wrote:

Otherwise, there exists $j_1,j_2$ such that $i$ is the only value in $\{1,2,\cdots,2^{n-2}+1\}$ for which $s_i[j_1]=s_i[j_2]=1.$

Unless I'm missing something obvious this is a nontrivial step, and in fact holds only with the crucial $M\ge 2^{n-2}+1$ . I think some explanation there would help, but otherwise the proof looks good.

Thank you, I should have specified more. Assume that a pair $(j_a,j_b)$ for which there is such a value of $i$ does not exist, then it follows that for every pair $(j_a,j_b)$ that there exists a second value $i'\neq i$ such that $s_{i'}[j_a]=1,$ contradicting the assumption that we cannot choose a set of distinct $i.$

Removing most of the notation, this is basically what I'm saying. Let $k$ be the maximum number of distinct strings we can choose such that:
- Among all of the strings, there is a $1$ in at least one string for every position represented
- Within this set, each string contributes at least one $1$ in a unique position
If $k<n,$ clearly by pigeonhole there is a string that has a $1$ in two positions. Now if there is another string in the set of all strings that has a $1$ in any of those two positions, we can add it to this set which contradicts maximality. Thus every other string must have $0$ in those two positions.

This post has been edited 2 times. Last edited by Generic_Username, May 8, 2017, 9:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1980 posts

anantmudgal09

#21 h Jun 12, 2017, 10:29 AM • 2 Y

Y by rashah76, Adventure10

After flailing for four hours, I came up with the following solution. It has some nice local ideas (which will take effort to decipher since bad write-up), but admittedly, doesn't give a spiritual reason for why the result should be true.

IMO ShortList 2010 C2 wrote:

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 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.

Proposed by Tonći Kokan, Croatia

Solution

This post has been edited 1 time. Last edited by anantmudgal09, Jun 12, 2017, 10:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pandadude

710 posts

pandadude

#24 h Jun 4, 2018, 10:16 PM • 3 Y

Y by Ali3085, Adventure10, Mango247

Obviously $M$ is greater than $2^{N-2}$ because we can construct a set of $2^{N-2}$ flags where the first square is always yellow, second square always blue.

Lemma: If we have $2^{N-1}+1$ flags, we can create diagonals of both colors.
Let the diagonal color that we construct be yellow, wlog.
We use Hall's Marriage Theorem. Suppose row $i$ wants to marry all flags with a yellow square in their ith column. If the Hall condition is satisfied, we can simply insert the flag married to row $i$ in row $i$ to create the yellow diagonal. Take and subset of $k$ rows, only look at the columns of those $k$ indices. We see that by pidgeonhole, there are at least $\frac{2^{N-1}+1}{2^{N-K}}$ combinations or at least $2^{K-1}+1$ distinct combinations for those $k$ columns. There is only 1 "bad" combination(all blue) so there are at least $2^{K-1}$ good flags. $2^{K-1}>=K$ so we are done.

Therefore, with $2^{N-2}+1$ flags, ignoring the last column, we can create a diagonal of any color of length $N-1$ .
The rest of the proof is very easy since $2^{N-2}+1>2N-2$ (from $N>3$ ), we always have a flag not used to create either diagonal. Thus we see what color the final column in this flag is and we stack the $N-1$ diagonal of same color on it. Done

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

william122

1576 posts

william122

#25 h Oct 13, 2019, 11:26 PM • 2 Y

Y by Adventure10, Mango247

I claim that the answer is $2^{N-2}+1$ . To show that $2^{N-2}$ is not sufficient, consider the set of flags where all flags have the first square yellow and the last square blue.

Now, we will prove our claim with induction. The base case of $N=4$ is trivial, so proceed to the inductive step. Suppose we have a set of $2^{N-2}+1$ flags, and for the sake of contradiction, no $N$ of them form a diverse set. Of course, there exists a set of $2^{N-3}+1$ flags such that the colorings of their latter $N-1$ parts are pairwise distinct, so selecting them, we know that the set formed by their latter $N-1$ bits are diverse. If, say, this diverse set has a blue diagonal, then all we need is for one of the remaining $2^{N-2}+2-N$ flags to have a blue square at the beginning to produce a diverse set. However, since we are assuming the contrary, they must all have the same wrong color (in this case yellow). So, these remaining flags all have the same (wrong) colored first bit. Now, choose a set of $2^{N-3}+1$ flags from these $2^{N-2}+2-N$ , and repeat the argument. We get that all flags must have the same colored first bit. The same logic applies to the last square, so we have shown that all our flags have the same first color, and same last color. Of course, this is a contradiction, as only a set of $2^{N-2}$ flags of such a type exist.

This post has been edited 2 times. Last edited by william122, Oct 21, 2019, 1:04 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mofumofu

179 posts

mofumofu

#26 h Oct 14, 2019, 4:23 PM • 2 Y

Y by Adventure10, winniep008hfi

william122 wrote:

By inductive hypothesis, we know that for any set of $2^{N-3}+1$ flags, we can choose $N-1$ of them such that the last $N-1$ squares on them form a diverse $N-1$ set.

rah4927 wrote:

Suppose that if we take $2^{k-2}+1$ strings of length $k$ , we can always find a diverse set. Now let $N=k+1$ . Take any $2^{k-1}+1$ strings of length $k$ . Assume that there is no diverse set among these. Then erase the last digit of each string. Now take any random $2^{k-2}+1$ strings from the $2^{k-1}+1$ strings . Applying the induction hypothesis, we get a diverse set $D$ containing $k$ strings.

The induction hypothesis cannot be applied (yet) as the last $N-1$ squares may have duplicates. For example if $N=5$ , $2^{N-3}+1=5$ , so by induction hypothesis in any $5$ flags we can find $4$ , such that the last $4$ squares is diverse. But clearly the flags
10000
00000
11111
01111
10101
does not work. The induction hypothesis can only be used if the last $N-1$ squares are distinct, such as in post #6 and #16.

pandadude wrote:

The rest of the proof is very easy since $2^{N-2}+1>2N-2$ (from $N>3$ ), we always have a flag not used to create either diagonal.

This does not hold for $N=4$ .

rah4927 wrote:

But the number of strings that start with a $0$ and end with a $1$ is $2^{k-2}$ , which is smaller than $2^{k-1}+1-2k$ for $k\ge 4$ . This is a contradiction, thus ending the proof.

This does not hold for $k=4,5$ .

william122 wrote:

This tells us that, for any set of $2^{N-2}-1$ flags we choose, they will all have the same first square.

Do you mind elaborating how $2^{N-2}-1$ is obtained, and how "they will all have the same first square"?

AdithyaBhaskar wrote:

Then we have at least $\lceil \frac{2^{N-1}-1}{2} \rceil = 2^{N-2} -1$ distinct 'sub-flags'. By the induction hypothesis there exists a diverse set (diverse for the last $n$ fields) among these. Now, exactly one of $A,B$ when added to the 'bottom' of these flags will make a diverse set (diverse for $n+1$ fields). We still require a base case. Any small value, say $n=4$ will do.

Comments. This was a very easy problem by all standards, took like $15$ seconds. However, its a C2, and without doubt it is pretty so I have nothing to complain about

.

Firstly $\left\lceil\frac{2^{N-1}-1}{2} \right\rceil = 2^{N-2}$ and not $2^{N-2} -1$ , secondly I'm quite sure that the induction hypothesis is used for when there are $2^{N-2}+1$ distinct sub-flags, not $2^{N-2} -1$ or even $2^{N-2}$ . Finally post #12 did mention that smaller values of $N$ does not work, not just because the problem says $N\ge 4$ , but for $N=1,2,3$ the minimum flags needed is $M=1,3,4$ (I believe) respectively, which is greater than $2^{N-2}+1$ for those values.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#27 h Feb 9, 2020, 1:43 AM • 2 Y

Y by Adventure10, Mango247

Re-interpret the problem as an $M\times N$ binary matrix with distinct rows. Our goal is to find the smallest $M$ such that any such matrix has a way to choose a zero from each column with no two in the same row, or a way to choose a one from each column with no two in the same row. Call such a selection a good selection. We claim that the minimum such $M$ is $\boxed{2^{N-2}+1}$ . To see that we need $M\ge 2^{N-2}+1$ , note that we can select the matrix such that all rows start off with $01$ , which doesn't have a good selection since the first and second columns are always incompatible.

Now suppose that $M=2^{N-2}+1$ . We'll show that there is in fact a good selection. First note that there cannot be two columns that are both constant, since then there would be at most $2^{N-2}$ rows (each row has to be distinct). Thus, we have two cases.

Case 1: Suppose there is exactly one column that is entirely constant. Without loss of generality, suppose that this column is all $1$ s. We'll now show that there is a good selection of $1$ s (as there must be since we can't select a zero from the all ones column). Interpret the binary matrix as a bipartite matrix with the $N$ columns on the left and the $M=2^{N-2}+1$ rows on the right, and an edge between row and column if and only if the square formed by the two has a $1$ . Our goal is to show that this graph has a matching saturating the columns, so it suffices to verify Hall's condition.

Suppose that we choose $k\ge 1$ columns. We want to show there are at least $k$ rows with a $1$ in one of these columns. If $k=1$ then we're done since there is no column of all zeroes.

Suppose now that $k\ge 2$ . Assume for sake of contradiction that for these $k$ columns, all but $k-1$ of the rows have zeroes in both columns (note that this means we couldn't have picked the all ones column). Thus, for $M-k+1$ rows of the original matrix, we have $k+1$ positions fixed - one from the all $1$ s column, and $k$ from the other $k$ all zeroes columns (except for the $k-1$ rows we removed). All these rows have to be distinct, so we must have $M-1\le 2^{n-k-1}$ , which is a contradiction, as desired.

Thus Hall's condition is satisfied in this case, so there is a good selection in this case.

Case 2: Suppose there are no entirely constant columns. Now, we have to verify Hall's condition in the same manner, except that we may have to replace the $0$ s with $1$ s.

We see that the Hall verification for $k=1$ works in the same way as the previous case. Furthermore, for $k\ge 3$ , the logic of the previous case tells us that $M-1\le 2^{n-k}$ in the event that Hall condition is broken (since we now only have $k$ fixed positions due to the lack of the all $1$ s column), which is again a contradiction.

Thus, it suffices to look at the case of $k=2$ . Assume for sake of contradiction that among these two columns, all but one row has zeroes in both columns. In this case, we may now shift our focus to finding a good selection of zeroes. The Hall verification for $k\ne 2$ works the same, so it suffices to look at this case. Again, a contradiction argument would give that we have two columns that have all but one row having all $1$ s. Clearly these two must be distinct from the two columns that have all but one row having all $0$ s. Thus, for at least $M-2$ rows, we have $4$ positions fixed, two forced to be zero, and two forced to be $1$ . This means that $M-2\le 2^{n-4}$ , which is clearly a contradiction.

Therefore, there is a good selection in this case too, completing the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MelonGirl

575 posts

MelonGirl

#28 h Feb 9, 2020, 2:19 AM • 2 Y

Y by Adventure10, winniep008hfi

Does anyone have a solution that doesn't use hall's?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Eyed

1065 posts

Eyed

#29 h Nov 13, 2020, 1:51 PM

Y by

@above, sorry

The answer is $M = 2^{n-2} + 1$ . We can prove $M > 2^{n-2}$ by taking a set of flags that start with $01$ . Now we prove that this works.

Consider a bipartite graph $G$ taking the positions to tuple, where there is an edge between a position $p$ and a tuple $t$ if $t[p] == 1$ . Furthermore, assume there are $2^{n-2} + 1$ tuples. I claim either halls condition is satisfied for $G$ , or it's satisfied for $\overline{G}$ (where we define $\overline{G}$ as every edge between a position and tuple gets flipped, but there are still no edges between tuples and tuples along with positions and positions). We have $2$ cases.

Case 1: There exists some position $p$ in $G$ that has degree $0$ .

We take $\overline{G}$ . For any set $A = \{a_{1}, a_{2}, \ldots a_{i}\}$ of positions, I claim halls condition is satisfied. Let's say only $j<i$ tuples are adjacent to an element in $A$ . Clearly $p$ is not an element of $A$ (or else every tuple will be connected), which also means $j < i < n$ . Then, all the other $2^{n-2} + 1 - j$ tuples has $0$ at $p$ and $1$ at the positions of $A$ , but there are only $2^{j-1}$ such tuples, a contradiction since $2^{j-1} \leq 2^{n-3} < 2^{n-2} + 1 - j$ . Thus, halls condition is always satisfied.

Case 2: Everything else

I claim halls condition is still satisfied. For every set $A = \{a_{1}, a_{2}, \ldots a_{i}\}$ of positions, let's say $j < i$ tuples are adjacent to an element in $A$ . If $i> 2$ , then there are $2^{n-i}$ tuple without a $1$ at any element in $A$ , but there must be $2^{n-2} + 1 - j$ such tuples, a contradiction since $2^{n-i} < 2^{n-2} + 1 - j$ for $i> 2$ . We now only need to check when $i = 2$ . If $i = 2$ , then clearly $j \geq 1$ (every position has positive degree), so $j = 1$ . We take $\overline{G}$ . Then, for every $2$ element position set $B$ , it must have at least $2$ tuples with $0$ s in those positions, otherwise every tuple but $1$ (so $2^{n-2}$ tuples) has a $1$ at $b_{1}, b_{2}$ , and a $0$ at $a_{1}, a_{2}$ , but there are only $2^{n-4}$ such sets, a contradiction. Thus, either $G$ or $\overline{G}$ satisfies halls.

Since either $G$ or $\overline{G}$ satisfies halls, this means we can have a $1$ in every position of different tuples, or a $0$ in every position of different tuples. Placing such tuples in a way such that they are on the main diagonal gives the result, so the answer is $M = 2^{n-2} + 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

guptaamitu1

656 posts

guptaamitu1

#30 h Nov 26, 2021, 2:02 PM

Y by

v_Enhance wrote:

The answer is $M = 2^{N-2}+1$ ; interpret as binary strings. To show $M > 2^{N-2}$ , we simply take a set of flags with all $0$ in first column and all $1$ in second column (thus using the fact that $N \ge 4$ ).

Now, we show that any bad sets of $m$ flags satisfies $m \le 2^{N-2}$ .
Since it's impossible to align $0$ 's on the diagonal, by Hall's Marriage Theorem there is a set of $1 \le a < N$ indices so that almost all (i.e. all but $a-1$ ) strings have all $1$ 's in these positions; call these strings $0$ -deficient. Define the $1$ -deficient strings over a set of $1 \le b < N$ indices similarly.
If the two sets of indices overlap, then no string can be both $0$ and $1$ deficient, so $m \le (a-1) + (b-1) \le 2N-4 \le 2^{N-2}$ .
Otherwise, there can be up to $2^{N-(a+b)}$ strings which are both $0$ and $1$ -deficient, so we deduce $m \le (a-1) + (b-1) + 2^{N-(a+b)} \le 2^{N-2}$ with equality when $a+b=2$ .
In both cases we're done. $\blacksquare$

(Example: if $N=6$ , $a=3$ and the indices are $\{1,2,3\}$ , then in the set of strings $\{111010, 111011, 111100, 111001, 111111, 101010, 000001 \}$ , the first five strings are $0$ -deficient; since there fewer than $3$ other strings, it's impossible to align $0$ 's on the main digonal.)

Somehow the construction for $M = 2^{N-2}$ took me twice as long as the Hall's theorem? That's what I get for using $N \le 3$ to guide myself

Here's a very fast way to finish after using Hall's theorem.

If $a \ge 2$ , then $m \le (a-1) + 2^{N-a}$ . For $a \ge 3$ , we are already done. If $a=2$ , then equality cannot holds (otherwise Hall's theorem would be vilated for the other color). So we are done for $a=2$ also. Similarly, for $b \ge 2$ we are done. The leftover case $a=b=1$ is just trivial. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#31 h Feb 9, 2022, 1:42 PM

Y by

The answer is $M=2^{N-2}+1$ . Interpret flags as binary strings with yellow being $0$ and blue being $1$ . To show that $2^{N-2}$ fails consider all the flags where the leftmost bit is $0$ and the second-leftmost is $1$ , of which there are $2^{N-2}$ .
To show that $M=2^{N-2}+1$ works we use Hall's marriage theorem. Suppose $M$ fails, so by Hall's there is some set of $1 \leq a<N$ bits such that at most $a-1$ of them contain a $0$ , so $2^{N-2}-a+2$ of them have all $1$ 's there. On the other hand, there are at most $2^{N-a}$ of the latter type, and for $a \geq 3$ we clearly have $2^{N-2}-a+2>2^{N-a}$ . Thus $a \leq 2$ .
If $a=2$ , then we have equality, meaning that every binary string with $1$ 's in those two bits is present. But then we can trivially form a diverse set such that the main diagonal is all $1$ , which means $a=1$ .
Similarly, if $M$ fails there is some set of $1 \leq b<N$ bits where at most $b-1$ of them contain a $1$ , and we get $b=1$ . But then there exists some bits $A,B$ such that bit $A$ is always $1$ and $B$ is always $0$ , giving only $2^{N-2}$ possible flags, contradiction. Thus any $M$ distinct flags must contain $N$ flags which form a diverse set. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sman96

136 posts

sman96

#32 h Aug 3, 2022, 4:57 PM

Y by

ISL Marabot solve

We will prove that the answer is $2^{N-2}+1$
Clearly, if we take all $2^{N-2}$ flags with first field yellow and second field blue then no subset of those flags will be diverse.

Also it's easy to see that for $M$ flags if there is no blue in $x$ th field and no yellow in $y$ th field then $M\leq 2^{N-2}$
So, if $M > 2^{N-2}$ then for at least one colour (WLOG let blue), for each field there will be a flag with that field of colour blue.
FTSOC, lets assume that we cant assign each field with a flag with that field of colour blue. So the marriage condition doesnt hold. Therefore there are $k>1$ fields s.t. the number of flags with at least one of those field blue is at most $k-1$ . So at least, $2^{N-2}-k+2$ flags must have all of those $k$ field yellow. And simple bounding shows that it can only happen for $k=2$ . But then we will get all possible combinations of colouring for the other $N-2$ field while those $2$ field being yellow. And clearly we will be able to make yellow diagonal in that case. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgrozev

2463 posts

dgrozev

#33 h Aug 10, 2022, 6:28 AM

Y by

The first idea that might appear is Hall's marriage theorem. Put 1 and 0 instead of the two colors, and suppose the binary strings that corresponds to the flags are put inside a $2^N\times N$ table $T$ . So, $T$ has $2^N$ rows and $N$ columns and each row contains a binary string of length $N$ . We refer to the columns as "positions". A diverse set is actually a matching between the positions and some $N$ rows. You dispose the flags as the first flag will be the row that matches the firs position, second flag - the row that corresponds to the second position and so on.

Let $G(A,B)$ be the complete bipartite graph on $A$ - the set of positions, and $B$ - the set of all rows. We color the edge $a\,b, a\in A, b\in B$ white if the row $b$ has $1$ at its $a$ -th position, and we color it black if there is $0$ at the $a$ -th position of $b$ . Let's denote by $G_0(A,B), G_1(A,B)$ the graphs corresponding to black and white edges respectively. We look for the smallest number $M$ such that for any subset $B'$ of $B$ with $|B'|=M$ there is a full matching $A\to B'$ in at least one of the induced graphs $G_0(A,B')$ or $G_1(A,B')$ .

Note that $M>2^{N-2}$ . Indeed, let $B'$ be the set of rows, each one having $0$ at its first and second positions. Clearly, $|B'|=2^{N-2}$ and each of the graphs $G_0(A,B')$ and $G_1(A,B')$ has a vertex in $A$ that is isolated vertex (with no incident edges). That is, no full matching $A\to B'$ is possible.

We will prove $M=2^{N-2}+1$ . Take any $B'\subset B$ with $|B'|=2^{N-2}+1$ and suppose for the sake of contradiction that Hall's marriage condition fails for both graphs $G_0(A,B')$ and $G_1(A,B')$ . This means that there are vertex sets $A_0$ and $A_1\,;\, (A_0,A_1\subset A)$ such that $N_{G_0}(A_0)<|A_0|$ and $N_{G_1}(A_1)<|A_1|,$ where $N_G(X)$ denotes the vertex set of all neighbors of $X$ in a graph $G.$ Let's first consider the case $A_0\cap A_1\neq \emptyset.$ This is not possible when $N\ge 5$ because then $2^{N-2}+1\ge 2N-1,$ hence the degree of a vertex $v\in A_0\cap A_1$ in either $G_0$ or $G_1$ is at least $N$ (the Hall's condition would be satisfied). The case $N=4$ is quickly checked. Indeed, since $2^{4-2}+1=5$ and $d_{G(A,B')}(v)=5$ , either $d_{G_0}(v)\ge 3$ or $d_{G_1}(v)\ge 3$ , say, $d_{G_0}(v)\ge 3$ . We know the Hall's condition fails for $A_0$ in $G_0(A,B')$ it means $d_{G_0}(v)= 3, |A_0|=|A|=4$ and $N_{G_0}(A_0)=3.$ The first two conditions show $A$ is connected to only two rows (out of 5) in $G_0$ , that is, there are two rows that consist of only $1$ 's, which is impossible because the binary strings are distinct. Note that in case $N=3$ we cannot get a contradiction like that (and the claim doesn't hold). That's why, $N\ge 4$ is required.

Thus, it remains to check the case $A_0\cap A_1= \emptyset.$ Delete all the rows in $N_{G_0}(A_0)$ and $N_{G_1}(A_1)$ . The number of deleted rows is at most $|A_0|+|A_1|-2$ , since $N_{G_0}(A_0)<|A_0|$ and $N_{G_1}(A_1)<|A_1|$ . The remaining rows have only $1$ 's at all positions in $A_0,$ and $0$ 's at positions in $A_1$ . Hence, if we delete all the columns that are in $A_0$ and $A_1$ there remain $N-|A_0|-|A_1|$ columns and at least $2^{N-2}+1-|A_0|-|A_1|+2$ rows of distinct binary strings on those columns. But, given $N-|A_0|-|A_1|$ positions, the number of all possible distinct binary strings on them is
$2^{N-|A_0|-|A_1|}=2^{(N-2)-|A_0|-|A_1|+2} <2^{N-2}+3-|A_0|-|A_1|$ contradiction. In the second part of the above inequality we used $2^{x-y}\le 2^{x}-y$ providing $x\ge 2, x\ge y$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1916 posts

cj13609517288

#34 h Jan 19, 2023, 3:06 PM

Y by

Used the 30% hint on ARCH. Also, in the version of the problem I received, $N$ was lowercase.

I claim that the answer is $\boxed{2^{n-2}+1}$ .

Construction for $2^{n-2}$ : $0S1$ , where $S$ can be any binary string of length $n-2$ .

Proof that $2^{n-2}+1$ always works:

Lemma 1. This is true for $x=0$ (inclusive or) $x=1$ : For every digits place, there is at least one flag that has an $x$ at that place.

Proof. Suppose not. Then by pigeonhole, each digit( $0$ or $1$ ) appears in exactly $n-1$ places. But that means the other place was only the other digit, meaning that some digit was always $0$ and some digit was always $1$ . But the number of remaining possibilities is now only $2^{n-2}$ , contradiction.

We can now apply Hall's Marriage Theorem to easily finish.

This post has been edited 1 time. Last edited by cj13609517288, Jan 19, 2023, 3:07 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1719 posts

awesomeming327.

#35 h May 29, 2023, 6:30 PM

Y by

The answer is $2^{N-2}+1$ . First, we note that $2^{N-2}$ fails by taking the subset of every flag such that the first field is yellow and the second is blue. In this way, no matter how we arrange into a square, the first square of the diagonal and the second square of the diagonal will be differently colored.

We proceed by contradiction that $2^{N-2}+1$ works. If for each subset of numbers $S\subseteq \{1,2,\dots, N\}$ , there are at least $|S|$ of the $M$ flags for which the $i$ th space on that flag is yellow, for some $i\in S$ , then by Hall's Marriage Lemma there exists an injective function from indices to flags, thus proving that our set of flags is diverse. Thus, for some subset $S_f$ of those numbers, at most $|S_f|-1$ flags have the $i$ th space as yellow, for some $i\in S_f$ .

Thus, there are at least $2^{N-2}-|S_f|+2$ blues at index $i$ for each $i\in S_f$ . On the other hand, there can at most $2^{N-|S_f|}$ flags with all of those fields blue. We have $|S_f|\le 2$ .

If $|S_f|=2$ then $2^{N-|S_f|}=2^{N-2}-|S_f|+2$ so each flag satisfying that both fields at index $i$ are blue. Clearly, we can then find $N$ of those flags, since $N\ge 4$ , such that they form the desired square.

If $|S_f|=1$ , then there exists a column that's only blue. Repeat the above process, ignoring the blue column, but with yellow replaced with blue and vice versa. We have a column that's only blue and a column that's only yellow, so we have at most $2^{N-2}$ flags. Contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#37 h Aug 24, 2023, 11:47 PM

Y by

This has happened in a few problems: when the equality case is harder than the bound :ewpu:

solved on OTIS where flags can be represented as binary strings

The answer is 2^{n-2}+1, with the lower bound easily achieved by taking some subset of flags s.t. they all start in 0 and end in 1, there are 2^{n-2} of these so that does not suffice. Assume FTSOC our answer does not work; in particular, by Hall's, there is some $1\le x<N$ with at most x-1 flags that contain 0s in some $i$ th column (WLOG). Then, (looking at the 1s in ith column) 2^{n-x}\ge 2^{n-2}-(x-1)+1\implies x\le 2.

Now, if x=2, equality means every binary string with 1 in the $i$ th column; in this case Hall's condition on 1s is satisfied. If x=1, again Hall's condition is satisfied.

my writeup is really weird can someone do a FTFY and fix it for me its super mind twisting

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwerty123456asdfgzxcvb

1086 posts

qwerty123456asdfgzxcvb

#38 h Mar 1, 2024, 10:49 PM

Y by

huashiliao2020 wrote:

This has happened in a few problems: when the equality case is harder than the bound :ewpu:

solved on OTIS where flags can be represented as binary strings

The answer is 2^{n-2}+1, with the lower bound easily achieved by taking some subset of flags s.t. they all start in 0 and end in 1, there are 2^{n-2} of these so that does not suffice. Assume FTSOC our answer does not work; in particular, by Hall's, there is some $1\le x<N$ with at most x-1 flags that contain 0s in some $i$ th column (WLOG). Then, (looking at the 1s in ith column) 2^{n-x}\ge 2^{n-2}-(x-1)+1\implies x\le 2.

Now, if x=2, equality means every binary string with 1 in the $i$ th column; in this case Hall's condition on 1s is satisfied. If x=1, again Hall's condition is satisfied.

my writeup is really weird can someone do a FTFY and fix it for me its super mind twisting

phrase from hall to col -> row instead

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8865 posts

HamstPan38825

#39 h Jun 9, 2024, 10:28 PM

Y by

With Hall's this problem is a bit boring; essentially you know that $2^{N-2}$ is the maximal counterexample, so $2^{N-2}+1$ should work by Hall, now just grind out all the details.

The answer is $M = 2^{N-2} + 1$ . To see that this is sharp, note that for $M = 2^{N-2}$ , we take all binary strings with a $1$ in the first position and a $0$ in the second position. Then there will always be both a $1$ and $0$ on the main diagonal no matter what $n$ strings we pick.

To see that the bound is tight, consider a mapping from the set $A$ of $N$ columns (or positions in the string) to the set $B$ of $M$ strings, where we color an edge from $a \in A$ to $b \in B$ red if $b$ has a $0$ in position $a$ and blue otherwise. It suffices to find a perfect matching between $A$ and $B$ consisting of all red or all blue edges; we will verify Hall's condition for one color to show this.

In particular, notice:

If Hall's condition for $k=1$ is not satisfied by the red edges, there is a position (say, position $1$ ) where all $M$ strings have $1$ . Then, Hall's condition for $k = 1$ must be true for blue edges, as otherwise all $M$ strings read $1$ in position $1$ and $0$ in a different fixed position, while $M > 2^{N-2}$ . So Hall's condition for $k=1$ must be true for either red or blue edges.
Suppose Hall's condition for $k=1$ is true for red edges. Then, if there are two indices, say $1$ and $2$ , where Hall's condition is not true (i.e. at most one string has a $0$ in position $1$ or position $2$ ), it follows that $M-1 \geq 2^{N-2}$ strings have ones in positions $1$ and $2$ . If $M > 2^{N-2}$ , this yields a contradiction; if $M = 2^{N-2}$ , there trivially exists a perfect matching of blue edges among these $2^{N-2}$ strings. Thus, we can verify Hall's condition for $k=2$ .
Finally, for $k \geq 3$ , if Hall's condition is false, then $2^{N-2} + 1 - k > 2^{N-k}$ sets must have $1$ 's in $k$ fixed positions as $N \geq 4$ . This is clearly a contradiction.

So we have verified Hall's condition for red edges (by our WLOG assumption), and thus there exists a perfect matching that corresponds to a solution of the problem.

This post has been edited 1 time. Last edited by HamstPan38825, Jun 9, 2024, 10:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#40 h Dec 21, 2024, 1:16 AM

Y by

iirc this wasn't the most elegant way to articulate the solution (still wip)

The answer is $M=2^{N-2}+1$ . Notice that $2^{N-2}$ flags fails; take all flags where the first two fields are yellow and blue, respectively, so that the first two cells on the main diagonal are necessarily yellow and blue---different colors.

Take $M$ flags and "stack" top-to-bottom into a rectangle with $M$ rows and $N$ columns. Consider Hall's Theorem, which states that---given sets $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ ---and a set $B_i\in B$ corresponding to the "wants" of each $a_i$ , the following holds: if the union of all $\{B_i\}$ for a set of $\{a_i\}$ has size at least equal to the size of the $\{a_i\}$ (so, the size of the union of the wants is at least the number of wanters), then we can choose a value $c_i\in B_i$ which is unique to every $a_i$ (so that every wanter gets a unique want).

Here, the columns are the wanters. We apply Hall's Theorem twice, once for each of the colors yellow and blue.

Consider yellow first. Number the rows from $1$ to $M$ , and the wants for each column are the positions of the yellow fields in each column.

The idea is a proof by contradiction: if $M$ flags fails, then Hall's Theorem must fail on the yellows (WLOG). There exists a group of $c$ columns, such that the size of the union of all their wants is less than $c$ ; that is, the size of union of all rows with a yellow in at least one of the $c$ columns is less than $c$ . The total number of flags is then less than $2^{N-c}+c$ , where $2^{N-c}$ is found through counting the rows not in the aforementioned union---they must have a blue in each of the $c$ columns.

In order to not have a contradiction (which would already solve the problem), we must have $c\in \{1,2\}$ , where $c=3$ fails with $N\ge 4$ .

If $c=2$ , then equality holds---WLOG that in $2^{N-2}$ of the rows, the first two cells are blue, with the rest forming all combinations---with one other (irrelevant) row. In this case, we can easily create a blue diagonal using the first $2^{N-2}$ rows.
If $c=1$ , then all rows must have a blue in the first field. Turns out---repeat the process on an $M\times N-1$ with the first column removed, and we obtain $2^{N-2}+1<2^{N-1-d}+d$ in order to find a fail, with $d\ge 1$ . This does not work.

Now we are done. $\blacksquare$

This post has been edited 3 times. Last edited by asdf334, Dec 21, 2024, 4:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

126 posts

abeot

#41 h Dec 28, 2024, 2:55 AM • 1 Y

Y by centslordm

The answer is $M = 2^{n-2} + 1$ . When $M = 2^{n-2}$ just select all the binary strings starting with $10$ .

Represent a flag $b$ by letting $b(i)$ be its $i$ th digit. Thus, $b(1), b(2), \dots, b(n) \in \{ 0, 1 \}$ .

I will now show that $M = 2^{n-2}+1$ is attainable. Let $T = 1$ . Consider the following assertion:

$\text{For every $1 \le i \le n$, there is at least one flag $b$ with $b(i) = T$.}$
Suppose this assertion is violated. Then set $T = 0$ instead. Now,

Claim: For any $k \ge 2$ digits $d_1, d_2, \dots, d_k$ , there are at least $k$ flags $b$ with $b(d_i) = T$ for some $d_i$ . Otherwise, then we can solve the problem.

Proof. Assume that for some $k$ and choice of $d_1, d_2, \dots, d_k$ , there are at most $k-1$ flags with this property. This implies that there are at least $M-k+1$ flags $b$ that satisfy $b(d_1) = b(d_2) = \dots = b(d_k) = T$ yet there are at most $2^{n-k}$ of these, so $2^{n-k} \ge M-k+1 = 2^{n-2} - k + 2$ I claim that this is only true when $k = 2$ . Check $n = 4$ manually, and otherwise note $2^{n-3} \ge 2^{n-2} - 1 \iff 1 \ge 2^{n-3} \iff n \le 3 \text{, absurd}$ so it fails for $k = 3$ , and furthermore $2^{n-k} < 2^{n-2}-k+2$ $\implies 2^{n-k-1} < 2^{n-3} - \frac{k-2}{2} < 2^{n-2} - (k+1) + 2$ so by induction, it fails for $3 \le k \le n$ .

Thus we must have $k = 2$ . The bound is also true only when we have all $2^{n-2}$ flags with $b(d_1) = b(d_2) = 1-T$ .

If $T = 0$ then all flags $b$ must have $b(j) = 0$ for some $j$ , which is a contradiction. Thus $T = 1$ still.

I contend that by Hall, we can choose some of these $M$ flags to form a binary matrix with a diagonal of all $0$ . It suffices to check that for any $\ell$ digits $e_1, e_2, \dots, e_{\ell}$ , there exists at least $\ell$ flags $b$ with $b(e_i) = 0$ for some $e_i$ . Note $d_1, d_2 \in \{ e_1, e_2, \dots, e_{\ell} \} \implies \text{ all flags work }$ and otherwise, there are at most $2^{n-2-\ell} + 1 \le 2^{n-2}-\ell \le M-\ell$ flags not satisfying the condtion (the bound is just algebra), so some $\ell$ work as needed. $\blacksquare$

Now, assume that the problem is not yet solved, so for any choice of $k$ digits there are at least $k$ flags $b$ such that $b$ 's values in those $k$ digits are not all $1-T$ . Then by Hall, we are done anyways. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cherry265

16 posts

cherry265

#42 h Apr 9, 2025, 11:02 AM

Y by

orl wrote:

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.

I believe there is some ambiguity here, as to whether you can flip a flag upside-down, since it says if the flags can be arranged in a way that satisfies this property.

This post has been edited 1 time. Last edited by cherry265, Apr 9, 2025, 11:02 AM

Z K Y