Maths Olympiad Prep

Library / /9 of 16

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Japan

As shown in the figure, seven regular hexagonal cells form a hexagonal pattern. We write one integer from 11 to 77 in each cell without repetition. For any two cells that share an edge, the sum of the integers written in those cells must be at most 1010. How many ways are there to write the integers under these conditions?

Note that two labelings that coincide by rotation or reflection are counted as distinct ways.

Figure 1

Solution

7272

Since the sum of the integers in any two adjacent cells must be at most 1010, the only possible integers that can appear in the neighbors of the cell containing 77 are 11, 22, or 33. Therefore, the cell labeled 77 cannot be the central cell, and there are exactly 66 possible cells in which to place the 77.

By symmetry, the total number of labelings is 66 times the number of labelings in which the leftmost cell contains 77. Suppose the leftmost cell contains 77, and denote this cell by AA. We classify the other six cells into three groups, BB, CC, and DD, as shown in the left diagram below.

Figure 2
Figure 3

The three cells in group BB are all adjacent to AA, so they must be labeled with 11, 22, or 33 in some order. The remaining three cells in groups CC and DD must be labeled with 44, 55, and 66. Since the two cells labeled 55 and 66 are not adjacent to each other, both of them must lie in group CC (which consists of two cells), and the cell in group DD must be labeled 44.

Conversely, any labeling satisfying these assignments clearly meets the condition that each pair of adjacent cells sums to at most 1010. There are 3!3! ways to assign {1,2,3}\{1, 2, 3\} to the three cells in BB, and 2!2! ways to assign {5,6}\{5, 6\} to the two cells in CC. Hence the total number of labelings is 6(3!2!)=726 \cdot (3! \cdot 2!) = 72.

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 and solution reproduced as published; topic and difficulty added by this site.