Difference between revisions of "2011 AMC 10A Problems/Problem 25"

Revision as of 17:28, 5 August 2019

Problem 25

Let $R$ be a square region and $n\ge4$ an integer. A point $X$ in the interior of $R$ is called $n\text{-}ray$ partitional if there are $n$ rays emanating from $X$ that divide $R$ into $n$ triangles of equal area. How many points are 100-ray partitional but not 60-ray partitional?

$\text{(A)}\,1500 \qquad\text{(B)}\,1560 \qquad\text{(C)}\,2320 \qquad\text{(D)}\,2480 \qquad\text{(E)}\,2500$

Solution 1

First, notice that there must be four rays emanating from $X$ that intersect the four corners of the square region. Depending on the location of $X$ , the number of rays distributed among these four triangular sectors will vary. We start by finding the corner-most point that is $100$ -ray partitional (let this point be the bottom-left-most point). We first draw the four rays that intersect the vertices. At this point, the triangular sectors with bases as the sides of the square that the point is closest to both do not have rays dividing their areas. Therefore, their heights are equivalent since their areas are equal. The remaining $96$ rays are divided among the other two triangular sectors, each sector with $48$ rays, thus dividing these two sectors into $49$ triangles of equal areas. Let the distance from this corner point to the closest side be $a$ and the side of the square be $s$ . From this, we get the equation $\frac{a\times s}{2}=\frac{(s-a)\times s}{2}\times\frac1{49}$ . Solve for $a$ to get $a=\frac s{50}$ . Therefore, point $X$ is $\frac1{50}$ of the side length away from the two sides it is closest to. By moving $X$ $\frac s{50}$ to the right, we also move one ray from the right sector to the left sector, which determines another $100$ -ray partitional point. We can continue moving $X$ right and up to derive the set of points that are $100$ -ray partitional. In the end, we get a square grid of points each $\frac s{50}$ apart from one another. Since this grid ranges from a distance of $\frac s{50}$ from one side to $\frac{49s}{50}$ from the same side, we have a $49\times49$ grid, a total of $2401$ $100$ -ray partitional points. To find the overlap from the $60$ -ray partitional, we must find the distance from the corner-most $60$ -ray partitional point to the sides closest to it. Since the $100$ -ray partitional points form a $49\times49$ grid, each point $\frac s{50}$ apart from each other, we can deduce that the $60$ -ray partitional points form a $29\times29$ grid, each point $\frac s{30}$ apart from each other. To find the overlap points, we must find the common divisors of $30$ and $50$ which are $1, 2, 5,$ and $10$ . Therefore, the overlapping points will form grids with points $s$ , $\frac s{2}$ , $\frac s{5}$ , and $\frac s{10}$ away from each other respectively. Since the grid with points $\frac s{10}$ away from each other includes the other points, we can disregard the other grids. The total overlapping set of points is a $9\times9$ grid, which has $81$ points. Subtract $81$ from $2401$ to get $2401-81=\boxed{\textbf{(C)}\ 2320}$ .

Solution 2

We may assume that the square $R$ has coordinates $R_{1}(0,0), R_{2}(1,0), R_{3}(1,1), R_{4}(0,1)$ . Suppose that $X = (x,y)$ is $n$ -ray partitional. $[asy] defaultpen(fontsize(10)); int i; pair R1=(0,0),R2=(1,0),R3=(1,1),R4=(0,1), X=(3/7,5/7); draw(R1--R2--R3--R4--cycle); for(i=0;i<10;++i){draw(X--(i*R1+(10-i)*R2)/10,linewidth(0.1));} for(i=0;i< 8;++i){draw(X--(i*R2+( 8-i)*R3)/ 8,linewidth(0.1));} for(i=0;i< 4;++i){draw(X--(i*R3+( 4-i)*R4)/ 4,linewidth(0.1));} for(i=0;i< 6;++i){draw(X--(i*R4+( 6-i)*R1)/ 6,linewidth(0.1));} draw(X--R1);draw(X--R2);draw(X--R3);draw(X--R4); label("$R_{1}$",R1,(-1,-1)); label("$R_{2}$",R2,( 1,-1)); label("$R_{3}$",R3,( 1, 1)); label("$R_{4}$",R4,(-1, 1)); label("Example: $X = (\frac{3}{7},\frac{5}{7})$ is $28$-ray partitional.",(R1+R2)/2,(0,-10)); [/asy]$ By definition, there exist $n$ rays from $X$ which divide $R$ into $n$ triangles of equal area, and $4$ of these rays intersect the vertices of $R$ . Let $a,b,c,d$ be the number of triangles that share a side with $\overline{R_{1}R_{2}}, \overline{R_{2}R_{3}}, \overline{R_{3}R_{4}}, \overline{R_{4}R_{1}}$ , respectively. Then $a+b+c+d = n \;.$ Let the common area of the triangles be $A$ . Each of the triangles that share a side with $\overline{R_{1}R_{2}}$ have common height $y$ ; since they have the same area, they must have the same base $\frac{1}{a}$ . Hence $A = \frac{1}{2}\cdot \frac{1}{a}\cdot y$ . Similarly, $A = \frac{y}{2a} = \frac{1-x}{2b} = \frac{1-y}{2c} = \frac{x}{2d} \;.$ Substituting gives $n = \frac{y}{2A}+\frac{1-x}{2A}+\frac{1-y}{2A}+\frac{x}{2A} = \frac{1}{A}$ and $a = \frac{n}{2}y \;,\; b = \frac{n}{2}(1-x) \;,\; c = \frac{n}{2}(1-y) \;,\; d = \frac{n}{2}x \;.$ Since $x = \frac{2d}{n}$ and $y = \frac{2a}{n}$ and $a,d,n$ are integers, $x,y$ are rational. Let $p_{i},q_{i}$ be integers such that $0 < p_{i} < q_{i}$ and $x = \frac{p_{1}}{q_{1}} \quad,\quad y = \frac{p_{2}}{q_{2}} \;.$ Thus we have derived a necessary condition for $X$ to be $n$ -ray partitional: $q_{1} \text{ divides } \frac{n}{2}p_{1} \quad\text{ and }\quad q_{2} \text{ divides } \frac{n}{2}p_{2} \;.$ Conversely, if $X = (x,y)$ satisfies the above condition, then it is $n$ -ray partitional since we can define $a,b,c,d$ in terms of $n,x,y$ as above.

