Maths Olympiad Prep

Library / /572 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Compute the number of permutations π\pi of the set {1,2,,10}\{1,2, \ldots, 10\} so that for all (not necessarily distinct) m,n{1,2,,10}m, n \in\{1,2, \ldots, 10\} where m+nm+n is prime, π(m)+π(n)\pi(m)+\pi(n) is prime.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Since π\pi sends pairs (m,n)(m, n) with m+nm+n prime to pairs (m,n)\left(m^{\prime}, n^{\prime}\right) with m+nm^{\prime}+n^{\prime} prime, and there are only finitely many such pairs, we conclude that if m+nm+n is composite, then so is π(m)+π(n)\pi(m)+\pi(n). Also note that 2π(1)=π(1)+π(1)2 \pi(1)=\pi(1)+\pi(1) is prime because 2=1+12=1+1 is prime. Thus, π(1)=1\pi(1)=1. Now, since 1+2,1+4,1+61+2,1+4,1+6, and 1+101+10 are all prime, we know that π(2),π(4),π(6)\pi(2), \pi(4), \pi(6), and π(10)\pi(10) are all even. Additionally, since 8+2,8+6,8+68+2,8+6,8+6, and 8+108+10 are all composite, it is not hard to see that π(8)\pi(8) must also be even. Therefore π\pi preserves parity. Now, draw a bipartite graph between the odd and even numbers where we have an edge between aa and bb if and only if a+ba+b composite. We now only need to compute automorphisms of this graph that fix 1. Note that the edges are precisely 1872,3691-8-7-2,3-6-9, and 45104-5-10. Since 1 is a fixed point of π\pi, we know that π\pi fixes 1,8,71,8,7, and 2. Additionally, π(6)=6\pi(6)=6 and π(5)=5\pi(5)=5. We can swap 3 and 9, as well as 4 and 10. Thus, there are 22=42 \cdot 2=4 possible permutations.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.