Thisoldmage

Number 1 There are 7 different characters that can be picked, with 0 being the only number that can be repeated twice.

If $0$ appears 0 or 1 times amongst the sequence, there are ${\frac {7!}{(7-5)!}}=2520$ sequences possible.
If $0$ appears twice in the sequence, there are ${5 \choose 2}=10$ places to place the $0$ s. There are ${\frac {6!}{(6-3)!}}=120$ ways to place the remaining three characters. Totally, that gives us $10\cdot 120=1200$ .

Thus, $\displaystyle N=2520+1200=3720$ , and ${\frac {N}{10}}=372$ .

Number 2 Denote $x={\frac {b}{a}}$ and $y={\frac {c}{a}}$ . The last condition reduces to $\displaystyle a(1+x+y)=100$ . Therefore, $\displaystyle 1+x+y$ is equal to one of the 9 factors of $\displaystyle 100=2^{2}5^{2}$ .

Subtracting the one, we see that $\displaystyle x+y=\{0,1,3,4,9,19,24,49,99\}$ . There are exactly $\displaystyle n-1$ ways to find pairs of $\displaystyle (x,y)$ if $\displaystyle x+y=n$ . Thus, there are $\displaystyle 0+0+2+3+8+18+23+48+98=200$ solutions of $(a,b,c)$ .

Alternatively, note that the sum of the divisors of $100$ is $(1+2+2^{2})(1+5+5^{2})\displaystyle$ (notice that after distributing, every divisor is accounted for). This evaluates to $7\cdot 31=217$ . Subtract $9\cdot 2$ for reasons noted above to get $199$ . Finally, this changes $\displaystyle 1\Rightarrow -1$ , so we have to add one to account for that. We get $200$ .

Number 3

Denote $x={\frac {b}{a}}$ and $y={\frac {c}{a}}$ . The last condition reduces to $\displaystyle a(1+x+y)=100$ . Therefore, $\displaystyle 1+x+y$ is equal to one of the 9 factors of $\displaystyle 100=2^{2}5^{2}$ .

Subtracting the one, we see that $\displaystyle x+y=\{0,1,3,4,9,19,24,49,99\}$ . There are exactly $\displaystyle n-1$ ways to find pairs of $\displaystyle (x,y)$ if $\displaystyle x+y=n$ . Thus, there are $\displaystyle 0+0+2+3+8+18+23+48+98=200$ solutions of $(a,b,c)$ .

Alternatively, note that the sum of the divisors of $100$ is $(1+2+2^{2})(1+5+5^{2})\displaystyle$ (notice that after distributing, every divisor is accounted for). This evaluates to $7\cdot 31=217$ . Subtract $9\cdot 2$ for reasons noted above to get $199$ . Finally, this changes $\displaystyle 1\Rightarrow -1$ , so we have to add one to account for that. We get $200$ . Extend ${\overline {AE}},{\overline {DF}}$ and ${\overline {BE}},{\overline {CF}}$ to their points of intersection. Since $\triangle ABE\cong \triangle CDF$ and are both $5-12-13$ right triangles, we can come to the conclusion that the two new triangles are also congruent to these two (use ASA, as we know all the sides are $13$ and the angles are mostly complementary). Thus, we create a square with sides $5+12=17$ .

File:2007 AIME II-3b.PNG

${\overline {EF}}$ is the diagonal of the square, with length $17{\sqrt {2}}$ ; the answer is $EF^{2}=(17{\sqrt {2}})^{2}=578$ .

A slightly more analytic/brute-force approach:

File:AIME II prob10 bruteforce.PNG

Drop perpendiculars from $E$ and $F$ to $I$ and $J$ , respectively; construct right triangle $EKF$ with right angle at K and $EK||BC$ . Since $2[CDF]=DF*CF=CD*JF$ , we have $JF=5\times 12/13={\frac {60}{13}}$ . Similarly, $EI={\frac {60}{13}}$ . Since $\triangle DJF\sim \triangle DFC$ , we have $DJ={\frac {5JF}{12}}={\frac {25}{13}}$ .

Now, we see that $FK=DC-(DJ+IB)=DC-2DJ=13-{\frac {50}{13}}={\frac {119}{13}}$ . Also, $EK=BC+(JF+IE)=BC+2JF=13+{\frac {120}{13}}={\frac {289}{13}}$ . By the Pythagorean Theorem, we have $EF={\sqrt {\left({\frac {289}{13}}\right)^{2}+\left({\frac {119}{13}}\right)^{2}}}={\frac {\sqrt {(17^{2})(17^{2}+7^{2})}}{13}}$ $={\frac {17{\sqrt {338}}}{13}}={\frac {17(13{\sqrt {2}})}{13}}=17{\sqrt {2}}$ . Therefore, $EF^{2}=(17{\sqrt {2}})^{2}=578$ .

Number 4 Suppose that it takes $x$ hours for one worker to create one widget, and $y$ hours for one worker to create one whoosit.

Therefore, we can write that (note that two hours is similar to having twice the number of workers, and so on):

$100=300x+200y$

$2(60)=240x+300y$

$3(50)=150x+my$

Solve the system of equations with the first two equations to find that $(x,y)=\left({\frac {1}{7}},{\frac {2}{7}}\right)$ . Substitute this into the third equation to find that $1050=150+2m$ , so $m=450$ .

Number 5

Solution 1

There are $223\cdot 9=2007$ squares in total formed by the rectangle with edges on the x and y axes and with vertices on the intercepts of the equation, since the intercepts of the lines are $(223,0),\ (0,9)$ .

Count the number of squares that the diagonal of the rectangle passes through. Since the two diagonals of a rectangle are congruent, we can consider instead the diagonal $y={\frac {223}{9}}x$ . This passes through 8 horizontal lines ( $\displaystyle y=1\ldots 8$ ) and 222 vertical lines ( $\displaystyle x=1\ldots 222$ ). At every time we cross a line, we enter a new square. Since 9 and 223 are relatively prime, we don’t have to worry about crossing an intersection of a horizontal and vertical line at one time. We must also account for the first square. This means that it passes through $222+8+1=231$ squares.

The number of non-diagonal squares is $2007-231=1776$ . Divide this in 2 to get the number of squares in one of the triangles, with the answer being ${\frac {1776}{2}}=888$ .

Solution 2

Count the number of each squares in each row of the triangle. The intercepts of the line are $(223,0),\ (0,9)$ .

In the top row, there clearly are no squares that can be formed. In the second row, we see that the line $y=8$ gives a $x$ value of ${\frac {2007-8(223)}{9}}=24{\frac {7}{9}}$ , which means that $\lfloor 24{\frac {7}{9}}\rfloor =24$ unit squares can fit in that row. In general, there are

\displaystyle \sum _{i=0}^{8}\lfloor {\frac {223i}{9}}\rfloor

triangles. Since $\lfloor {\frac {223}{9}}\rfloor =24$ , we see that there are more than $24(0+1+\ldots +8)=24({\frac {8\times 9}{2}})=864$ triangles. Now, count the fractional parts. $\lfloor {\frac {0}{9}}\rfloor =0,\lfloor {\frac {7}{9}}\rfloor =0,\lfloor {\frac {14}{9}}\rfloor =1,$ $\lfloor {\frac {21}{9}}\rfloor =2,\lfloor {\frac {28}{9}}\rfloor =3,\lfloor {\frac {35}{9}}\rfloor =3,$ $\lfloor {\frac {42}{9}}\rfloor =4,\lfloor {\frac {49}{9}}\rfloor =5,\lfloor {\frac {56}{9}}\rfloor =6$ . Adding them up, we get $864+1+2+3+3+4+5+6=888\displaystyle$ .

