Suppose FTSoC that there isn't such quadrilateral. The idea is to double-count the number $T$ of pairs (quadrilateral, side with two black vertices). On the one hand, each quadrilateral has even number of such sides, hence $T$ is even. But note that each "black" diagonal contributes to two pairs, and each "black" side to one, hence the parity of $T$ is determined only by the number of "black" sides, which is odd: $1+2+...+49=49.25$, contradiction. Remarks: This is quite similar to 2016 C3. In addition, the existence of such quadrilateral is guaranteed for all colorings with odd number of black sides, not just for that particular one (as seen in the solution).

The idea is to double count the number of purely white edges. In a valid quadrilateral-angulation, diagonals are counted twice and edges are counted once. This means that the parity of the total number of purely white edges and diagonals equals the parity of the number of white edges, which is $49 \cdot 25$; thus, it is odd. However, all other configurations of quadrilaterals yield an even number of white edges in each quadrilateral, so it follows that such a quadrilateral must exist.

Incoherent Invariant Solution: This is equivalent to having Dania removing two consecutive vertices until two are left, and considering the quadrilaterals formed by the removed two vertices and the two neighboring vertices. Consider the vertices as alternating runs of the two different colors. Claim: The number of even runs can only change when such a quadrilateral appears. Proof. Suppose not. If the two removed vertices are the same color, then this is equivalent to reducing one of the runs by $2$. By hypothesis, this can't remove a run of length $2$. Else, suppose they are different colors. If the two bordering vertices are the same color, then the result follows as the two runs are merged into an even run. Else, if they are different colors, then this is just removing two odd runs of length $1$. $\blacksquare$ This invariant holds until broken by the desired quadrilateral appears, and since there are more than $2$ such runs.

pretty cool huh Let a $ww$ edge be one such that both vertices are white. Let $x$ be the number of purely white edges along the perimeter of the $2550$-gon; note that $x=49\cdot 25$. Let $y$ be the number of purely white edges when the $2550$-gon is split into disjoint quadrilaterals; i.e., ones that do not share any edges. Clearly each $ww$ edge drawn by Dania will appear in two quadrilaterals; therefore $x\equiv y\pmod 2$. Thus $y$ is odd. However, the only coloring of vertices in a quadrilateral resulting in an odd number of $ww$ edges is exactly described in the problem. So we're done. $\blacksquare$

First, we show that any dissection of a $2n$-gon will contain a quadrilateral whose vertices are consecutive on the $2n$-gon. Consider first drawing any edge that could be a part of a dissection. Then, consider one of the two polygons created. Label the vertices of this polygon $1,2,\dots,k$ where adjacent vertices on the $2n$-gon have adjacent labels. Then, the drawn edge has endpoints with labels $1,k.$ Furthermore, notice that $k$ is even. Now, if we draw another valid edge in this polygon, say, from labels $i$ to $j,$ with $1 \le i<j \le k,$ then the polygon with labels $i,i+1,\dots,j-1,j$ will be a smaller polygon, also with an even number of vertices, since this edge must also be part of a dissection. Repeat this, each time drawing an edge in a polygon with all vertices adjacent, until one of them has $4$ vertices. This must happen, since each time the number of vertices decreases, and it must be even and cannot reach $2$ or $0.$ Next, consider dissecting the polygon by drawing only edges that separate $4$ vertices in the smallest polygon containing them. Each of these operations can be seen as removing the middle two vertices. Additionally, suppose, for the sake of contradiction, that we do not draw edges that form a quadrilateral with $2$ adjacent black vertices and $2$ adjacent white vertices. Then, after considering all possible quadrilaterals, we see that our only valid operations are decreasing the length of a run of the same color by $2$ in such a way that it must end up greater than or equal to $1,$ or deleting a run of length $1,$ and replacing the adjacent runs of length $a,b$ with a run of length $a+b-1.$ However, now we consider the parities of the lengths of our runs. Letting $E$ denote an even length and $O$ an odd length, what we notice is that our polygon has runs $OOEEOOEE \dots OOEE.$ Considering our valid operations on runs, we notice that the first one changes $E$ to $E,$ and the second one changes $OOE$ or $EOO$ to $E.$ Thus, in our polygon, all we can do is delete the string $OO.$ Once this is done, we will still have $50$ runs with $E,$ however, if there existed a dissection of our polygon without the special type of quadrilateral mentioned in the problem, then it would possible to reduce our polygon to two vertices. However, this string of $E$s cannot be reduced further than $50 \cdot 2=100$ vertices, contradiction. Thus there must exist such a quadrilateral.

The number of edges with black vertices is $1 + 2 + 3 \dots + 49 = 49 \cdot 5 \equiv 1\pmod{2}$. Since diagonals don't count to our total$\pmod{2}$, since they are double-counted, the only edges that matter are the non-diagonals. The only configuration that leads to an odd number of non-diagonal edges is a quadrilateral with 2 black vertices, so we are done.

Notice that for all possible colorings of a quadrilateral, only the specified quadrilateral in this problem will create a odd number of black edges. Thus, we just need to prove the sum of the number of black edges of all the quadrilaterals is odd. For each black edge on the perimeter of this polygon, it will be included in exactly one quadrilateral, which is $$0+1+2+\dots+49=25 \cdot 49.$$For each black edge (diagonal) inside this polygon, it will be counted twice (so it won't matter). Since $25 \cdot 49$ is odd, we are done. \qed

DCW-Global yay

Attachments: