Maths Olympiad Prep

Library / /67 of 75

Combinatorics Difficulty 6.2 National Olympiad Prove it Italy

Problem:

The integers from 11 to 99 are written in the nine cells of a 3×33 \times 3 chessboard, each integer in a different cell, in such a way that every pair of consecutive numbers is written in two adjacent cells (that is, having a side in common). How many possible values are there for the number placed in the central cell?

Solution

Solution:

The answer is 55. In order for the given condition to be realized, it is necessary that one can make a path from the cell with the number 11 to the cell with the number 99 by moving successively from one cell to a cell adjacent to it. Let us color the chessboard in the usual way, so that the corner cells and the central one are black and the others are white. Moving from one cell to an adjacent cell means going from a black cell to a white one, or vice versa. It follows that, if 11 were in a white cell, then 22 would have to be in a black one, 33 in a white one, and so on. Therefore all the odd numbers from 11 to 99, which are 55, would have to be in white cells, while all the even numbers, which are 44, would have to be in black cells: but this is impossible, since there are 55 black cells and 44 white ones. Conversely, it is easy to construct spiral or snake-like paths so that any one of the odd numbers 1,3,5,7,91,3,5,7,9 appears in the central cell.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.