Maths Olympiad Prep

Library / /474 of 520

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it

Some cells of a checkered plane are marked so that figure AA formed by marked cells satisfies the following condition:1)1) any cell of the figure AA has exactly two adjacent cells of AA; and 2)2) the figure AA can be divided into isosceles trapezoids of area 22 with vertices at the grid nodes (and acute angles of trapezoids are equal to 4545) . Prove that the number of marked cells is divisible by 88.

Solution

1. Understanding the Problem:
We are given a figure A A formed by marked cells on a checkered plane. The figure A A satisfies two conditions:
- Any cell of the figure A A has exactly two adjacent cells of A A .
- The figure A A can be divided into isosceles trapezoids of area 2 2 with vertices at the grid nodes, and the acute angles of the trapezoids are 45 45^\circ .

2. Analyzing the Isosceles Trapezoids:
Each isosceles trapezoid has an area of 2 2 . Given that the acute angles are 45 45^\circ , the trapezoids are right-angled isosceles trapezoids. The height of each trapezoid is 1 1 unit, and the bases are 1 1 unit and 2 2 units respectively.

3. Midlines of Trapezoids:
Consider the midlines of each trapezoid. The midline of a trapezoid with bases 1 1 and 2 2 units is 1.5 1.5 units. However, for simplicity, we can scale down the problem such that each midline is 1 1 unit.

4. Properties of the Polygon Formed by Midlines:
- Every side of the polygon is either vertical or horizontal and has an integer length.
- The sides alternate between vertical and horizontal.
- If a side has an even length, the adjacent sides go in opposite directions (neighboring angles sum to 360 360^\circ ). If a side has an odd length, the adjacent sides go in the same direction.

5. Proving the Perimeter is Divisible by 4:
We need to show that the perimeter of the polygon formed by the midlines is divisible by 4 4 .

6. Carving Out Squares:
- If there are two adjacent sides with lengths greater than 2 2 , we can carve out or attach a 2×2 2 \times 2 square to decrease the sum of the squares of all sides while preserving the perimeter.
- Eventually, we arrive at a polygon where out of any two adjacent sides, one has a length 2 \leq 2 .

7. Handling Sides of Length 1:
- If there are two adjacent sides of length 1 1 , the polygon is a 1×1 1 \times 1 square with a perimeter of 4 4 .
- If there is a side of length 1 1 , we can cut out a 1×2 1 \times 2 square from the side of length 1 1 , preserving the perimeter modulo 4 4 .

8. Final Case:
- If all side lengths are even, we can scale down by 12 \frac{1}{2} , and any lattice polygon has an even perimeter.
- If there is an odd side, we keep carving out 2×2 2 \times 2 squares until the odd side has only a length 1 1 part left. Then, we use the previous operation on sides of length 1 1 to strictly decrease the perimeter.

9. Conclusion:
- Eventually, we must arrive at a 1×1 1 \times 1 square, and we have preserved the perimeter modulo 4 4 with each operation.
- Therefore, the number of marked cells is divisible by 8 8 .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.