Mathematical Olympiads and Olympiad problems. Logical problem of arranging dominoes on a chessboard
Tasks for independent
1. Is it possible to cover a 10×10 board with figures?
2. A beetle sits in each cell of a 9 × 9 square. On command, each beetle flies to one of the diagonally adjacent cells. Prove that at least 9 cells will be free after this.
3. Is it possible to lay out an 8×8 square using 15 1×4 rectangles and one
view corner?
4. Is it possible to fold a 6 × 6 square using 11 1 × 3 rectangles and one
corner of the view?
Answers to problems for independent solution
1. Chess coloring. Each such figure occupies an odd number of black cells, which means that all 25 figures also occupy an odd number of black cells.
2. In each cell of a 9 × 9 square sits a beetle.
On command, each beetle flies to one of the diagonally adjacent cells. Prove that at least 9 cells will be free after this.
3. Zebra coloring book. The rectangles occupy an even number of black cells, and the corners occupy an odd number.
4. Let's assume that we managed to fold the square. Let's color the cells in three colors "diagonally", and so that the two "outermost" cells of the corner are the same color (blue). The rectangles will occupy another 11 blue cells, which means that all the figures together occupy 13 blue cells, but there are only 12 blue cells on the board.
Contact information
Creators: Bondareva Polina and Nabieva Zeinab
Contact numbers: 8-905-660-25-23, 8-
Coloring method for solving problems
Nizhny Novgorod
Lyceum No. 180
Reason for choosing the theme | Tasks on the topic |
We chose this topic because it interested us most, and we wanted to learn more about how to correctly format our notes when solving such problems at the Olympiads.
We want to talk about different types coloring books Let's start with the Zebra view. It is most often used for tasks where there are only two types of data. When coloring is used in problems, they usually use white and black or other colors that are opposite to each other.
There are tasks that are characterized by
another coloring: “polka dots”. Using this coloring book you can solve problems of varying complexity. In the figure, each datum (different objects used in the task) is painted with a certain color (you can choose any color). At first glance, it may seem that this coloring has no difficulties, but this is not the case; when a large amount of data is given, this type of solution to the problem will not be optimal. In addition to these types, there are also “three-color” or “diagonal” coloring, used for intermediate-level tasks. The meaning of this coloring is that there must be three data. To do this, you need to select a color in the picture
mark it with your color. For tasks not
the same coloring can be used, since each task has its own coloring method, which we described.
1. Is it possible to lay out a chessboard with thirty-two dominoes so that 17 of them are located horizontally and 15 are located vertically?
Solution: You can use zebra coloring. Horizontal dominoes occupy an odd number of black cells (namely 17), and vertical dominoes occupy an even number.
2. The “camel” figure walks around chessboard move type (1, 3). Is it possible to move with a camel move from an arbitrary field to an adjacent one?
Solution: The camel's move does not change the color of the cell on which it stands, so it will not be able to move to an adjacent cell.
3. The castle has the shape of a regular triangle, divided into 25 small halls of the same shape. There is a door in each wall between the halls. The traveler walks along
castle without visiting any of the castles more than once
halls Find the maximum number of halls that he can visit.
Solution: 21 rooms. Let's color the triangle in a checkerboard pattern. There are 15 halls of one color (for example, black), and 10 of another color (white). Note that a traveler can be in a black hall from the very beginning, or
hit him from white, so he will visit
in no more than 11 black halls. Thus, at least 4 black halls will remain unvisited. An example where the traveler does not visit exactly four halls is constructed without difficulty.
4. Given a board 12 × 12. There are 9 checkers in the lower left corner, forming a 3 × 3 square. In one move, you can choose some two checkers and
rearrange one of them symmetrically
relative to another (without leaving the board). Is it possible to move these checkers in a few moves so that they form a 3 × 3 square in the lower right corner?
Solution: No
(chess coloring -
checkers remain on squares of the same colors).
5. Cut a corner square from an 8×8 board. Can the rest be cut into rectangles?
Solution: three-color coloring
In this lesson we will talk about coloring books and how they help solve problems. Let's consider non-standard cutting and tiling problems and methods for solving them.
Summary of the lesson "Cutting. Tessellation. Coloring."
Coloring pages. Cutting. Tessellations.
Many scientists have been interested in cutting problems since ancient times. Solutions to many simple cutting problems were found by the ancient Greeks and Chinese, but the first systematic treatise on this topic belongs to the pen of Abul-Vef, the famous Persian astronomer of the 10th century, who lived in Baghdad. Geometers seriously began solving problems of cutting figures into the smallest number of parts and then composing one or another new figure from them only at the beginning of the 20th century. One of the founders of this fascinating branch of geometry was the famous puzzle maker Henry E. Dudeney. A particularly large number of pre-existing records for cutting figures were broken by an expert at the Australian Patent Office, Harry Lindgren. He is a leading expert in the field of cutting shapes.
Nowadays, puzzle lovers are keen on solving cutting problems primarily because there is no universal method for solving such problems, and everyone who takes on solving them can fully demonstrate their ingenuity, intuition and ability for creative thinking. Since it does not require deep knowledge of geometry, amateurs can sometimes even outperform professional mathematicians.
To prove that the solution to the problem of cutting a figure into pieces is possible, it is enough to provide some method of cutting. Finding all the solutions, that is, all the cutting methods, is a little more difficult. But it is already quite difficult to prove that cutting is impossible. In some cases, coloring the figure helps us do this.
Task 1: We took a square of 8x8 checkered paper and cut two squares from it (lower left and upper right). Is it possible to completely cover the resulting figure with “dominoes” - 1×2 rectangles?
Task 2. Is it possible to lay out a chessboard with thirty-two dominoes so that 17 of them are horizontal and 15 are vertical?
Task 3: Is it possible to cut a square of checkered paper to size
4×4 for one pedestal, one square, one post and one zigzag?
Task 4: Is it possible to lay out an 8×8 square using 15 1×4 rectangles and one view corner?
Task 5: Is it possible to line a 6×10 rectangle with 1×4 rectangles?
Task 6: Is it possible to fold a 6 × 6 square using 11 1 × 3 rectangles and one corner of the form?
Task 7: On each square of the 5 × 5 board sits a beetle. At some point in time, all the beetles fly up and land on adjacent cells. Prove that this will result in at least one empty cell.
Problem 8: A corner square was cut from an 8×8 board. Can the remaining portion be cut into 3×1 rectangles?
Problem 9: The camel piece moves on the chessboard with a move of the type (1, 3). Is it possible to move with a camel move from an arbitrary field to an adjacent one?
Problem 10: Is it possible to cover a 10×10 board with pieces of the form ?
Problem 11: Given a board 12 × 12. There are 9 checkers in the lower left corner, forming a 3 × 3 square. In one move, you can select any two checkers and rearrange one of them symmetrically relative to the other (without leaving the board). Is it possible to move these checkers in a few moves so that they form a 3 × 3 square in the lower right corner?
Problem 12: In each cell of a 9 × 9 square sits a beetle. On command, each beetle flies to one of the diagonally adjacent cells. Prove that at least 9 cells will be free after this.
Problem 13: The castle has the shape of a regular triangle, divided into 25 small halls of the same shape. There is a door in each wall between the halls. The traveler walks around the castle without visiting any of the halls more than once. Find the maximum number of halls that he can visit. 
Problem 14:For what greatest number of rhombuses, can an equilateral triangle be cut into 36 equilateral triangles?
Problem 15. A 7x7 square contains 16 1x3 tiles and one 1x1 tile. Prove that a 1x1 tile either lies in the center or is adjacent to the boundaries of the square.
Problem 16. Nine pieces are placed in the lower left corner of an 8x8 chessboard in the shape of a 3x3 square. A chip can jump onto a free field through a nearby chip, that is, it can be symmetrically reflected relative to its center (you can jump vertically, horizontally and diagonally). Is it possible, after a certain number of such moves, to place all the chips again in the shape of a 3x3 square, but in a different corner.
Given an 8x8 chessboard, from which two diagonally opposite corners have been cut, and 31 dominoes; Each domino can cover two squares on the board. Is it possible to pave the entire board with bones? Give reasons for your answer.
Solution
At first glance it seems that this is possible. The board is 8x8, therefore, there are 64 squares, we exclude two, which means 62 remain. It seems that 31 dice should fit, right?
When we try to place dominoes in the first row, we only have 7 squares at our disposal, one bone goes to the second row. We then place the dominoes on the second row, and again one tile moves to the third row.
There will always be one tile left in each row that needs to be moved to the next row, no matter how many layout options we try, we will never be able to arrange all the tiles.
The chessboard is divided into 32 black and 32 white squares. By removing opposite corners (note that these cells are the same color), we are left with 30 cells of one color and 32 cells of the other color. Let's say we now have 30 black and 32 white squares.
Each dice we place on the board will occupy one black and one white cell. Therefore, 31 dominoes will occupy 31 white and 31 black cells. But our board has only 30 black and 32 white cells. Therefore, it is impossible to decompose the bones.
The analysis is taken from the translation of the book by G. Luckman McDowell and is intended for informational purposes only.
If you liked it, we recommend buying the book
Task 1: Is it possible to cut a 5 × 5 square into 1 × 2 rectangles (dominoes). Task 2: Opposite corner squares are cut from an 8×8 chessboard. Can the remainder be cut into 1×2 rectangles (dominoes)? Solution: No. Each domino occupies one black and one white cells, and on a board without corners there are different numbers of black and white cells. Task 3: Two 3×3 squares are cut from opposite corners of a 10×10 board. Can the remainder be cut into dominoes? Task 4: Come up with a coherent piece on a chessboard that has an equal number of black and white cells, but which cannot be divided into dominoes. Task 5: Is it possible to cut a 10 × 10 square into 25 shapes? Task 6:Solution: Color the board in a checkerboard pattern. There will be an even number of black cells, and each figure will contain one or three of them. Task 7: Is it possible to cut a 10 × 10 square into 25 shapes? Solution:
Color the board in four colors (see picture). Each figure occupies one cell of each color, and the number of cells of the first and second colors is different.
Directions: Color the board three colors.
Problem 12: What is the maximum number of 1 × 1 × 4 bars that can be cut from a 6 × 6 × 6 cube? Problem 13: The rectangle is divided into figures and. We lost one of them, but replaced it with . It can be proven that it is impossible to cover the original rectangle with a new set. Problem 14: Can a 16×16 square be divided into 64 1×4 rectangles, of which 31 will be vertical and the remaining 33 horizontal? Solution: Paint every fourth vertical. Problem 15: For what n can the square n × n be divided into a) ;b) ? Solution: When n is a multiple of four.
Problem 16: An m × k rectangle is divided into 1 × n rectangles. Prove that m is divisible by n or k is divisible by n.c) for any n. Solution:
Color in n colors.
Problem 17: Prove that a rectangle m × n can be divided into rectangles a × b if and only if the following conditions are satisfied:1) m and n are represented as ka + lb (k and l are non-negative integers)
2) m and n are divisible by a.
3) m or n is divisible by b.
Problem 18: An m × n rectangle is called strong if it can be divided into dominoes such that any cut of the rectangle intersects at least one domino. Prove that:a) rectangle 2 × n - fragile
b) rectangle 3 × n - fragile
c) rectangle 4 × n - fragile
d) 5 × 6 and 6 × 8 rectangles - strong
e) if the rectangle m × n is strong, then the rectangle m × (n + 2) is strong.
f) * 6 × 6 rectangle - fragile
g) Which rectangles are strong and which are not? Solution: f) Hint: Each line in a 6 × 6 square intersects an even number of dominoes.
g) All m × n rectangles, where mn is even, m,n ≥ 5, except 6 × 6.
Problem 19:A corner is a figure of the form.
a) Can a 5 × 9 rectangle be divided into corners?
b) Prove that a rectangle with sides greater than 100 and area divisible by 3 can be divided into corners.
c) Which rectangles can be divided into corners and which cannot?
Problem 20:Is it possible to divide a 2n × 2n board without a corner square into corners? Solution: Yes, you can. The partition is constructed by induction.
Problem 21: For what n can the board (2n + 1) × (2n + 1) without a corner square be divided into dominoes, among which there are equal numbers of vertical and horizontal ones? Solution: For even n.Prove that the checkered board is 10X10 cannot be cut along the grid lines into rectangles 1X4. (Decisions according to D.Yu. Kuznetsov.)
Solution 1 . Divide the board into 2x2 squares and color them in a checkerboard pattern (Fig. 1). Note that any 1x4 rectangle contains equally (2) black and white cells, but with this coloring there are 52 black cells and 48 white cells on the board, i.e. not equally. This means that it will not be possible to cut a 10x10 board into 1x4 rectangles.
Solution 2 . Let's paint the board diagonally in 4 colors (Fig. 2). Note that any rectangle contains one cell of each of the four colors, but with this coloring on the board there are 25 cells of the 1st and 3rd colors, 26 cells of the 2nd and 24 cells of the 4th, i.e. not equally. This means that it will not be possible to cut a 10x10 board into 1x4 rectangles.
1. The lower right and left corner squares were cut out of the chessboard. Is it possible to cut the resulting figure into 1x2 dominoes? What if you cut out the bottom right and top left?
2. Is it possible to cut a 6x6 board into dominoes so that there are exactly 11 horizontal ones among them? (Horizontal coloring in two colors.)
3. Color the drawing in four colors so that adjacent parts are painted in different colors. Is it possible to get by with three colors? (See Activity 6: Coloring geographical map- 5-6th grade).
4. In a 4x4 square, the cells of the left half are painted black, and the rest are white. In one operation, you can repaint all the cells inside any rectangle in the opposite color. How to get a chess coloring from the original coloring in three operations?
5. Several grasshoppers sit on the same straight line, and the distances between neighbors are the same. Every minute one of them jumps to a point symmetrical to it relative to the other grasshopper. Could after some time the grasshopper Sasha end up in the place where his neighbor Lyosha sat at the beginning?
6. a) Is it possible to cut a chessboard into pieces consisting of 4 squares in the shape of the letter “T”?
b) Is it possible to cut a 10x10 chessboard into such figures?
7. Is it possible to divide an 8x8 square with a corner cut off into 1x3 rectangles?
8. Is it possible to cut a 10×10 board into figures from four cells shaped like the letter "L"? (Horizontal coloring in two colors.)
9. An 8x8 board is cut into 2x1 dominoes. Can there be 15 vertical and 17 horizontal dominoes?
10. The triangle is divided into triangles (25 pieces), as shown in the figure. A beetle can walk along a triangle, moving between adjacent (side-by-side) triangles. What is the maximum number of triangles a beetle can go through if it has visited each one no more than once?
11. What is the largest number of rhombuses, each of which is made up of two equilateral triangles with side 1, that can be cut from an equilateral triangle with side 5 (see the figure of the previous problem).
12. The triangular castle is divided into 100 identical triangular halls. There is a door in the middle of each wall. How many halls can a person see who doesn’t want to go anywhere more than once?
