2011 AIME II — Problems & Online Timed Exam

Timed

3:00:00

1.

Gary purchased a large beverage, but drank only $\frac{m}{n}$ of this beverage, where $m$ and $n$ are relatively prime positive integers. If Gary had purchased only half as much and drunk twice as much, he would have wasted only $\frac{2}{9}$ as much beverage. Find $m + n.$

Answer

Answer: 37

Concepts:linear equation ratio and proportion

Difficulty rating: 1710

Small Hint:

Let $x$ be the amount purchased and $y$ the amount drunk; the wasted amount is $x - y$

Big Hint:

The second scenario wastes $\frac{x}{2} - 2y,$ so set $\frac{x}{2} - 2y = \frac{2}{9}(x - y)$ and solve for $\frac{y}{x}$

Solution:

Say Gary purchased an amount $x$ and drank an amount $y,$ wasting $x - y.$ In the second scenario he would have purchased $\frac{x}{2}$ and drunk $2y,$ wasting $\frac{x}{2} - 2y.$ The condition is $\frac{x}{2} - 2y = \frac{2}{9}(x - y).$

Multiplying by $18$ gives $9x - 36y = 4x - 4y,$ so $5x = 32y$ and $\frac{y}{x} = \frac{5}{32}.$ Since $\gcd(5, 32) = 1,$ the answer is $5 + 32 = 37.$

2.

On square $ABCD,$ point $E$ lies on side $\overline{AD}$ and point $F$ lies on side $\overline{BC},$ so that $BE = EF = FD = 30.$ Find the area of square $ABCD.$

Answer

Answer: 810

Concepts:square (geometry)coordinate geometry Pythagorean Theorem

Difficulty rating: 1970

Small Hint:

Put $B = (0, 0),$ $C = (s, 0),$ $A = (0, s),$ $D = (s, s),$ and write $E = (a, s),$ $F = (b, 0)$

Big Hint:

$BE = FD$ forces $b = s - a,$ and then $EF = BE$ forces $a = \frac{s}{3};$ finish with $a^2 + s^2 = 900$

Solution:

Let the side length be $s,$ and place $B = (0, 0),$ $C = (s, 0),$ $A = (0, s),$ $D = (s, s).$ Write $E = (a, s)$ and $F = (b, 0).$ Then $BE^2 = a^2 + s^2,$ $FD^2 = (s - b)^2 + s^2,$ and $EF^2 = (a - b)^2 + s^2.$

From $BE = FD$ we get $a = s - b,$ so $a - b = 2a - s.$ Then $EF = BE$ gives $(2a - s)^2 = a^2,$ whose solutions are $a = \frac{s}{3}$ and $a = s$ (the latter identifies the separately named points $E$ and $F$ with corners $D$ and $B,$ making all three segments the same diagonal). So $a = \frac{s}{3}.$

Now $900 = BE^2 = \frac{s^2}{9} + s^2 = \frac{10s^2}{9},$ so the area is $s^2 = \frac{9}{10} \cdot 900 = 810.$

3.

The degree measures of the angles of a convex $18$ -sided polygon form an increasing arithmetic sequence with integer values. Find the degree measure of the smallest angle.

Answer

Answer: 143

Concepts:angle sum arithmetic sequence parity

Difficulty rating: 1920

Small Hint:

The interior angles of an $18$ -gon sum to $180 \cdot 16 = 2880$ degrees

Big Hint:

With smallest angle $a$ and common difference $d,$ $2a + 17d = 320,$ so $d$ is even; convexity caps the largest angle below $180$

Solution:

The interior angles of an $18$ -gon sum to $180 \cdot 16 = 2880$ degrees. If the smallest angle is $a$ and the common difference is $d,$ then $18a + 153d = 2880,$ i.e. $2a + 17d = 320.$ Since $a$ and $d$ are integers, $17d$ must be even, so $d$ is even, and $d \ge 2$ because the sequence is increasing.

Convexity requires the largest angle $a + 17d = \frac{320 + 17d}{2}$ to be less than $180,$ so $17d \lt 40$ and $d \le 2.$ Thus $d = 2$ and $a = \frac{320 - 34}{2} = 143.$

