Combinatorics and Coloring (Part 3)
There is also a type of combinatorics that is very famous in international competitions like the IMO, the IMC, or PUTNAM: coloring problems. In this blog, I will share a problem:
Given that m and n are two positive numbers that are larger than 3. A board has the size m x n. A student must put small brick figures on the board. The figures look like this:
-
Can the board filled fully with figures when m=2022, n=2024?
-
Can the board filled fully with figures when m=2023, n=2024?
Another famous problem that has appeared in many math competitions is:
Prove that: If each point on the surface is colored with one of the three colors then their exists 2 same colored points that have the distance of 1.
We construct a rhombus CDEF with 2 equilateral triangles CDF and EDF whose sides are 1. According to the Dirichlet theorem, among the 4 points, there are 2 points that have the same color. If that pair is (C,D),(C,F),(D,E),(E,F),(D,F), we are done.
If that pair is C,E, we will construct another rhombus CGHI. So C,E,I are the same color and similarly, every points on the circle (C,CE) must have the same color. We will choose on that circle 2 points that they have the distance of 1. (Q.E.D)