To count the points that are $100$ -ray partitional, it suffices to count the ordered pairs of rationals $(\frac{p_{1}}{q_{1}},\frac{p_{2}}{q_{2}})$ in the interior of $R$ such that $q_{1}$ divides $\frac{100}{2}p_{1}$ and $q_{2}$ divides $\frac{100}{2}p_{2}$ . This is just $\left\{(\frac{p_{1}}{50},\frac{p_{2}}{50}) \;:\; 0<p_{1},p_{2}<50 \right\}$ which has $49^{2}$ points.

We need to subtract the points that are $100$ -ray partitional and $60$ -ray partitional; those are the ordered pairs of rationals $(\frac{p_{1}}{q_{1}},\frac{p_{2}}{q_{2}})$ in the interior of $R$ such that $q_{1}$ divides $GCD(\frac{100}{2}p_{1},\frac{60}{2}p_{1}) = 10p_{1}$ and $q_{2}$ divides $GCD(\frac{100}{2}p_{2},\frac{60}{2}p_{2}) = 10p_{2}$ . This is just $\left\{(\frac{p_{1}}{10},\frac{p_{2}}{10}) \;:\; 0<p_{1},p_{2}<10 \right\}$ which has $9^{2}$ points.

Hence the answer is $49^{2} - 9^{2} = \boxed{2320}$ .

Solution 3

As with solution $2$ , place the square on the coordinate plane with coordinates $(0,0), (1,0),(1,1),(0,1)$ . Let the point $(a,b)$ be $n$ -ray partitional. Note that we must have four rays going to each corner of the square to have all triangles, so we gave four "big" triangles of area $\frac{a}{2}, \frac{1-a}{2}, \frac{b}{2}, \frac{1-b}{2}.$ We need to split each one into an integral number of triangles with area $\frac{1}{n}$ , so we must have $\frac{na}{2}, \frac{n(1-a)}{2}, \frac{nb}{2}, \frac{(1-b)}{2}$ be an integer. Letting $n$ equal $60$ and $100$ , we now have that we need to find all points $(a,b)$ such that $50a$ and $50b$ are integers, but $30a$ and $30b$ aren't. We will use complementary counting. I claim that that there are $(\sum_{d|n} \phi(n))-1$ fractions less than one such that for every fraction $f$ , $nf$ is an integer, where $\phi(n)$ is Euler's totient function. This is easy to see: we want to count the number of fractions with a denominator that divides $n$ but is simplified, so a numerator that is relatively prime to the denominator. However, we must exclude one since our fraction is less than $1$ . This is precisely what our sum counts. However, this sum is very well known and evaluates to $n-1$ . Thus there are $(n-1)*(n-1)$ that are $n$ -ray partitional (I believe that this is for even $n$ only but I haven't checked the odd case yet). Letting $n=100$ gives us $49^2$ points that are $100$ -ray partitional. Since we are counting the complement, we want to find all points that are both $60$ -ray partitional and $100$ -ray partitional, or counting all pairs of fractions $(a,b)$ such that $60a, 60b, 100a, 100b$ are all integers. Since the GCD of the two numbers is $10$ , it suffices to find the number of pairs of fractions such that $10a$ and $10b$ are integers, which is simply $9^2$ . Thus, our answer is simply $49^2-9^2=\boxed{2320}$ . -franchester

Solution 4

$[asy] unitsize(36); draw((0,0)--(3,0)--(3,3)--(0,3)--cycle); draw((0,0)--(1.8,0.8)); draw((3,0)--(1.8,0.8)); draw((3,3)--(1.8,0.8)); draw((0,3)--(1.8,0.8)); label("$R_1$",(-0.25,3.5),S); label("$R_2$",(3.5,3.25),W); label("$R_3$",(3.5,-0.25),W); label("$R_4$",(0,-0.25),W); label("$X$",(2,1.25),W); label("$C$",(1.5,-0.25),W); label("$a$",(1,5,3.25),W); label("$b$",(3.25,1.5),W); label("$c$",(1.5,-0.25),W); label("$d$",(-0.25,1.5),W); [/asy]$

2011 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search