Maths Olympiad Prep

Library / /2 of 4

Combinatorics Difficulty 6.2 National olympiad Find the answer

A natural number is written in each cell of an 8×88 \times 8 board. It turned out that for any tiling of the board with dominoes, the sum of numbers in the cells of each domino is different. Can it happen that the largest number on the board is no greater than 3232?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine if it is possible for the largest number on an 8×88 \times 8 board to be no greater than 32 while ensuring that the sum of numbers in the cells of each domino is different for any tiling, we must consider how domino tiles cover such a board.

### Understanding Domino Tiling

A domino covers two adjacent cells, either horizontally or vertically. For an 8×88 \times 8 board, there are a total of 64 cells, meaning we need 32 dominos to completely cover the board. Each domino will cover exactly two cells.

### Objective

We need to find a way to assign numbers to each cell of the board such that for all possible tilings, the sum of the numbers within the cells covered by each domino is unique. Specifically, we want the largest number on the board to be no greater than 32.

### Construction

One effective method to achieve this is to use the concept of parity. Assign numbers to the cells in a way that ensures each domino sum is unique by ensuring sums have a specific property relative to parity:

1. Parity Approach: Assign numbers to the board in a checkerboard pattern such that all numbers on black squares are odd and all numbers on white squares are even (or vice versa).

2. Value Assignment: Given that numbers can go up to 32:
- Assign numbers within 1 to 32 such that the sum of a number from a black square and a number from a white square is unique for each domino.

### Example

Suppose we fill the board such that:

- Black squares contain odd numbers only: {1, 3, 5, ..., 31}.
- White squares contain even numbers only: {2, 4, 6, ..., 32}.

By using only odd numbers for one type of square and only even for the other, any domino covering two adjacent squares (one black and one white) will have a sum that is distinctly odd (since an odd number plus an even number equals an odd number) ensuring all possible tiling sums are unique.

### Conclusion

By employing a parity-based approach, we have shown that it is indeed possible to fill each cell of an 8×88 \times 8 board with natural numbers not exceeding 32 while ensuring varying domino sum values. Therefore, the answer to the problem is:
Yes \boxed{\text{Yes}}
This solution ensures that all possible domino sums are different by keeping them consistently odd or spaced uniquely if constructed beyond parity, enabling control over domino sums even with a maximum cell value constraint of 32.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.