Solution 3

From Pick's Theorem, ${\frac {2007}{2}}={\frac {233}{2}}-{\frac {2}{2}}+{\frac {2I}{2}}$ . In other words, $2I=1776$ and I is $\displaystyle 888$ .

Number 6

Let's set up a table of values. Notice that 0 and 9 both cannot appear as any of $a_{1},\ a_{2},\ a_{3}$ because of the given conditions. A clear pattern emerges.

For example, for $3$ in the second column, we note that $3$ is less than $4,6,8$ , but greater than $1$ , so there are four possible places to align $3$ as the second digit.

Number	1st	2nd	3rd	4th
0	0	0	0	64
1	1	4	16	64
2	1	4	16	64
3	1	4	16	64
4	1	4	16	64
5	1	4	16	64
6	1	4	16	64
7	1	4	16	64
8	1	4	16	64
9	0	0	0	64

For any number from 1-8, there are exactly 4 numbers from 1-8 that are odd and less than the number or that are even and greater than the number (the same will happen for 0 and 9 in the last column). Thus, the answer is $\displaystyle 4^{k-1}*10=4^{3}10=640$ .

Number 7

For $x=1$ , we see that ${\sqrt[{3}]{1}}\ldots {\sqrt[{3}]{7}}$ all work, giving 7 integers. For $x=2$ , we see that in ${\sqrt[{3}]{8}}\ldots {\sqrt[{3}]{26}}$ , all of the even numbers work, giving 10 integers. For $x=3$ , we get 13, and so on. We can predict that at $x=22$ we get 70.

To prove this, note that all of the numbers from ${\sqrt[{3}]{x^{3}}}\ldots {\sqrt[{3}]{(x+1)^{3}-1}}$ divisible by $x$ work. Thus, ${\frac {(x+1)^{3}-1-x^{3}}{x}}+1={\frac {3x^{2}+3x+1-1}{x}}+1=3x+4$ (the one to be inclusive) integers will fit the conditions. $3k+4=70\Longrightarrow k=22$ .

The maximum value of $\displaystyle n_{i}=(x+1)^{3}-1$ . Therefore, the solution is ${\frac {23^{3}-1}{22}}={\frac {(23-1)(23^{2}+23+1)}{22}}=529+23+1=553$ .

Number 8

Solution 1

Denote the number of horizontal lines as $x$ , and the number of vertical lines as $y$ . The number of basic rectangles is $(x-1)(y-1)$ . $5x+4y=2007\Longrightarrow y={\frac {2007-5x}{4}}$ . Substituting, we find that $(x-1)\left(-{\frac {5}{4}}x+{\frac {2003}{4}}\right)$ .

FOIL this to get a quadratic, $-{\frac {5}{4}}x^{2}+502x-{\frac {2003}{4}}$ . Use ${\frac {-b}{2a}}$ to find the maximum possible value of the quadratic: $x={\frac {-502}{-2\cdot {\frac {5}{4}}}}={\frac {1004}{5}}\approx 201$ . However, this gives a non-integral answer for $y$ . The closest two values that work are $(199,253)$ and $(203,248)$ .

We see that $252\cdot 198=49896>202\cdot 247=49894$ . The solution is $896$ .

Solution 2

We realize that drawing $x$ vertical lines and $y$ horizontal lines, the number of basic rectangles we have is $(x-1)(y-1)$ . The easiest possible case to see is $223$ vertical and $223$ horizontal lines, as $(4+5)223=2007$ . Now, for every 4 vertical lines you take away, you can add 5 horizontal lines, so you basically have the equation $(222-4x)(222+5x)$ maximize.

Expanded, this gives $-20x^{2}+222x+222^{2}$ . From $-{\frac {b}{2a}}$ you get that the vertex is at $x={\frac {111}{20}}$ . This is not an integer though, so you see that when $x=5$ , you have $-20*25+222*5+222^{2}$ and that when x=6, you have $-20*36+222*6+222^{2}$ . $222>20*11$ , so the maximum integral value for x occurs when $x=6$ . Now you just evaluate $-20*36+222*6+222^{2}\mod 1000$ which is ${896}$ .