4.

In triangle $ABC,$ $AB = \frac{20}{11} AC.$ The angle bisector of angle $A$ intersects $\overline{BC}$ at point $D,$ and point $M$ is the midpoint of $\overline{AD}.$ Let $P$ be the point of intersection of $\overline{AC}$ and line $BM.$ The ratio of $CP$ to $PA$ can be expressed in the form $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Answer

Answer: 51

Concepts:mass points angle bisector theorem

Difficulty rating: 2270

Small Hint:

The angle bisector theorem gives $\frac{BD}{DC} = \frac{AB}{AC} = \frac{20}{11}$

Big Hint:

Mass points: masses $11$ at $B$ and $20$ at $C$ make $D$ carry $31;$ placing $31$ at $A$ balances the midpoint $M$

Solution:

By the angle bisector theorem, $\frac{BD}{DC} = \frac{AB}{AC} = \frac{20}{11}.$ Use mass points: place mass $11$ at $B$ and mass $20$ at $C,$ so that $D,$ which divides $\overline{BC}$ with $BD : DC = 20 : 11,$ is their balance point and carries mass $31.$ Placing mass $31$ at $A$ makes the balance point of $A$ and $D$ exactly the midpoint $M$ of $\overline{AD}.$

The center of mass of the whole system therefore lies on line $BM,$ and it also lies on the segment from $B$ to the balance point of $A$ and $C.$ That balance point is precisely where line $BM$ crosses $\overline{AC},$ namely $P,$ and it satisfies $31 \cdot PA = 20 \cdot CP.$

Hence $\frac{CP}{PA} = \frac{31}{20},$ which is in lowest terms, and $m + n = 31 + 20 = 51.$

5.

The sum of the first $2011$ terms of a geometric series is $200.$ The sum of the first $4022$ terms of the same series is $380.$ Find the sum of the first $6033$ terms of the series.

Answer

Answer: 542

Concepts:geometric sequence summation

Difficulty rating: 1970

Small Hint:

Terms $2012$ through $4022$ are $r^{2011}$ times the first $2011$ terms

Big Hint:

Each successive block of $2011$ terms is the previous block times $r^{2011};$ find that ratio from the two given sums

Solution:

Group the series into blocks of $2011$ consecutive terms. Each term of the second block is $r^{2011}$ times the corresponding term of the first block, so the block sums form a geometric sequence with ratio $r^{2011}.$ The first block sums to $200$ and the second block sums to $380 - 200 = 180,$ so $r^{2011} = \frac{180}{200} = \frac{9}{10}.$

The third block then sums to $180 \cdot \frac{9}{10} = 162,$ so the sum of the first $6033$ terms is $380 + 162 = 542.$

6.

Define an ordered quadruple of integers $(a, b, c, d)$ to be interesting if $1 \le a \lt b \lt c \lt d \le 10$ and $a + d \gt b + c.$ How many interesting ordered quadruples are there?

Answer

Answer: 80

Concepts:combinations bijection symmetry

Difficulty rating: 2390

Small Hint:

The condition $a + d \gt b + c$ is the same as $d - c \gt b - a$

Big Hint:

The map $(a, b, c, d)$ $\small \mapsto (11 - d,\, 11 - c,\, 11 - b,\, 11 - a)$ swaps $d - c$ with $b - a;$ count the quadruples with $d - c = b - a$ and use symmetry

Solution:

The condition $a + d \gt b + c$ is equivalent to $d - c \gt b - a.$ There are $\binom{10}{4} = 210$ quadruples in all, and the involution $(a, b, c, d)$ $\small \mapsto (11 - d,\, 11 - c,\, 11 - b,\, 11 - a)$ exchanges the outer gaps $b - a$ and $d - c.$ So the quadruples with $d - c \gt b - a$ and those with $d - c \lt b - a$ are equinumerous, and the answer is $\frac{210 - T}{2},$ where $T$ counts quadruples with $d - c = b - a.$

