Combinatorics, Colorings
Coloring problems involve assigning 'colors' (labels) to objects (like regions of a map, vertices/edges of a graph, or squares on a board) subject to certain constraints (e.g., adjacent objects must have different colors). Questions ask if a coloring is possible or seek the minimum number of colors.
Chessboard Coloring-
Question
The magical land consists of `25` provinces. Is it possible that each province borders an odd number of other provinces?
-
Question
A number of lines and circles are drawn in the plane. Prove that it is possible to color the regions into which the plane is divided using two colors such that neighboring regions (those sharing a line segment or arc) are colored with different colors.
-
Question
The plane is divided by n lines and circles.
Prove that the resulting map can be colored with two colors such that any two adjacent regions (separated by a segment or an arc) are colored with different colors.
Sources: -
Question
Given an infinite grid whose vertices are colored with two colors, blue and red. Prove that there exist two horizontal lines and two vertical lines such that their four intersection points are colored with the same color.
Sources:Topics:Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry Combinatorics -> Colorings- Zebra Exercises, 2018-2019, Exercise 1 Question 1
-
Circle and Three Points
A circle is drawn on the board, and three points are marked on it in the following colors (clockwise): green, blue
and red. Jonathan is playing the following game – in each step he can do one of the following:
a) Choose two adjacent points with different colors and draw a point between them in one of these two colors
only.
b) Choose two adjacent points with identical colors and draw a point between them in any color.
c) Choose three adjacent points where at least two of them are the same color, and erase the middle one.Can Jonathan reach a state where there are three points left on the board in the following colors (clockwise): blue, green, red? Justify your answer.
Sources:- Gillis Mathematical Olympiad, 2015-2016 Question 4
-
The Beaver and the Mole
There is a plot of land in the shape of a square `4 times 4` divided into cells of `1 times 1`. The beaver wants to build a house on it that occupies 4 cells, which from a top-down view looks like this:
The mole wants to disturb him. For this purpose, it can dig holes, each of which occupies one cell. It is impossible to build on the cells that have become holes. What is the smallest number of holes the mole needs to dig so that the beaver cannot build the house?
Sources: -
More Game Cubes
Aviv has game cubes, where two opposite faces of each are painted red and the rest are blue.
Sources:
Aviv glued together a `3 xx 3 xx 3` cube from the game cubes. Then his friend Kfir came and calculated the total red area on the surface of the large cube.
What is the largest result Kfir can get? -
Drawing Board
A painter has a `10 times 10` grid. Each time, the painter chooses a row or column and paints it entirely with a color of their choice.
Sources:
If they pass over a square that has already been painted with a new color, the new color completely covers the old color,
that is, the color of the square changes.
What is the largest number of colors we can see on this board? -
Question
There are 5778 extinguished lamps arranged at equal distances on a circle. Below each lamp is a button. Pressing a button changes the state of 4 lamps: the lamp next to the button, the next two lamps in the circle clockwise, and the lamp opposite the button (an extinguished lamp lights up when its state is changed, and a lit lamp is extinguished). What is the maximum number of lamps that can be lit simultaneously?
Sources:Topics:Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings- Beno Arbel Olympiad, 2017, Grade 8 Question 8
-
A PROBLEM IN MOSAICS
The art of producing pictures or designs by means of joining together pieces of hard substances, either naturally or artificially coloured, is of very great antiquity. It was certainly known in the time of the Pharaohs, and we find a reference in the Book of Esther to "a pavement of red, and blue, and white, and black marble." Some of this ancient work that has come down to us, especially some of the Roman mosaics, would seem to show clearly, even where design is not at first evident, that much thought was bestowed upon apparently disorderly arrangements. Where, for example, the work has been produced with a very limited number of colours, there are evidences of great ingenuity in preventing the same tints coming in close proximity. Lady readers who are familiar with the construction of patchwork quilts will know how desirable it is sometimes, when they are limited in the choice of material, to prevent pieces of the same stuff coming too near together. Now, this puzzle will apply equally to patchwork quilts or tesselated pavements.
It will be seen from the diagram how a square piece of flooring may be paved with sixty-two square tiles of the eight colours violet, red, yellow, green, orange, purple, white, and blue (indicated by the initial letters), so that no tile is in line with a similarly coloured tile, vertically, horizontally, or diagonally. Sixty-four such tiles could not possibly be placed under these conditions, but the two shaded squares happen to be occupied by iron ventilators.
The puzzle is this. These two ventilators have to be removed to the positions indicated by the darkly bordered tiles, and two tiles placed in those bottom corner squares. Can you readjust the thirty-two tiles so that no two of the same colour shall still be in line?
Sources:- Amusements in Mathematics, Henry Ernest Dudeney Question 302