Difference between revisions of "2025 AIME I Problems/Problem 13"

Revision as of 21:26, 13 February 2025

Problem

Alex divides a disk into four quadrants with two perpendicular diameters intersecting at the center of the disk. He draws $25$ more lines segments through the disk, drawing each segment by selecting two points at random on the perimeter of the disk in different quadrants and connecting these two points. Find the expected number of regions into which these $27$ line segments divide the disk.

Solution

Consider a blank circle. Drawing one line yields one more region. In fact, if we consider any arrangement of lines in a circle, drawing one line yields one more region. Since Alex draws $25$ more lines, these form $25$ new regions solely by existing. We add these to the original $4$ formed by the perpendicular diameters. We also note that each time a new line intersects an existing line, this adds one more region to the count. All that is left to consider now is the expected number of intersections.

First, we consider how many intersections are expected to occur between the quadrant lines and the new $25$ lines. Consider only one of the new lines. Let one of its endpoints lie in one of the four quadrants. There is a $\frac{2}{3}$ chance that the other endpoint lies on one of the adjacent quadrants, where only one of the diameters would be crossed. There is a $\frac{1}{3}$ chance that the other endpoint lies on the opposite quadrant, where both of the diameters would be crossed. Thus the expected number of crossings of the diameters for one line is $1\cdot\frac{2}{3}+2\cdot\frac{1}{3}=\frac{4}{3}$ . There are $25$ lines, so $25\cdot\frac{4}{3}=\frac{100}{3}$ crossings.

Next, we consider interactions between non-diameter lines. Assume we place one line arbitrarily onto the circle (the blue line). As before, there is a $\frac{2}{3}$ chance that the line's endpoints lie on adjacent quadrants and a $\frac{1}{3}$ chance that the line's endpoints lie on opposite quadrants. We first consider the adjacent quadrant case.

$[asy] pair A,B,C,D,E,F,O; A=(1,0);B=(0,1);C=(-1,0);D=(0,-1);E=(0.5,0.86602540);F=(0.707106,-0.707106);O=(0,0); draw(A--C);draw(B--D);draw(circle((0,0),1));draw(E--F,blue);dot(E,blue);dot(F,blue); label("$x$",(1,0.5));label("$m-x$",(0.3,1.1));label("$y$",(1.1,-0.4));label("$m-y$",(0.4,-1.1)); [/asy]$

Assume WLOG that the endpoints of the blue line lie in quadrants one and four (diagram above). Let the arc lengths from the end of the $x$ -axis to the endpoints be $x$ and $y$ , and let the arc length of one quadrant be $m$ . We know that $x$ and $y$ 's angles range between $0$ and $90$ degrees and the probability is evenly distributed, so the expected value of $x$ and $y$ 's central angles are $45$ degrees, or $\frac{1}{2}m$ . We need only consider the expected values, so let $x=E(x)=\frac{1}{2}m$ and $y=E(y)=\frac{1}{2}m$ .

For our new line, we first place one endpoint in some region and consider probabilities. We first consider the case where the first endpoint is placed in the $x$ arc. This occurs with a probability of $\frac{x}{4m}$ . Then the sum of the arcs where the new line would cross the blue line is $(m-y)+m+m=3m-y$ (remember that the new line cannot fall in one quadrant only), so the overall probability is $\frac{x(3m-y)}{4m\cdot3m}=\frac{x(3m-y)}{12m^2}$ . Since we only need expected values, we can substitute in $x=y=\frac{1}{2}m$ to find a probability of $\frac{5}{48}$ . Notice that the first endpoint falling in the $y$ arc case is the same since $x=y$ , so the probability doubles to $\frac{5}{24}$ . Finally, we could have flipped the new line (placing the first endpoint where the second currently is and vice versa), so we double again for an overall probability of $\frac{5}{12}$ . This only occurs $\frac{2}{3}$ of the time, so the contribution is $\frac{5}{12}\cdot\frac{2}{3}=\frac{5}{18}$ .

Next, we consider the case where the blue line's endpoints fall in two opposite quadrants.

$[asy] pair A,B,C,D,E,F,O; A=(1,0);B=(0,1);C=(-1,0);D=(0,-1);E=(0.5,0.86602540);F=(-0.707106,-0.707106);O=(0,0); draw(A--C);draw(B--D);draw(circle((0,0),1));draw(E--F,blue);dot(E,blue);dot(F,blue); label("$x$",(0.3,1.1));label("$m-y$",(-0.4,-1.1));label("$y$",(-1.05,-0.25));label("$m-x$",(1,0.6)); [/asy]$

(am completing right now)

Solution 1

First, we calculate the probability that two segments intersect each other. Let the quadrants be numbered $1$ through $4$ in the normal labeling of quadrants, let the two perpendicular diameters be labeled the $x$ -axis and $y$ -axis, and let the two segments be $A$ and $B.$ $\[\]$ $\textbf{Case 1:}$ Segment $A$ has endpoints in two opposite quadrants. This happens with probability $\frac{1}{3}.$ WLOG let the two quadrants be $1$ and $3.$ We do cases in which quadrants segment $B$ lies in.

Quadrants $1$ and $2,$ $2$ and $3,$ $3$ and $4,$ and $4$ and $1$ : These share one quadrant with $A,$ and it is clear that for any of them to intersect $A,$ the endpoint that shares a quadrant with an endpoint of $A$ on a certain side of that endpoint of $A$ For example, if it was quadrants $1$ and $2,$ then the point in quadrant $1$ must be closer to the $x$ -axis than the endpoint of $A$ in quadrant $1.$ This happens with probability $\frac{1}{2}.$ Additionally, segment $B$ has a $\frac{1}{6}$ to have endpoints in any set of two quadrants, so this case contributes to the total probability