If $b - a = d - c = k$ and $c - b = j,$ the quadruple is determined by $(a, j, k)$ with $a, j, k \ge 1$ and $a + 2k + j \le 10.$ For $k = 1,$ $2,$ $3,$ and $4,$ respectively, the bounds on $a + j$ are $8,$ $6,$ $4,$ and $2;$ the corresponding counts are $28,$ $15,$ $6,$ and $1,$ so $T = 50.$

Therefore the number of interesting quadruples is $\frac{210 - 50}{2} = 80.$

7.

Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves equals the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let $m$ be the maximum number of red marbles for which such an arrangement is possible, and let $N$ be the number of ways in which Ed can arrange the $m + 5$ marbles to satisfy the requirement. Find the remainder when $N$ is divided by $1000.$

Answer

Answer: 3

Concepts:arrangements with restrictions partitions and compositions stars and bars

Difficulty rating: 2710

Small Hint:

If the row consists of $k$ maximal single-color runs, the number of different-color neighbor pairs is $k - 1$

Big Hint:

Five greens allow at most $11$ runs, so at most $10$ color changes. Matching same and different pairs then forces $16$ reds; count compositions of $16$ into $6$ positive parts.

Solution:

Break the row into maximal single-color runs. If there are $k$ runs, there are exactly $k - 1$ different-color neighbor pairs. Since runs alternate colors and the five green marbles form at most $5$ runs, there are at most $6$ red runs, hence at most $11$ runs and at most $10$ different-color pairs. With $n$ red marbles there are $n + 4$ neighbor pairs in all, and the requirement says half of them are different-color pairs, so $n + 4 \le 20,$ i.e. $n \le 16.$ Thus $m = 16.$

With $16$ reds and $21$ marbles, the count of different-color pairs must be exactly $10,$ so there are exactly $11$ runs: the colors must alternate as red–green–red– $\cdots$ –red with $6$ red runs and $5$ single green marbles between them. The arrangements correspond to compositions of $16$ into $6$ positive parts, of which there are $\binom{15}{5} = 3003.$

Hence $N = 3003,$ and the remainder upon division by $1000$ is $3.$

8.

Let $z_1,$ $z_2,$ $z_3,$ $\ldots,$ $z_{12}$ be the $12$ zeroes of the polynomial $z^{12} - 2^{36}.$ For each $j,$ let $w_j$ be one of $z_j$ or $\mathrm{i}z_j.$ Then the maximum possible value of the real part of $\sum_{j=1}^{12} w_j$ can be written as $m + \sqrt{n},$ where $m$ and $n$ are positive integers. Find $m + n.$

Answer

Answer: 784

Concepts:roots of unity complex number optimization

Difficulty rating: 2560

Small Hint:

The zeroes are $8\big(\cos\frac{\pi j}{6} + \mathrm{i}\sin\frac{\pi j}{6}\big),$ and the real part of $\mathrm{i}z$ is minus the imaginary part of $z$

Big Hint:

For each $j$ independently take the larger of $8\cos\frac{\pi j}{6}$ and $-8\sin\frac{\pi j}{6}$

Solution:

The zeroes are $z_j = 8\left(\cos\frac{\pi j}{6} + \mathrm{i}\sin\frac{\pi j}{6}\right)$ for $j = 1,$ $\ldots,$ $12,$ and $\operatorname{Re}(\mathrm{i}z_j) = -\operatorname{Im}(z_j).$ Since the choices are independent, the maximum real part of the sum is $\sum_j 8\max\left(\cos\frac{\pi j}{6},\, -\sin\frac{\pi j}{6}\right).$

Comparing the two values, $-\sin\frac{\pi j}{6}$ is larger exactly for $j = 5,$ $\ldots,$ $10.$ The cosines kept, for $j = 1,$ $2,$ $3,$ $4,$ $11,$ and $12,$ sum to $\begin{aligned} &\frac{\sqrt{3}}{2} + \frac{1}{2} + 0 - \frac{1}{2} \\ &\quad {}+ \frac{\sqrt{3}}{2} + 1 = 1 + \sqrt{3}, \end{aligned}$ and the values $-\sin\frac{\pi j}{6}$ kept, for $j = 5,$ $\ldots,$ $10,$ sum to $\begin{aligned} &-\frac{1}{2} + 0 + \frac{1}{2} + \frac{\sqrt{3}}{2} \\ &\quad {}+ 1 + \frac{\sqrt{3}}{2} = 1 + \sqrt{3}. \end{aligned}$

