Problem 26 · 2012 Math Kangaroo
Stretch
Counting & Probability
casework
How many permutations (x1, x2, x3, x4) of the set {1, 2, 3, 4} have the property that the number x1x2 + x2x3 + x3x4 + x4x1 is divisible by 3?
Show answer
Answer: D — 16
Show hints
Hint 1 of 2
The cyclic sum \(x_1x_2 + x_2x_3 + x_3x_4 + x_4x_1\) groups into a single product.
Still stuck? Show hint 2 →
Hint 2 of 2
It equals \((x_1+x_3)(x_2+x_4)\); check which way of splitting \(\{1,2,3,4\}\) into the two diagonals makes a multiple of 3.
Show solution
Approach: factor the cyclic sum, then count arrangements
- Group terms: \(x_1x_2 + x_2x_3 + x_3x_4 + x_4x_1 = (x_1+x_3)(x_2+x_4)\).
- The two diagonals \(\{x_1,x_3\}\) and \(\{x_2,x_4\}\) split \(\{1,2,3,4\}\) into a pair-sum product: \(5\cdot5\), \(4\cdot6\), or \(3\cdot7\) — only \(4\cdot6\) and \(3\cdot7\) are divisible by 3.
- Each good split fills the two diagonals in \(2\times2\) orders, and either pair can be the odd-positioned one, giving \(8\) permutations per split.
- Two good splits give \(2\times8 = 16\) permutations, choice D.
Mark:
· log in to save