Number 9 Several Pythagorean triples exist amongst the numbers given. $BE=DF={\sqrt {63^{2}+84^{2}}}=21{\sqrt {3^{2}+4^{2}}}=105$ . Also, the length of $EF={\sqrt {63^{2}+(448-2\cdot 84)^{2}}}=7{\sqrt {9^{2}+40^{2}}}=287$ .

Use the Two Tangent theorem on $\triangle BEF$ . Since both circles are inscribed in congruent triangles, they are congruent; therefore, $EP=FQ={\frac {287-PQ}{2}}$ . By the Two Tangent theorem, note that $EP=EX={\frac {287-PQ}{2}}$ , making $\displaystyle BX=105-EX=105-\left[{\frac {287-PQ}{2}}\right]$ . Also, $\displaystyle BX=BY$ . $FY=364-BY=364-\left[105-\left[{\frac {287-PQ}{2}}\right]\right]$ .

Finally, $FP=FY=364-\left[105-\left[{\frac {287-PQ}{2}}\right]\right]={\frac {805-PQ}{2}}$ . Also, $FP=FQ+PQ={\frac {287-PQ}{2}}+PQ$ . Equating, we see that ${\frac {805-PQ}{2}}={\frac {287+PQ}{2}}$ , so $\displaystyle PQ=259$ .

Solution 2

By the Two Tangent theorem, we have that $\displaystyle FY=PQ+QF$ . Solve for $\displaystyle PQ=FY-QF$ . Also, $\displaystyle QF=EP=EX$ , so $\displaystyle PQ=FY-EX$ . Since $\displaystyle BX=BY$ , this can become $\displaystyle PQ=FY-EX+(BY-BX)$ $=\left(FY+BY\right)-\left(EX+EY\right)=FB-EB$ . Substituting in their values, the answer is $364-105=259$ .

Number 10

$B$ $B$ has 6 elements:
- Probability: ${\frac {1}{2^{6}}}={\frac {1}{64}}$
- $A$ must have either 0 or 6 elements, probability: ${\frac {2}{2^{6}}}={\frac {2}{64}}$ .
$B$ $B$ has 5 elements:
- Probability: ${6 \choose 5}/64={\frac {6}{64}}$
- $A$ must have either 0, 6, or 1, 5 elements. The total probability is ${\frac {2}{64}}+{\frac {2}{64}}={\frac {4}{64}}$ .
$B$ $B$ has 4 elements:
- Probability: ${6 \choose 4}/64={\frac {15}{64}}$
- $A$ must have either 0, 6; 1, 5; or 2,4 elements. If there are 1 or 5 elements, the set which contains 5 elements must have four emcompassing $B$ and a fifth element out of the remaining $2$ numbers. The total probability is ${\frac {2}{64}}\left({2 \choose 0}+{2 \choose 1}+{2 \choose 2}\right)={\frac {2}{64}}+{\frac {4}{64}}+{\frac {2}{64}}={\frac {4}{64}}$ .

We could just continue our casework. In general, the probability of picking B with $n$ elements is ${\frac {6 \choose n}{64}}$ . Since the sum of the elements in the $k$ th row of Pascal's Triangle is $2^{k}$ , the probability of obtaining $A$ or $S-A$ which encompasses $B$ is ${\frac {2^{7-n}}{64}}$ . In addition, we must count for when $B$ is the empty set (probability: ${\frac {1}{64}}$ ), of which all sets of $A$ will work (probability: $1$ ).