The maximum is $\begin{aligned} &8\left(2 + 2\sqrt{3}\right) \\ &= 16 + 16\sqrt{3} \\ &= 16 + \sqrt{768}, \end{aligned}$ so $m + n = 16 + 768 = 784.$

9.

Let $x_1,$ $x_2,$ $\ldots,$ $x_6$ be nonnegative real numbers such that $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 =$ $1,$ and $x_1x_3x_5 + x_2x_4x_6 \ge \frac{1}{540}.$ Let $p$ and $q$ be positive relatively prime integers such that $\frac{p}{q}$ is the maximum possible value of $\begin{aligned} &x_1x_2x_3 + x_2x_3x_4 \\ &\quad {}+ x_3x_4x_5 + x_4x_5x_6 \\ &\quad {}+ x_5x_6x_1 + x_6x_1x_2. \end{aligned}$ Find $p + q.$

Answer

Answer: 559

Concepts:AM-GM Inequality factoring bounding to limit cases

Difficulty rating: 3060

Small Hint:

The cyclic sum plus the constrained quantity $x_1x_3x_5 + x_2x_4x_6$ factors as $(x_1 + x_4)(x_2 + x_5)(x_3 + x_6)$

Big Hint:

AM-GM bounds that product by $\frac{1}{27},$ and equality together with a tight constraint is achievable

Solution:

Let $r = x_1x_3x_5 + x_2x_4x_6$ and let $s$ be the cyclic sum in question. Expanding $(x_1 + x_4)(x_2 + x_5)(x_3 + x_6)$ produces eight triple products, which are exactly the six terms of $s$ together with the two terms of $r.$ So $r + s =$ $(x_1 + x_4)(x_2 + x_5)(x_3 + x_6),$ and by AM-GM this is at most $\left(\frac{1}{3}\right)^3 = \frac{1}{27}.$

Therefore $\begin{aligned} s &\le \frac{1}{27} - r \\ &\le \frac{1}{27} - \frac{1}{540} \\ &= \frac{20 - 1}{540} = \frac{19}{540}. \end{aligned}$ Equality needs $x_1 + x_4 = x_2 + x_5 = x_3 + x_6 =$ $\frac{1}{3}$ with $r = \frac{1}{540}:$ take $x_1 = x_3 = \frac{3}{10},$ $x_5 = \frac{1}{60},$ $x_2 = \frac{19}{60},$ $x_4 = x_6 = \frac{1}{30}.$ Then $r = \frac{9}{6000} + \frac{19}{54000} = \frac{100}{54000} = \frac{1}{540},$ as required.

So the maximum is $\frac{19}{540},$ and $p + q = 19 + 540 = 559.$

10.

A circle with center $O$ has radius $25.$ Chord $\overline{AB}$ of length $30$ and chord $\overline{CD}$ of length $14$ intersect at point $P.$ The distance between the midpoints of the two chords is $12.$ The quantity $OP^2$ can be represented as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find the remainder when $m + n$ is divided by $1000.$

Answer

Answer: 57

Concepts:chord cyclic quadrilateral law of cosines law of sines

Difficulty rating: 2990

Small Hint:

Let $M$ and $N$ be the chords’ midpoints; then $OM \perp AB,$ $ON \perp CD,$ and $OM = 20,$ $ON = 24$

Big Hint:

The right angles at $M$ and $N$ put them on the circle with diameter $OP;$ there $MN = OP \sin \angle MON,$ with $\angle MON$ from the law of cosines

Solution:

Let $M$ and $N$ be the midpoints of $\overline{AB}$ and $\overline{CD}.$ The segment from the center to a chord’s midpoint is perpendicular to the chord, so $OM = \sqrt{25^2 - 15^2} = 20$ and $ON = \sqrt{25^2 - 7^2} = 24,$ with $MN = 12.$

