Maths Olympiad Prep

Library / /318 of 520

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Five. (20 points) On the circumference, there are nn points A1A_{1}, A2,,AnA_{2}, \cdots, A_{n} in sequence. Now, kk points are randomly selected as vertices to form a convex kk-gon B1B2BkB_{1} B_{2} \cdots B_{k}, with the possibility of selection being the same. Try to find the probability that for each i{1,2,,k}i \in\{1,2, \cdots, k\}, between two adjacent vertices BiB_{i} and Bi+1B_{i+1} (with the convention that Bk+1=B_{k+1}= B1B_{1}), there are at least rir_{i} points from the set X={A1,A2,,An}X=\left\{A_{1}, A_{2}, \cdots, A_{n}\right\}, where r1,r2,,rkr_{1}, r_{2}, \cdots, r_{k} are a given set of positive integers.

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

Solution

Let Ai1Ai2AikA_{i_{1}} A_{i_{2}} \cdots A_{i_{k}} be a convex kk-gon that meets the conditions, and let P={Ai1,Ai2,,Aik}P=\left\{A_{i_{1}}, A_{i_{2}}, \cdots, A_{i_{k}}\right\}. Suppose there are xtx_{t} points in XX between AitA_{i_{t}} and Ait+1A_{i_{t+1}} that do not belong to P(t=1,3,,k, with Aik+1=Ai1)P \left(t=1,3, \cdots, k, \text{ with } A_{i_{k+1}}=A_{i_{1}}\right), then
x1+x2++xk=nk, x_{1}+x_{2}+\cdots+x_{k}=n-k,

where x1r1,xkrkx_{1} \geqslant r_{1}, \cdots \cdots x_{k} \geqslant r_{k}. Thus,
(x1r1+1)+(x2r2+1)++(xkrk+1)=nS(r), \begin{array}{l} \left(x_{1}-r_{1}+1\right)+\left(x_{2}-r_{2}+1\right)+\cdots+\left(x_{k}-r_{k}+1\right) \\ =n-S(r), \end{array}

where S(r)=r1+r2++rkS(r)=r_{1}+r_{2}+\cdots+r_{k}.
This way, each combination PP corresponds one-to-one with the positive integer solutions of equation (1)
(x1r1+1,x2r2+1,,xkrk+1) \left(x_{1}-r_{1}+1, x_{2}-r_{2}+1, \cdots, x_{k}-r_{k}+1\right)

The number of positive integer solutions of equation (1) is Cns(r)1k1\mathrm{C}_{n-s(r)-1}^{k-1}, so there are Cns(r)1k1\mathrm{C}_{n-s(r)-1}^{k-1} combinations PP.

Placing each combination on a circle, there are nn different arrangements (each vertex rotates once), but each convex kk-gon has kk vertices,

and each vertex is considered as B1B_{1} with the corresponding intervals (solutions of the indeterminate equation) counted once, thus, each convex kk-gon is counted kk times (for example, the triangle A2B3C4A 2 B 3 C 4, when points A,B,CA, B, C are considered as B1B_{1}, it is counted once in the interval patterns 2,3,42, 3, 4, 3,4,23, 4, 2, and 4,2,34, 2, 3). Therefore, the number of all convex kk-gons that meet the conditions is nkCnS(r)1k1\frac{n}{k} \mathrm{C}_{n-S(r)-1}^{k-1}.

Since there are Cnk\mathrm{C}_{n}^{k} ways to choose kk points from nn points on a circle, the required probability is
nCns(r)1k1kCnk=nCns(r)1k1nCn1k1=Cns(r)1k1Cn1k1, \frac{n \mathrm{C}_{n-s(r)-1}^{k-1}}{k \mathrm{C}_{n}^{k}}=\frac{n \mathrm{C}_{n-s(r)-1}^{k-1}}{n \mathrm{C}_{n-1}^{k-1}}=\frac{\mathrm{C}_{n-s(r)-1}^{k-1}}{\mathrm{C}_{n-1}^{k-1}},

where S(r)=r1+r2++rkS(r)=r_{1}+r_{2}+\cdots+r_{k}.

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