Tricolored polygon

Given a regular $(3n+2)$-gon, the vertices are colored with red, blue, or green such that there are $n+1$ green points, $n+1$ blue points, and $n$ red points. Prove that there exists a line going through a blue point and a green point, such that on one side of the line there are $k$ points of each color, and on the other side there are $(n-k)$ of each color (with $k \geq 0$).

Solution

First we claim that there is a way to pair each blue point with a green point such that the segments formed by each pair is non-intersecting. Proof:

Delete all the red points for now, so we are left with polygon with $(n+1)$ blue and green points each. Take any adjacent pair of a blue point and a green point, pair them, and then delete them. Now we are left with $n$ blue and green points each. Recursively apply this procedure until we are done. It's easy to see that the resulting segments are non-intersecting.

Now that we have $n+1$ such segments, label the points $(b_1, \dots, b_{n+1}, g_1, \dots, g_{n+1})$ where $b_i$ is a blue point that is paired with $g_i$. Let $S_i$ denote the segment formed by $b_ih_i$. Pick an arbitrary red point $R$. We define the following terminology: each segment divides the polygon into two. The "good" side of the segment is the side that contains $R$.

Since no two segments can intersect, then for two different segments $S_i,S_j$, one is fully on the good side of the other. If $S_i$ is fully contained in the good side of $S_j$ then we say that $S_j$ "covers" $S_i$. Note that for any two segments, if $S_i$ covers $S_j$ then $S_j$ does not cover $S_i$, and one necessarily covers the other.

Note the following properties. If $S_a$ covers $S_b$ and $S_b$ covers $S_c$ then $S_a$ covers $S_c$. Conversely, if $S_a$ and $S_b$ both cover $S_c$ then either $S_a$ covers $S_b$ or $S_b$ covers $S_a$. So we may define the relationship called "immediate covering." We say $S_a$ immediately covers $S_b$ if $S_a$ covers $S_b$ and there's no other $S_c$ such that $S_a$ covers $S_c$ and $S_c$ covers $S_b$.

Consider the graph with $n+1$ vertices $1,2,\dots,n+1$ and the edges where $i \to j$ if $S_i$ immediately covers $S_j$. Each segment can only be immediately covered by at most one other segment, so this graph is a tree. It cannot be a forest because for each root of each tree, one necessarily covers the other so there can only be one true root. Define the "height" of each node to be the distance between node $i$ to it's farthest leaf. So every leaf has height zero. If $i$ is a leaf and $S_j$ immediately covers $S_i$ (and only $S_i$), then $j$ has height 1, and so on. If a node has several children of differing heights, then the height of the node is 1 plus the maximum of its children's height.

Now also for each $i$, define $A_i$ to be the number of red points that are located on the good side of $S_i$. Define $B_i$ to be the number of descendants of $i$ in the above-mentioned graph. So, our aim is to show that there exists an $i$ such that $A_i = B_i$, because this would mean that on the good side of $S_i$, there are precisely $A_i$ red points, and $B_i$ segments, each of which contains $B_i$ blue points and $B_i$ green points. Now suppose, in our configuration, there is no $i$ such that $A_i = B_i$.

Our claim now is that for each $i$, $A_i > B_i$. We prove this by induction on the height of the nodes.

We start by looking at the leaves. If there's any leaf $i$ with $A_i = 0$ then there is a contradiction, because $B_i = 0$. So for each leaf $i$, $A_i \geq 1 > 0 = B_i$.

