Maths Olympiad Prep

Library / /540 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

The numbers 1,2,,101,2, \ldots, 10 are randomly arranged in a circle. Let pp be the probability that for every positive integer k<10k<10, there exists an integer k>kk^{\prime}>k such that there is at most one number between kk and kk^{\prime} in the circle. If pp can be expressed as ab\frac{a}{b} for relatively prime positive integers aa and bb, compute 100a+b100 a+b.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n=10n=10 and call two numbers close if there is at most one number between them and an circular permutation focused if only nn is greater than all numbers close to it. Let AnA_{n} be the number of focused circular permutations of {1,2,,n}\{1,2, \ldots, n\}. If n5n \geq 5, then there are 2 cases: n1n-1 is either one or two positions from nn. If n1n-1 is one position from nn, it is either on its left or right. In this case, one can check a permutation is focused if and only if removing nn yields a focused permutation, so there are 2An12 A_{n-1} permutations in this case. If n1n-1 is two positions from nn, there are n2n-2 choices for kk, the element that lies between nn and n1n-1. One can show that this permutation is focused if and only if removing both nn and kk and relabeling the numbers yields a focused permutation, so there are 2(n2)An22(n-2) A_{n-2} permutations in this case. Thus, we have An=2An1+2(n2)An2A_{n}=2 A_{n-1}+2(n-2) A_{n-2}. If we let pn=An/(n1)p_{n}=A_{n} /(n-1) ! the probability that a random circular permutation is focused, then this becomes pn=2pn1+2pn2n1p_{n}=\frac{2 p_{n-1}+2 p_{n-2}}{n-1} Since p3=p4=1p_{3}=p_{4}=1, we may now use this recursion to calculate p5=1,p6=45,p7=35,p8=25,p9=14,p10=1390p_{5}=1, p_{6}=\frac{4}{5}, p_{7}=\frac{3}{5}, p_{8}=\frac{2}{5}, p_{9}=\frac{1}{4}, p_{10}=\frac{13}{90}

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.