Since $P$ lies on both chords, $\angle OMP = \angle ONP = 90^\circ,$ so $M$ and $N$ lie on the circle with diameter $OP.$ In triangle $OMN,$ the law of cosines gives $\begin{aligned} \cos \angle MON &= \frac{20^2 + 24^2 - 12^2}{2 \cdot 20 \cdot 24} \\ &= \frac{832}{960} = \frac{13}{15}, \end{aligned}$ so $\sin \angle MON = \frac{2\sqrt{14}}{15}.$ In the circle through $O,$ $M,$ $P,$ $N,$ the extended law of sines says the chord $MN$ equals the diameter $OP$ times $\sin \angle MON,$ so $\begin{aligned} OP &= \frac{12}{\frac{2\sqrt{14}}{15}} = \frac{90}{\sqrt{14}}, \end{aligned}$ $\begin{aligned} OP^2 &= \frac{8100}{14} = \frac{4050}{7}. \end{aligned}$

Then $m + n = 4050 + 7 = 4057,$ which leaves remainder $57$ upon division by $1000.$

11.

Let $M_n$ be the $n \times n$ matrix with entries as follows: for $1 \le i \le n,$ $m_{i,i} = 10;$ for $1 \le i \le n - 1,$ $m_{i+1,i} = m_{i,i+1} = 3;$ all other entries in $M_n$ are zero. Let $D_n$ be the determinant of matrix $M_n.$ Then $\sum_{n=1}^{\infty} \frac{1}{8D_n + 1}$ can be represented as $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

Note: The determinant of the $1 \times 1$ matrix $[a]$ is $a,$ and the determinant of the $2 \times 2$ matrix $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ is $ad - bc;$ for $n \ge 2,$ the determinant of an $n \times n$ matrix with first row or first column $a_1$ $a_2$ $a_3$ $\ldots$ $a_n$ is equal to $a_1C_1 - a_2C_2$ $+ a_3C_3 - \cdots$ $+ (-1)^{n+1}a_nC_n,$ where $C_i$ is the determinant of the $(n - 1) \times (n - 1)$ matrix formed by eliminating the row and column containing $a_i.$

Answer

Answer: 73

Concepts:determinant recursion geometric sequence

Difficulty rating: 2920

Small Hint:

Cofactor expansion along the first row gives $D_n = 10D_{n-1} - 9D_{n-2}$

Big Hint:

Solving the recurrence with $D_1 = 10,$ $D_2 = 91$ gives $8D_n + 1 = 9^{n+1},$ so the series is geometric

Solution:

Expanding $D_n$ along the first row gives $10 D_{n-1}$ minus $3$ times a cofactor whose first column is $(3, 0, \ldots, 0);$ expanding that cofactor down its first column leaves $3 D_{n-2}.$ Hence $D_n = 10 D_{n-1} - 9 D_{n-2},$ with $D_1 = 10$ and $D_2 = 100 - 9 = 91.$

The characteristic equation $k^2 = 10k - 9$ has roots $9$ and $1,$ and fitting the initial values gives $D_n = \frac{9^{n+1} - 1}{8}.$ Therefore $8D_n + 1 = 9^{n+1},$ and $\begin{aligned} \sum_{n=1}^{\infty} \frac{1}{8D_n + 1} &= \sum_{n=1}^{\infty} \frac{1}{9^{n+1}} \\ &= \frac{\frac{1}{81}}{1 - \frac{1}{9}} = \frac{1}{72}. \end{aligned}$

Thus $\frac{p}{q} = \frac{1}{72}$ and $p + q = 73.$

12.

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate from another country be $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Answer

Answer: 97

Concepts:circular arrangements complementary counting inclusion-exclusion

Difficulty rating: 3060

Small Hint:

A delegate sits next to only compatriots exactly when his country’s three delegates occupy three consecutive chairs; count the complement

Big Hint:

Only the country pattern matters: $\frac{9!}{3!\,3!\,3!} = 1680$ equally likely patterns; apply inclusion-exclusion to the three consecutive-block events

Solution:

Only the pattern of countries in the nine chairs matters, and all $\frac{9!}{3!\,3!\,3!} = 1680$ patterns are equally likely. The condition fails for some delegate exactly when both of his neighbors are compatriots, which happens exactly when some country’s three delegates occupy three consecutive chairs. Let $A_i$ be the set of patterns in which country $i$ ’s delegates are consecutive.

There are $9$ triples of consecutive chairs, so $|A_i| = 9\binom{6}{3} = 180,$ choosing which $3$ of the remaining $6$ chairs go to one of the other countries. For two countries, after placing the first block ( $9$ ways) the remaining six chairs form an arc containing $4$ triples of consecutive chairs, so $|A_i \cap A_j| = 9 \cdot 4 = 36.$ For all three, the circle must split into three consecutive triples ( $3$ ways) assigned to the countries in $3!$ orders: $|A_1 \cap A_2 \cap A_3| = 18.$ By inclusion-exclusion, $\begin{aligned} |A_1 \cup A_2 \cup A_3| &= 3 \cdot 180 - 3 \cdot 36 \\ &\quad {}+ 18 = 450. \end{aligned}$

The probability is $1 - \frac{450}{1680} = 1 - \frac{15}{56} = \frac{41}{56},$ so $m + n = 41 + 56 = 97.$

13.

Point $P$ lies on the diagonal $AC$ of square $ABCD$ with $AP \gt CP.$ Let $O_1$ and $O_2$ be the circumcenters of triangles $ABP$ and $CDP,$ respectively. Given that $AB = 12$ and $\angle O_1PO_2 = 120^\circ,$ then $AP = \sqrt{a} + \sqrt{b},$ where $a$ and $b$ are positive integers. Find $a + b.$

Answer

Answer: 96

Concepts:circumcircle, circumcenter, and circumradius coordinate geometry vector

Difficulty rating: 3160

Small Hint:

Use coordinates: both circumcenters lie on the vertical line $x = 6,$ and with $P = (p, p)$ they work out to $(6,\, p - 6)$ and $(6,\, p + 6)$

Big Hint:

Apply the cosine formula to the vectors from $P$ to the two centers and solve $(p - 6)^2 = 12$

Solution:

Place $A = (0, 0),$ $B = (12, 0),$ $C = (12, 12),$ $D = (0, 12),$ and $P = (p, p)$ with $p \gt 6.$ Since $O_1$ is equidistant from $A$ and $B,$ it lies on $x = 6;$ setting $O_1 = (6, k)$ and equating $O_1A^2 = O_1P^2$ gives $k = p - 6,$ so $O_1 = (6,\, p - 6).$ Similarly $O_2,$ equidistant from $C$ and $D,$ is $O_2 = (6,\, p + 6).$

The vectors from $P$ to the centers are $(6 - p,\, -6)$ and $(6 - p,\, 6),$ so $\begin{aligned} \cos 120^\circ &= \frac{(6 - p)^2 - 36}{(6 - p)^2 + 36} \\ &= -\frac{1}{2}, \end{aligned}$ which gives $3(p - 6)^2 = 36,$ so $(p - 6)^2 = 12$ and $p = 6 + 2\sqrt{3}.$

Then $AP = p\sqrt{2} = 6\sqrt{2} + 2\sqrt{6} =$ $\sqrt{72} + \sqrt{24},$ so $a + b = 72 + 24 = 96.$

14.

There are $N$ permutations $(a_1, a_2, \ldots, a_{30})$ of $1,$ $2,$ $\ldots,$ $30$ such that for $m \in \{2, 3, 5\},$ $m$ divides $a_{n+m} - a_n$ for all integers $n$ with $1 \le n \lt n + m \le 30.$ Find the remainder when $N$ is divided by $1000.$

Answer

Answer: 440

Concepts:Chinese Remainder Theorem modular arithmetic permutations

Difficulty rating: 3270

Small Hint:

The conditions say that $a_n \bmod m$ depends only on $n \bmod m,$ for each of $m = 2,$ $3,$ and $5$

Big Hint:

By CRT, positions and values both correspond to triples of residues mod $2,$ $3,$ $5;$ a valid permutation is exactly a choice of one residue permutation for each modulus