$\dfrac{1}{3}\left(\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}\right)=\dfrac{1}{9}$

Quadrants $2$ and $4.$ This always intersects segment $A,$ so this case contributes to the total probability

$\dfrac{1}{3}\cdot\dfrac{1}{6}=\dfrac{1}{18}$

Quadrants $1$ and $3.$ We will first choose the endpoints, and then choose the segments from the endpoints. Let the endpoints of the segments in quadrant $1$ be $R_1$ and $R_2,$ and the endpoints of the segments in quadrant $3$ be $S_1$ and $S_2$ such that $R_1,R_2,S_1,$ and $S_2$ are in clockwise order. Note that the probability that $A$ and $B$ intersect is the probability that $A_1$ is paired with $B_1,$ which is $\dfrac{1}{2}.$ Thus, this case contributes to the total probability

$\dfrac{1}{3}\cdot\dfrac{1}{6}\cdot\dfrac{1}{2}=\dfrac{1}{36}.$ $\[\]$ $\textbf{Case 2:}$ Segment $A$ has endpoints in two adjacent quadrants. This happens with probability $\frac{2}{3}.$ WLOG let the two quadrants be $1$ and $2.$ We do cases in which quadrants segment $B$ lies in.

Quadrants $1$ and $2,$ $3$ and $4,$ $1$ and $3,$ and $2$ and $4.$ This is similar to our first case above, so this contributes to the total probability

$\dfrac{2}{3}\left(\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}\right)=\dfrac{2}{9}$

Quadrants $2$ and $3.$ This cannot intersect segment $A.$
Quadrants $1$ and $4,$ Similar to our third case above, this intersects segment $A$ with probability $\frac{1}{2},$ so this case contributes to the total probability

$\dfrac{2}{3}\cdot\dfrac{1}{6}\cdot\dfrac{1}{2}=\dfrac{1}{18}.$ Thus, the probability that two segments intersect is $\dfrac{1}{9}+\dfrac{1}{18}+\dfrac{1}{36}+\dfrac{2}{9}+\dfrac{1}{18}=\dfrac{17}{36}.$ Next, we will compute the expected number of intersections of a segment with the axes. WLOG let a segment have an endpoint in quadrant $1.$ Then, it will intersect each axis with probability $\dfrac{2}{3}$ because two out of the three remaining quadrants let it intersect a specific axis, so the expected number of axes a segment intersects is $\frac{4}{3}.$ $\[\]$ So, why do intersections matter, because when adding a segment, it will pass through a number of regions, and for each region it passes through, it will split that region into two and add another region. The segment starts in a region, and for each intersection, it will enter another region, so the number of regions a segment passes through is $1$ more than the number of intersections with the axes and other segments. Thus, we have that by linearity of expectation the expected number of new regions created by adding a segment is $\dfrac{17}{36}\cdot(\text{number of segments already added})+\dfrac{4}{3}+1,$ so the number of new regions added in total by $25$ segments again by linearity of expectation is $\sum_{k=0}^{24}\left(\dfrac{17}{36}k+\dfrac{7}{3}\right)=\dfrac{17}{36}\cdot \dfrac{24\cdot 25}{2}+\dfrac{25\cdot 7}{3}$ which simplifies to $200$ as the expected number of new regions added by the $25$ segments. At the beginning the axis create $4$ regions, so our answer is $200+4=\boxed{204}.$

~BS2012

@@ Line 39: / Line 39: @@
 <cmath></cmath>
 <math>\textbf{Case 1:}</math> Segment <math>A</math> has endpoints in two opposite quadrants. This happens with probability <math>\frac{1}{3}.</math> WLOG let the two quadrants be <math>1</math> and <math>3.</math> We do cases in which quadrants segment <math>B</math> lies in.
-* Quadrants <math>1</math> and <math>2,</math> <math>2</math> and <math>3,</math> <math>3</math> and <math>4,</math> and <math>4</math> and <math>1</math>: These share one quadrant with <math>A,</math> and it is clear that for any of them to intersect <math>A,</math> it must be on a certain side of <math>A.</math> For example, if it was quadrants <math>1</math> and <math>2,</math> then the point in quadrant <math>1</math> must be closer to the <math>x</math>-axis than the endpoint of <math>A</math> in quadrant <math>1.</math> This happens with probability <math>\frac{1}{2}.</math> Additionally, segment <math>B</math> has a <math>\frac{1}{6}</math> to have endpoints in any set of two quadrants, so this case contributes to the total probability
+* Quadrants <math>1</math> and <math>2,</math> <math>2</math> and <math>3,</math> <math>3</math> and <math>4,</math> and <math>4</math> and <math>1</math>: These share one quadrant with <math>A,</math> and it is clear that for any of them to intersect <math>A,</math> the endpoint that shares a quadrant with an endpoint of <math>A</math> on a certain side of that endpoint of <math>A</math> For example, if it was quadrants <math>1</math> and <math>2,</math> then the point in quadrant <math>1</math> must be closer to the <math>x</math>-axis than the endpoint of <math>A</math> in quadrant <math>1.</math> This happens with probability <math>\frac{1}{2}.</math> Additionally, segment <math>B</math> has a <math>\frac{1}{6}</math> to have endpoints in any set of two quadrants, so this case contributes to the total probability
 <cmath>\dfrac{1}{3}\left(\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}+\dfrac{1}{6}\cdot\dfrac{1}{2}\right)=\dfrac{1}{9}</cmath>
 * Quadrants <math>2</math> and <math>4.</math> This always intersects segment <math>A,</math> so this case contributes to the total probability

2025 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 12	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2025 AIME I Problems/Problem 13"

Revision as of 21:26, 13 February 2025

Contents

Problem

Solution

Solution 1

See also