Thus, the solution we are looking for is $\left(\displaystyle \sum _{i=1}^{6}{\frac {6 \choose i}{64}}\cdot {\frac {2^{7-i}}{64}}\right)+{\frac {1}{64}}\cdot {\frac {64}{64}}$ $={\frac {(1)(64)+(6)(64)+(15)(32)+(20)(16)+(15)(8)+(6)(4)+(1)(2)}{(64)(64)}}$ $={\frac {1394}{2^{12}}}$ $={\frac {697}{2^{11}}}$ .

The answer is $\displaystyle 697+2+11=710$ .

Number 11

File:2007 AIME II-11.png

If it weren’t for the small tube, the larger tube would travel $\displaystyle 144\pi$ . Consider the distance from which the larger tube first contacts the smaller tube, until when it completely loses contact with the smaller tube.

Drawing the radii as shown in the diagram, notice that the hypotenuse of the right triangle in the diagram has a length of $72+24=96$ . The horizontal line divides the radius of the larger circle into $72-24=48$ on the top half, which indicates that the right triangle has leg of 48 and hypotenuse of 96, a $30-60-90\triangle$ .

Find the length of the purple arc in the diagram (the distance the tube rolled, but not the horizontal distance). The sixty degree central angle indicates to take ${\frac {60}{360}}={\frac {1}{6}}$ of the circumference of the larger circle (twice), while the $180-2(30)=120^{\circ }$ central angle in the smaller circle indicates to take ${\frac {120}{360}}={\frac {1}{3}}$ of the circumference. This adds up to $2\cdot {\frac {1}{6}}144\pi +{\frac {1}{3}}48\pi =64\pi$ .

The actual horizontal distance it takes can be found by using the $30-60-90\triangle$ s. The missing leg is equal in length to $48{\sqrt {3}}$ . Thus, the total horizontal distance covered is $96{\sqrt {3}}$ .

Thus, we get $144\pi -64\pi +96{\sqrt {3}}=80\pi +96{\sqrt {3}}$ , and our answer is $179$ .

Number 12

Suppose that $\displaystyle x_{0}=a$ , and that the common ratio between the terms is $r$ .

The first conditions tells us that $\displaystyle \log _{3}a+\log _{3}ar\ldots \log _{3}ar^{7}=308$ . Using the rules of logarithms, we can simplify that to $\displaystyle \log _{3}a^{8}r^{1+2+\ldots +7}=308$ . Thus, $\displaystyle a^{8}r^{28}=3^{308}$ . Since all of the terms of the geometric sequence are integral powers of $3$ , we know that both $a$ and $r$ must be powers of 3. Denote $\displaystyle 3^{x}=a$ and $\displaystyle 3^{y}=r$ . We find that $8x+28y=308$ . The possible positive integral pairs of $(x,y)$ are $(35,1),\ (28,3),\ (21,5),\ (14,7),\ (7,9),\ (0,11)$ .

The second condition tells us that $56\leq \log _{3}(a+ar+\ldots ar^{7})\leq 57$ . Using the sum formula for a geometric series and substituting $x$ and $y$ , this simplifies to $3^{56}\leq 3^{x}{\frac {3^{8y}-1}{3^{y}-1}}\leq 3^{57}$ . The fractional part $\approx {\frac {3^{8y}}{3^{y}}}=3^{7y}$ . Thus, we need $\approx 56\leq x+7y\leq 57$ . Checking the pairs above, only $\displaystyle (21,5)$ is close.

Our solution is therefore $\log _{3}(ar^{14})=\log _{3}3^{x}+\log _{3}3^{14y}=x+14y=091\displaystyle$ .

Number 13 Label each of the bottom squares as $\displaystyle x_{0},x_{1}\ldots x_{9},x_{10}$ .

Through induction, we can find that the top square is equal to ${10 \choose 0}x_{0}+{10 \choose 1}x_{1}+{10 \choose 2}x_{2}+\ldots {10 \choose 10}x_{10}$ .