Solution:

For each $m \in \{2, 3, 5\},$ the condition $a_{n+m} \equiv a_n \pmod{m}$ means the residue of $a_n$ modulo $m$ depends only on $n \bmod m,$ defining a map $\sigma_m$ from residues to residues. Each residue class of positions has $\frac{30}{m}$ members, and so does each residue class of values; if $\sigma_m$ sent two position classes to the same value class, that class’s $\frac{30}{m}$ values would have to fill $\frac{60}{m}$ positions, which is impossible. So each $\sigma_m$ is a permutation of the residues modulo $m.$

Conversely, by the Chinese remainder theorem each position $n \in \{1, \ldots, 30\}$ corresponds to a unique triple $(n \bmod 2,\, n \bmod 3,\, n \bmod 5),$ and likewise for values. Any choice of permutations $(\sigma_2, \sigma_3, \sigma_5)$ therefore determines a unique valid permutation of $1, \ldots, 30,$ sending the position triple to the prescribed value triple.

Hence $N = 2! \cdot 3! \cdot 5! = 1440,$ and the remainder upon division by $1000$ is $440.$

15.

Let $P(x) = x^2 - 3x - 9.$ A real number $x$ is chosen at random from the interval $5 \le x \le 15.$ The probability that $\left\lfloor \sqrt{P(x)} \right\rfloor = \sqrt{P(\lfloor x \rfloor)}$ is equal to $\frac{\sqrt{a} + \sqrt{b} + \sqrt{c} - d}{e},$ where $a,$ $b,$ $c,$ $d,$ and $e$ are positive integers. Find $a + b + c + d + e.$

Answer

Answer: 850

Concepts:floor and ceiling functions geometric probability perfect square casework

Difficulty rating: 3370

Small Hint:

For $x \in [n, n+1)$ the right side is $\sqrt{P(n)},$ which must be an integer: find the $n$ with $P(n)$ a perfect square

Big Hint:

Only $n = 5,$ $6,$ and $13$ work; on each such interval solve $P(x) \lt \left(\sqrt{P(n)} + 1\right)^2$ for the valid subinterval

Solution:

For $x \in [n, n + 1)$ the right-hand side is $\sqrt{P(n)},$ which must be an integer, so $P(n) = n^2 - 3n - 9$ must be a perfect square. For $n = 5,$ $6,$ $\ldots,$ $14$ the values are $1,$ $9,$ $19,$ $31,$ $45,$ $61,$ $79,$ $99,$ $121,$ $145:$ only $n = 5,$ $6,$ and $13$ give squares, with $\sqrt{P(n)} = 1,$ $3,$ and $11,$ respectively.

$P$ is increasing on $[5, 15],$ so for $x \in [n, n + 1)$ we automatically have $\sqrt{P(x)} \ge \sqrt{P(n)},$ and $\left\lfloor \sqrt{P(x)} \right\rfloor = \sqrt{P(n)} = m$ holds exactly when $P(x) \lt (m + 1)^2,$ i.e. $x \lt \frac{3 + \sqrt{45 + 4(m+1)^2}}{2}.$ For $m = 1,$ $3,$ and $11$ the cutoffs are $\frac{3 + \sqrt{61}}{2},$ $\frac{3 + \sqrt{109}}{2},$ $\frac{3 + \sqrt{621}}{2},$ each lying inside the corresponding unit interval, so the successful subintervals have lengths $\frac{\sqrt{61} - 7}{2},$ $\frac{\sqrt{109} - 9}{2},$ $\frac{\sqrt{621} - 23}{2}.$

The interval $[5, 15]$ has length $10,$ so the probability is $\begin{aligned} &\frac{1}{10} \\ &\quad {}\cdot \frac{\sqrt{61} + \sqrt{109} + \sqrt{621} - 39}{2} \\ &= \frac{\sqrt{61} + \sqrt{109} + \sqrt{621} - 39}{20}, \end{aligned}$ giving $a + b + c + d + e =$ $61 + 109 + 621 + 39 + 20 =$ $850.$