Maths Olympiad Prep

Library / /1031 of 1394

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
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.

Solution

Solution:
Since π\pi sends pairs (m,n)(m, n) with m+nm+n prime to pairs (m,n)(m', n') with m+nm'+n' 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 11. Note that the edges are precisely 1872,3691-8-7-2, 3-6-9, and 45104-5-10. Since 11 is a fixed point of π\pi, we know that π\pi fixes 1,8,71,8,7, and 22. Additionally, π(6)=6\pi(6)=6 and π(5)=5\pi(5)=5. We can swap 33 and 99, as well as 44 and 1010. 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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.