Track / Stage 7 / 207 of 300 #1607 of 1964

Problem 1607

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.4 Prove it China Southeastern Mathematical Olympiad · China

Suppose that 12 acrobats labeled $1$ – $12$ are divided into two circles $A$ and $B$ , with six persons in each. Let each acrobat in $B$ stand on the shoulders of two adjacent acrobats of $A$ . We call it a tower if the label of each acrobat of $B$ is equal to the sum of the labels of the acrobats under his feet. How many different towers can they make?

(Remark. We treat two towers as the same if one can be obtained by rotation or reflection of the other. For example, the following towers are the same, where the labels inside the circle refer to the bottom acrobat, the labels outside the circle refer to the upper acrobat.)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Denote the sum of labels of $A$ and $B$ by $x$ and $y$ , respectively. Then $y = 2x$ . Thus, we have
$3x = x + y = 1 + 2 + \cdots + 12 = 78, \quad x = 26.$
Obviously, $1, 2 \in A$ and $11, 12 \in B$ . Denote $A = \{1, 2, a, b, c, d\}$ , where $a < b < c < d$ . Then $a + b + c + d = 23$ , and $a \ge 3$ , $8 \le d \le 10$ (if $d \le 7$ , then $a + b + c + d \le 4 + 5 + 6 + 7 = 22$ , which is a contradiction.)

(1) If $d = 8$ , then $A = \{1, 2, a, b, c, 8\}$ , $c \le 7$ , $a + b + c = 15$ . Thus, $(a, b, c) = (3, 5, 7)$ or $(4, 5, 6)$ , that is, $A = \{1, 2, 3, 5, 7, 8\}$ or $A = \{1, 2, 4, 5, 6, 8\}$ .

If $A = \{1, 2, 3, 5, 7, 8\}$ , then $B = \{4, 6, 9, 10, 11, 12\}$ . Since $B$ contains $11, 4, 6$ and $12$ , there is only one tower that, in $A$ , $8$ and $3$ , $3$ and $1$ , $1$ and $5$ , $5$ and $7$ are adjacent.

If $A = \{1, 2, 4, 5, 6, 8\}$ , then $B = \{3, 7, 9, 10, 11, 12\}$ . Similarly, we see that, in $A$ , $1$ and $2$ , $5$ and $6$ , $4$ and $8$ are adjacent, respectively. There are two arrangements, that is, there are two towers.

(2) If $d = 9$ , then $A = \{1, 2, a, b, c, 9\}$ , $c \le 8$ , $a + b + c = 14$ , where $(a, b, c) = (3, 5, 6)$ or $(3, 4, 7)$ , that is, $A = \{1, 2, 3, 5, 6, 9\}$ or $A = \{1, 2, 3, 4, 7, 9\}$ .

If $A = \{1, 2, 3, 5, 6, 9\}$ , then $B = \{4, 7, 8, 10, 11, 12\}$ . To obtain $4$ , $10$ and $12$ in $B$ , $1$ , $3$ , and $9$ in $A$ must be adjacent pairwise, it is impossible!

If $A = \{1, 2, 3, 4, 7, 9\}$ , then $B = \{5, 6, 8, 10, 11, 12\}$ . To obtain $6$ , $8$ and $12$ in $B$ , $2$ and $4$ , $1$ and $7$ , $9$ and $3$ must be adjacent in $A$ , respectively. There are two arrangements, that is, there are two towers.

(3) If $d = 10$ , then $A = \{1, 2, a, b, c, 10\}$ , where $c \le 9$ , $a + b + c = 13$ . Thus, $(a, b, c) = (3, 4, 6)$ , that is, $A = \{1, 2, 3, 4, 6, 10\}$ and $B = \{5, 7, 8, 9, 11, 12\}$ . To obtain $8$ , $9$ , $11$ and $12$ in $B$ , $6$ and $2$ , $6$ and $3$ , $10$ and $1$ , $10$ and $2$ must be adjacent, respectively. There is only one tower.

Summing up, there are six different towers all together. ☐

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.