Now suppose that $A_i > B_i$ (which means $A_i \geq B_i + 1$) for each node of height $0, 1, \dots, k$, then let $S_a$ be a node of height $k+1$, and let its children be $S_{b_1}, \dots, S_{b_m}$. Its children has height at most $k$, so for each $i$, $A_{b_i} \geq B_{b_i}$ holds. Now, each red point on the good side of $S_{b_i}$ is also on the good side of $S_a$, therefore $$A_a \geq A_{b_1} + \dots + A_{b_m} \geq (B_{b_1} + 1) + \dots + (B_{b_m}+1) = m + \sum B_{b_i} = B_a$$ The first inequality is due to the fact that each red point in $A_{b_i}$ must be contained in $A_a$ as well (although there may be more red points in $A_a$. The second inequality is from induction hypothesis. The third inequality is by construction of the graph and definition of $B_a$, because the number of descendants of $S_a$ can be counted by summing the number of descendant of children, plus each of the children themselves.

So we established that $A_a \geq B_a$, but because we assumed that there is not $A_i = B_i$, then $A_a > B_a$. Thus, by induction on the height of each node, we can claim that $A_i > B_i$ for each $i$ in the whole graph.

Now consider the root node $r$. We concluded that $A_r > B_r$. But $A_r$ is the number of red points on the good side of $S_r$, which is at most $n$. $B_r$ is the number of descendants of $S_r$, which is $n$. Contradiction.

Thus there must be an $i$ such that $A_i = B_i$ and that is our desired segment.

Lights forming a hexagon

Six lights are placed such that they form a regular hexagon. At each turn, we're allowed to do one of the following:

1. Toggle three consecutive lights

2. Toggle three lights that form an equilateral triangle

3. Toggle two diametrically opposite lights

Prove or disprove, for any given starting configuration, we can turn off all the lights through a series of turns as described above.

Solution

Answer: we cannot.

Label the lights as 1,2,3,4,5,6, and denote each move as follows:

$A_i$: toggling lights $i, i+1, i+2$. There are 6 such moves: $A_1, \dots, A_6$.

$B_i$: toggling an equilateral with $i$ as one of its vertices. Obviously we only need to consider $B_1, B_2$.

$C_i$: toggling $i$ and its opposite. Again, we only need to consider $C_1, C_2, C_3$.

$D$: toggling all the lights. Although this is not one of the moves allowed explicitly in the problem statement, it can be achieved by the combination of $A_1+A_4$ (as well as many others), so it is effectively a legal move.

From a set of moves, we're allowed to remove it if it can be achieved by a combination of all the other moves remaining in the set. So from the set of all the moves described above, we can remove $A_4, A_5, A_6$ because they can be achieved by $D + A_1, D+A_2, D+A_3$ respectively.

Likewise, we can remove $B_2 = B_1 + D$ and $C_3 = C_1+C_2+D$. So now we're down to $\{A_1,A_2,A_3,B_1,C_1,C_2,D\}$. Now notice that: $A_2 = C_1 + A_1$, $A_3 = C_1 + C_2 + A_1$ so we remove them as well, leaving us with $\{A_1,B_1,C_1,C_2,D\}$.

Now although the number of possible move sequences is infinite, the number of reachable configurations from an all-off configuration is limited. There are five moves left in our set. We have not yet proved that they're all truly independent (i.e. we can no longer remove any more), but we don't need to. For each move in that set, it only matters whether that move is performed an even or odd number of time. In algebraic lingo, these moves are commutative and self-inverse. So that means there are at most $2^5$ configurations reachable from an all-off configuration, but we have $2^6$ total configurations. Each sequence of moves are its own inverse, so that means there are 32 configurations such that we cant turn off all the lights.

If we're asked to identify such configuration, we note the following: the configuration where only 1 light is on is not reachable from an all-off configuration. If this were possible, then we could apply that same sequence of moves (rotated appropriately) to achieve any desired configuration.

An equilateral with side $n$ is divided into smaller equilaterals with size 1 so that they form a triangular lattice. Each segment of length 1 is colored either red, blue, or green. A coloring is called "good" if every equilateral has sides of three different colors. How many good colorings are there? Two colorings are called distinct if at least one segment is colored differently. For example, with $n=1$, there are 6 good colorings. With $n=2$, there are 48 colorings.

A Divided Kingdom

A kingdom has the shape of a convex $n$-sided polygon $A_1 \dots A_n$. The King owns a castle at point $O$ in the interior of the kingdom, and he has $n$ princes, $P_1, \dots P_n$. They are each given a castle at the vertices of the polygon, so that prince $P_i$ has a castle precisely at $A_i$. The area $OA_iA_{i+1}$ is called the province $i$.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:
1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.

Graph with degree 3

A graph where each vertex has degree 3 has all of its edges colored with red, green, or blue. How many colorings are there such that every 3 edges that meet in a vertex are either of the same color or have 3 different colors?

Colored chessboard

An $n \times n$ chessboard is put on the table such that its sides are facing the North, East, South, and West. Each cell is then colored either with red, green, blue, or yellow paint such that:
1. The North-most cells are colored only with red or green
2. The East-most cells are colored only with green or blue
3. The South-most cells are colored only with blue or yellow
4. The West-most cells are colored only with yellow or red

Prove that there is a point that serves as a vertex to at least three squares of different colors.

Solution


For each cell that has color red, green, blue, and yellow, give it a rank of 1,2,3, and 4 respectively.

Then for each "side" (a segment of line between two cells), mark it if:
1. It delineates two cells. That is, sides that coincides with the sides of the large chess board cannot be marked.
2. Those two cells have a rank differing by exactly 1.

Now, for each vertex, give it a score as follows:
1. The score of each vertex is the number of marked sides that border it. Thus, each cell might have a score of 0, 1, 2, 3, or 4.
2. Vertices that lie on the sides of the large chess board also get their own score. These vertices cannot have a score of 4 of course, but give it a score regardless. Call these vertices the "border vertices" as opposed to "inner vertices"

We assert the following: if an inner vertex has an odd score, then it serves as a vertex to at least three squares of different colors. In other words, an inner vertex with an odd score is the vertex whose existence we seek to prove.

Indeed, it is impossible to form an inner vertex with a score of 1 or 3 with merely one or two colors. For example, if the four squares surrounding the vertex has colors R,G,G,R, then the squares would have ranks of 1,2,2,1, and there are two marked sides. The other combinations are left to the reader as an exercise.

Now, let $A$ be the sum of scores among the inner vertices, and $B$ be the total number of scores among the border vertices. $A+B$ must be even since each marked side contributes two points of score to that total.

We will show that $B$ is odd. The Northwest (NW) corner must be colored red, and the NE corner must be colored green, and the North side must be colored only red or green. Thus, the North side changes color an odd number of times, and each change of color is between a red and a green, producing an odd number of marked sides in the process. These marked sides contribute 1 point each to $B$.

The same argument can be made to the East side and the South side, but not the West side. In fact, none of the color changes on the West side contribute to $B$ at all since they're between a cell of rank 1 and rank 4. So in total, $B$ is a sum of three odd numbers, which means $B$ is odd.

Since $A+B$ is even, then $A$ is odd. That means there must be at least one inner vertex that has an odd score, showing the existence of our desired vertex.

Triangular (and tetrahedral) lattice

An equilateral triangle $ABC$ with side $n$ a positive integer is divided into triangular lattice consisting of unit triangles.

Each point on the lattice is colored red, white, or blue such that:
1. No point on $AB$ is colored red
2. No point on $BC$ is colored blue
3. No point on $AC$ is colored white

Prove that there exists a unit triangle whose vertices are colored with 3 different colors.

Challenge problem: Same problem but for tetrahedron and four colors.

Solution

We first state the one-dimensional version of this problem:

Given a sequence of points on a line colored red or blue, and the first point must be colored red, and the last point must be colored blue, then we have an ODD number of segments that has two differently-colored end points.

This one-dimensional version is trivial to prove.

Now we turn to the 2-dimensional version as stated in the problem.
For each side that has both red and blue endpoints, we "mark" that side.
Then for each unit triangle, we give it a score based on how many marked sides it has. Now, if we consider the "outside" area as another "surrogate unit triangle", then we can also give it a score based on how many marked sides are facing the outside.

First, note that the total score of all areas must be even, since any marked side contribute one score to two areas.

Now, applying the 1-dimensional version of the problem, we know that side AC has an odd number of marked sides. Side AB and BC does not have any marked sides. So the outside area has an odd score. Thus, there is an odd number of unit triangles that has an odd score. In order for a unit triangle to have an odd score, it must have three differently-colored vertices.

Chess Board Coloring

Each cell in an infinite chess board is colored with one of the $n$ available colors. Prove that we can always find a rectangle such that all four corners have the same color.

Advanced version: Suppose not all cells are colored, but only some of them. Furthermore, for any circle with radius R, we can always find a colored cell in that circle. Prove that we can still find a monochromatic rectangle.

Circles and Coloring

Several circles are drawn on a piece of paper to form several regions on the paper. We wish to color these regions such that no two regions that share a common boundary would have the same color.

(It is okay if two regions that share a common point to have the same color, but not boundary)

How many colors minimum are needed?