Examine the equation $\mod 3$ . All of the coefficients from $\displaystyle x_{2}\ldots x_{8}$ will be multiples of $3$ (since the numerator will have a $9$ ). Thus, the expression boils down to $x_{0}+10x_{1}+10x_{9}+x_{10}\equiv 0\mod 3$ . Reduce to find that $x_{0}+x_{1}+x_{9}+x_{10}\equiv 0\mod 3$ . Out of $x_{0},\ x_{1},\ x_{9},\ x_{10}$ , either all are equal to $0$ , or three of them are equal to $1$ . This gives ${4 \choose 0}+{4 \choose 3}=1+4=5$ possible combinations of numbers that work.

The seven terms from $\displaystyle x_{2}\ldots x_{8}$ can assume either $0$ or $1$ , giving us $2^{7}$ possibilities. The answer is therefore $5\cdot 2^{7}=640$ .

Number 14

Note:The following solution(s) are non-rigorous.

Substitute the values $x=\pm i$ . We find that $\displaystyle f(i)f(-2)=f(-i)$ , and that $\displaystyle f(-i)f(-2)=f(i)$ . This means that $f(i)f(-i)f(-2)^{2}=f(i)f(-i)\Longrightarrow f(i)f(-i)(f(-2)-1)=0$ . This suggests that $\pm i$ are roots of the polynomial, and so $\displaystyle (x-i)(x+i)=x^{2}+1$ will be a root of the polynomial.

The polynomial is likely in the form of $f(x)=(x^{2}+1)g(x)$ ; $g(x)$ appears to satisfy the same relation as $f(x)$ , so it also probably has the same roots. Thus, $f(x)=(x^{2}+1)^{n}h(x)$ is the solution. Guessing values for $h(x)$ , try $h(x)=1$ . Checking a couple of values shows that $f(x)=(x^{2}+1)^{2}$ works, and so the solution is $f(5)=676$ .

Number 15

Solution

File:2007 AIME II-15.png

Solution 1

First, apply Heron's formula to find that the area is ${\sqrt {21\cdot 8\cdot 7\cdot 6}}=84$ . Also the semiperimeter is $21$ . So the inradius is ${\frac {A}{s}}={\frac {84}{21}}=4$ .

Now consider the incenter I. Let the radius of one of the small circles be $r$ . Let the centers of the three little circles tangent to the sides of $\triangle ABC$ be $X$ , $Y$ , and $Z$ . Let the centre of the circle tangent to those three circles be P. A homothety centered at $I$ takes $XYZ$ to $ABC$ with factor ${\frac {4-r}{4}}$ . The same homothety takes $P$ to the circumcentre of $\triangle ABC$ , so ${\frac {PX}{R}}={\frac {2r}{R}}={\frac {4-r}{4}}$ , where $R$ is the circumradius of $\triangle ABC$ . The circumradius of $\triangle ABC$ can be easily computed by $R={\frac {a}{2\sin A}}$ , so doing that reveals $R={\frac {65}{8}}$ . Then ${\frac {2r}{\frac {65}{8}}}={\frac {(4-r)}{4}}\Longrightarrow {\frac {16r}{65}}={\frac {1-r}{4}}\Longrightarrow {\frac {129r}{260}}=1\Longrightarrow r={\frac {260}{129}}$ , so the answer is $389$ .

Solution 2

File:2007 AIME II-15b.gif

Consider a 13-14-15 triangle. $A=84.$ [By Heron's Formula or by 5-12-13 and 9-12-15 right triangles.]

The inradius is $r={\frac {A}{s}}={\frac {84}{21}}=4$ , where $s$ is the semiperimeter. Scale the triangle with the inradius by a linear scale factor, $u.$

The circumradius is $R={\frac {abc}{4rs}}={\frac {13\cdot 14\cdot 15}{4\cdot 4\cdot 21}}={\frac {65}{8}},$ where $a,$ $b,$ and $c$ are the side-lengths. Scale the triangle with the circumradius by a linear scale factor, $v$ .