HMMT 二月 2010 · 冲刺赛 · 第 14 题

HMMT February 2010 — Guts Round — Problem 14

[ 8 ] In how many ways can you fill a 3 × 3 table with the numbers 1 through 9 (each used once) such that all pairs of adjacent numbers (sharing one side) are relatively prime?

解析

[ 8 ] In how many ways can you fill a 3 × 3 table with the numbers 1 through 9 (each used once) such that all pairs of adjacent numbers (sharing one side) are relatively prime? Answer: 2016 The numbers can be separated into four sets. Numbers in the set A = { 1 , 5 , 7 } can be placed next to anything. The next two sets are B = { 2 , 4 , 8 } and C = { 3 , 9 } . The number 6, which forms the final set D , can only be placed next to elements of A . The elements of each group can be interchanged without violating the condition, so without loss of generality, we can pretend we have three 1’s, three 2’s, two 3’s, and one 6, as long as we multiply our answer by 3!3!2! at the end. The available arrangements are, grouped by the position of the 6, are: When 6 is in contact with three numbers: 1 2 3 6 1 2 1 2 3 When 6 is in contact with two numbers: Guts Round 6 1 2 6 1 2 1 2 3 1 1 3 2 3 1 2 3 2 The next two can be flipped diagonally to create different arrangements: 6 1 2 6 1 2 1 2 3 1 2 3 1 3 2 3 1 2 Those seven arrangements can be rotated 90, 180, and 270 degrees about the center to generate a total of 28 arrangements. 28 · 3!3!2! = 2016.