I'm probably misunderstanding the problem, but why are the $B_i$ colors needed? We can do a 2-coloring of the regions as in EGMO 2017/3 and so all $n$ work?

L567 wrote: I'm probably misunderstanding the problem, but why are the $B_i$ colors needed? We can do a 2-coloring of the regions as in EGMO 2017/3 and so all $n$ work? Yikes, totally forgot the key part of the problem (all of the problems I posted are from memory, as I don't have the actual problems). Should be fixed now - all color combinations must appear at least once.

The answer should be $n\ge 5$ I proved that the graph of regions is bipartite and if two regions have distance $\ge 5$ then we are done. Then I failed to prove two regions have distance $\ge 5$.

Imagine getting more progress than me i think i got n=3,4 doesn't work

bruh there are so many people better than you. I don't know the final part seems very easy but I can't do it without casework bash. Alternatively, since 5=5, we may be able to prove this claim with induction, but in contest I fakesolved because I don't understand how lines and regions behave

Quote: bruh there are so many people better than you. I am aware. also i think induction would work n=3 clearly works. then you can prove that each time you add a line, one of the n+1 regions you go through is split by this new line? edit1: in the graph theory representation pick a path such that upon removal of these points on the paths the graph becomes disconnected? combined with extremal pinciple this might work

MortemEtInteritum wrote: A coloring is an assignment MortemEtInteritum wrote: A number $n$ is colourable if Typical Canadians being unable to decide whether to use American or British english...

CANBANKAN wrote: The answer should be $n\ge 5$ I proved that the graph of regions is bipartite and if two regions have distance $\ge 5$ then we are done. Then I failed to prove two regions have distance $\ge 5$. If $n\le 4$, setting $n$ parallel lines divide the plane into $n+1$ regions, so it fails. It remains to show $n\ge 5$ works. Consider a graph where each vertex corresponds to a region and there is an edge between two vertices if and only if their corresponding regions intersect at a line. We can represent each region with a binary number with $n$ digits, where for $j=1,\cdots,n$, a 1 on bit $j$ indicates it is on one fixed side of line $j$, and 0 on bit $j$ indicates it is on the other side. Claim 1: This graph is bipartite. Proof: It suffices to show that all cycles of the graph have even length. Note two vertices are adjacent if and only if their binary numbers differ by exactly one digit. Therefore, each line must be crossed an even number of times for me to go back to the region I started with. Claim 2: This graph has 2 vertices with distance $5$ (in fact, $n$). Proof: Note $n\ge 5$. If a line is not parallel to any of the other lines, it must intersect with all regions, so we can induct down. Otherwise, each line is parallel to another line, so we can casework on $n=4$ and $n=5$. Claim 3: A coloring exists if the distance between two vertices is at least 5. Proof: Suppose $dist(u,v)\ge 5$. Let $S_j=\{ w | dist(u,w)=j\}$ for $j\in \mathbb{N}$. Since the graph is bipartite, the induced subgraph of $S_j$ is an anticlique. By the definition of distance, there are no edges between $S_i$ and $S_j$ if $|i-j|\ge 2$. We color all vertices in $S_j$ with color $A_{(j \bmod\; 2)}, B_{(j\bmod\; 3)}$, which works for reasons explained above.

Let $n$ be a positive integer. A set of n distinct lines divides the plane into various (possibly unbounded) regions. The set of lines is called “nice” if no three lines intersect at a single point. A “colouring” is an assignment of two colours to each region such that the first colour is from the set $\{A_1, A_2\}$, and the second colour is from the set $\{B_1, B_2, B_3\}$. Given a nice set of lines, we call it “colourable” if there exists a colouring such that (a) no colour is assigned to two regions that share an edge; (b) for each $i \in \{1, 2\}$ and $j \in \{1, 2, 3\}$ there is at least one region that is assigned with both $A_i$ and $B_j$ . Determine all $n$ such that every nice configuration of $n$ lines is colourable.

The answer is all $n \ge 5$. Consider the corresponding graph $G$. As shown in above posts, $G$ is bipartite. We consider assigning :- $A_1,A_2$ as coloring the region with two colors red and blue. $B_1,B_2,B_3$ as writing $1,2,3$ in the regions. Then we have to ensure that: All numbers get written in regions of both colors. Two adjacent regions don't have the same number written in them. It isn't hard to verify all $n \le 4$ don't work. This is true even when lines are not allowed to be parallel! For $n \le 3$, this is easy to see. For $n=4$, we do the work below: Assume contrary. Note any configuration of four lines will look something like above. We color the regions red and blue. WLOG assume that the inner red quadrilateral region has $1$ written in it. Now $2,3$ should also be written in red regions. The only four red regions are around $1$. Now $2,3$ must be written diagonally opposite regions, otherwise a blue region sandwiched between three of those red regions can have no number written in it. So we have two choices. Both of them are shown below. And the other case is: In both cases, numbers of rest of regions get automatically determined and $1$ gets written in none of the of the blue regions, which is a contradiction. $\blacksquare$ Now we prove that for each $n \ge 5$, a construction exists. Claim: If we could find a red region $R_0$ and a blue region $B_0$ such that their distance (wrt $G$) is $>3$, then we are done (i.e. such a construction exists). Proof: Intially write a $1$ in all red regions and a $2$ in all blue regions. Denote by $N(v)$ the set of neighbours of $v$. We do some rewriting: Rewrite a $3$ in all regions of $N(R_0) \cup N(B_0)$. Rewirte a $2$ in $R_0$. Rewrite a $1$ in $B_0$. Note that all numbers get written in regions of both colors. So we just have to note no two adjacent regions have same number written in them. By construction, we just have to verify that no two regions in $N(R_0)$ and $N(B_0)$ are adjacent, and that just follows by the fact that distance between $R_0$ and $B_0$ is $>3$. $\square$ So lastly, to solve the problem it suffices to show that we can always find two regions that have distance $\ge 5$ among them. To prove this, we use a similar idea as in the official solution. Due to rotation WLOG assume that none of the lines is horizontal. Further by translation we may assume all regions lie above the $x$-axes (for infinite regions, we only look at their relevant part). Let $R_1$ denote the region to the almost right and $R_2$ denote the region to the almost left. Then $R_1,R_2$ have a distance of $\ge n$ among them, because of the following: For any line $\ell$ among those $n$ lines, $R_1,R_2$ lie on opposite sides of $\ell$. So to go from $R_1$ to $R_2$, we have to cross all the $n$ lines. In a step we can jump over at most one line, so at least $n$ edges are required. $\blacksquare$ This completes the proof!