HMMT 二月 2022 · 冲刺赛 · 第 18 题

HMMT February 2022 — Guts Round — Problem 18

[11] Compute the number of permutations π of the set { 1 , 2 , . . . , 10 } so that for all (not necessarily distinct) m, n ∈ { 1 , 2 , . . . , 10 } where m + n is prime, π ( m ) + π ( n ) is prime.

解析

[11] Compute the number of permutations π of the set { 1 , 2 , . . . , 10 } so that for all (not necessarily distinct) m, n ∈ { 1 , 2 , . . . , 10 } where m + n is prime, π ( m ) + π ( n ) is prime. Proposed by: Sheldon Kieren Tan Answer: 4 ′ ′ ′ ′ Solution: Since π sends pairs ( m, n ) with m + n prime to pairs ( m , n ) with m + n prime, and there are only finitely many such pairs, we conclude that if m + n is composite, then so is π ( m ) + π ( n ). Also note that 2 π (1) = π (1) + π (1) is prime because 2 = 1 + 1 is prime. Thus, π (1) = 1. Now, since 1 + 2 , 1 + 4 , 1 + 6 , and 1 + 10 are all prime, we know that π (2) , π (4) , π (6) , and π (10) are all even. Additionally, since 8 + 2 , 8 + 6 , 8 + 6 , and 8 + 10 are all composite, it is not hard to see that π (8) must also be even. Therefore π preserves parity. Now, draw a bipartite graph between the odd and even numbers where we have an edge between a and b if and only if a + b composite. We now only need to compute automorphisms of this graph that fix 1. Note that the edges are precisely 1 − 8 − 7 − 2, 3 − 6 − 9, and 4 − 5 − 10. Since 1 is a fixed point of π , we know that π fixes 1 , 8 , 7 , and 2. Additionally, π (6) = 6 and π (5) = 5. We can swap 3 and 9, as well as 4 and 10. Thus, there are 2 · 2 = 4 possible permutations.