Soluciones del 2023 AIME II | LIVE by Po-Shen Loh

1.

El número de manzanas que crecen en cada uno de seis manzanos forma una progresión aritmética, donde el mayor número de manzanas en cualquiera de los seis árboles es el doble del menor número de manzanas en cualquiera de los seis árboles. El número total de manzanas en los seis árboles es $990.$ Halla el mayor número de manzanas en cualquiera de los seis árboles.

The numbers of apples growing on each of six apple trees form an arithmetic sequence where the greatest number of apples growing on any of the six trees is double the least number of apples growing on any of the six trees. The total number of apples growing on all six trees is $990.$ Find the greatest number of apples growing on any of the six trees.

Respuesta

Conceptos:sucesión aritmética ecuación lineal

Nivel de dificultad: 1890

Solución:

Sean las seis cantidades $a, a+d, \ldots, a+5d$ con diferencia común $d \ge 0.$ La mayor cantidad es el doble de la menor, así que $a + 5d = 2a,$ lo que da $a = 5d.$ El total es $\begin{aligned} 6a + 15d &= 30d + 15d \\ &= 45d = 990, \end{aligned}$ por lo que $d = 22.$

El mayor número de manzanas es $a + 5d = 10d = 220.$

Let the six counts be $a, a+d, \ldots, a+5d$ with common difference $d \ge 0.$ The greatest count is double the least, so $a + 5d = 2a,$ which gives $a = 5d.$ The total is $\begin{aligned} 6a + 15d &= 30d + 15d \\ &= 45d = 990, \end{aligned}$ so $d = 22.$

The greatest number of apples is $a + 5d = 10d = 220.$

2.

Recuerda que un palíndromo es un número que se lee igual de izquierda a derecha que de derecha a izquierda. Halla el mayor entero menor que $1000$ que sea palíndromo tanto escrito en base diez como escrito en base ocho, como $292 = 444_{\text{eight}}.$

Recall that a palindrome is a number that reads the same forward and backward. Find the greatest integer less than $1000$ that is a palindrome both when written in base ten and when written in base eight, such as $292 = 444_{\text{eight}}.$

Respuesta

Conceptos:palíndromo base numérica enumeración sistemática

Nivel de dificultad: 2070

Solución:

Un número de cuatro dígitos en base ocho está entre $512$ y $4095,$ así que un palíndromo en base ocho menor que $1000$ con cuatro dígitos debe tener el dígito inicial (y final) igual a $1:$ tiene la forma $\overline{1bb1}_{\text{eight}} = 512 + 64b$ ${}+ 8b + 1$ $= 513 + 72b.$ Para mantenerlo por debajo de $1000$ se necesita $b \le 6,$ lo que da los candidatos $513, 585, 657, 729, 801, 873, 945.$

Comprobando de mayor a menor, el único de estos que también es palíndromo en base diez es $585 = 1111_{\text{eight}}.$ Todo palíndromo en base ocho con a lo sumo tres dígitos es a lo sumo $777_{\text{eight}} = 511 \lt 585,$ así que la respuesta es $585.$

A four-digit base-eight number lies between $512$ and $4095,$ so a base-eight palindrome less than $1000$ with four digits must have leading (and trailing) digit $1:$ it has the form $\overline{1bb1}_{\text{eight}} = 512 + 64b$ ${}+ 8b + 1$ $= 513 + 72b.$ Keeping this below $1000$ requires $b \le 6,$ giving the candidates $513, 585, 657, 729, 801, 873, 945.$

Checking from the top, the only one of these that is also a palindrome in base ten is $585 = 1111_{\text{eight}}.$ Every base-eight palindrome with at most three digits is at most $777_{\text{eight}} = 511 \lt 585,$ so the answer is $585.$

3.

Sea $\triangle ABC$ un triángulo isósceles con $\angle A = 90^\circ.$ Existe un punto $P$ dentro de $\triangle ABC$ tal que $\angle PAB = \angle PBC = \angle PCA$ y $AP = 10.$ Halla el área de $\triangle ABC.$

Let $\triangle ABC$ be an isosceles triangle with $\angle A = 90^\circ.$ There exists a point $P$ inside $\triangle ABC$ such that $\angle PAB = \angle PBC = \angle PCA$ and $AP = 10.$ Find the area of $\triangle ABC.$

Respuesta

Conceptos:persecución de ángulos ley de los senos trigonometría

Nivel de dificultad: 2460

Solución:

Sea $\omega$ el ángulo común y $L = AB = AC.$ Como $\angle PAB = \omega,$ tenemos $\angle PAC = 90^\circ - \omega,$ y con $\angle PCA = \omega$ los ángulos del triángulo $APC$ dan $\angle APC = 90^\circ.$ Por lo tanto, en el triángulo rectángulo $APC,$ $L = AC = \frac{AP}{\sin\omega} = \frac{10}{\sin\omega}.$

En el triángulo $ABP,$ el ángulo en $A$ es $\omega$ y el ángulo en $B$ es $45^\circ - \omega,$ así que $\angle APB = 135^\circ.$ La ley de senos da $\frac{AP}{\sin(45^\circ - \omega)} = \frac{AB}{\sin 135^\circ},$ es decir, $10 \sin 135^\circ = L \sin(45^\circ - \omega).$ Sustituyendo $L = \frac{10}{\sin\omega}$ y desarrollando se obtiene $\begin{aligned} \sin\omega &= \sqrt{2}\,\sin(45^\circ - \omega) \\ &= \cos\omega - \sin\omega, \end{aligned}$ así que $\tan\omega = \frac{1}{2}$ y $\sin^2\omega = \frac{1}{5}.$

Por lo tanto $L^2 = \frac{100}{\sin^2\omega} = 500,$ y el área es $\frac{1}{2}L^2 = 250.$

Let $\omega$ denote the common angle and $L = AB = AC.$ Since $\angle PAB = \omega,$ we have $\angle PAC = 90^\circ - \omega,$ and with $\angle PCA = \omega$ the angles of triangle $APC$ give $\angle APC = 90^\circ.$ Hence in right triangle $APC,$ $L = AC = \frac{AP}{\sin\omega} = \frac{10}{\sin\omega}.$

In triangle $ABP,$ the angle at $A$ is $\omega$ and the angle at $B$ is $45^\circ - \omega,$ so $\angle APB = 135^\circ.$ The law of sines gives $\frac{AP}{\sin(45^\circ - \omega)} = \frac{AB}{\sin 135^\circ},$ that is, $10 \sin 135^\circ = L \sin(45^\circ - \omega).$ Substituting $L = \frac{10}{\sin\omega}$ and expanding yields $\begin{aligned} \sin\omega &= \sqrt{2}\,\sin(45^\circ - \omega) \\ &= \cos\omega - \sin\omega, \end{aligned}$ so $\tan\omega = \frac{1}{2}$ and $\sin^2\omega = \frac{1}{5}.$

Therefore $L^2 = \frac{100}{\sin^2\omega} = 500,$ and the area is $\frac{1}{2}L^2 = 250.$

4.

Sean $x,$ $y,$ y $z$ números reales que satisfacen el sistema de ecuaciones $\begin{aligned} xy + 4z &= 60, \\ yz + 4x &= 60, \\ zx + 4y &= 60. \end{aligned}$

Sea $S$ el conjunto de los posibles valores de $x.$ Halla la suma de los cuadrados de los elementos de $S.$

Let $x,$ $y,$ and $z$ be real numbers satisfying the system of equations $\begin{aligned} xy + 4z &= 60, \\ yz + 4x &= 60, \\ zx + 4y &= 60. \end{aligned}$

Let $S$ be the set of possible values of $x.$ Find the sum of the squares of the elements of $S.$

Respuesta

Conceptos:sistema de ecuaciones factorización simetría (álgebra)

Nivel de dificultad: 2460

Solución:

Restar la segunda ecuación de la primera da $xy - yz + 4z - 4x = 0,$ que se factoriza como $(y - 4)(x - z) = 0.$ Así que $y = 4$ o $x = z.$

Si $y = 4:$ la primera ecuación se convierte en $4x + 4z = 60,$ así que $x + z = 15,$ y la segunda vuelve a ser $4z + 4x = 60$ mientras que la tercera da $zx = 44.$ Entonces $x$ y $z$ son raíces de $t^2 - 15t + 44 = (t - 4)(t - 11),$ así que $x \in \{4, 11\}.$

Si $x = z:$ la primera ecuación queda $x(y + 4) = 60,$ así que $y = \frac{60}{x} - 4,$ y la tercera queda $x^2 + 4y = 60.$ Sustituyendo, $\begin{gathered} x^2 + \frac{240}{x} - 16 = 60 \\ \Longrightarrow x^3 - 76x + 240 = 0 \\ = (x - 4)(x - 6)(x + 10), \end{gathered}$ así que $x \in \{4, 6, -10\},$ cada uno con $y$ y $z$ reales. Por lo tanto $S = \{-10, 4, 6, 11\}$ y la suma de los cuadrados es $100 + 16 + 36 + 121 = 273.$

Subtracting the second equation from the first gives $xy - yz + 4z - 4x = 0,$ which factors as $(y - 4)(x - z) = 0.$ So $y = 4$ or $x = z.$

If $y = 4:$ the first equation becomes $4x + 4z = 60,$ so $x + z = 15,$ and the second becomes $4z + 4x = 60$ again while the third gives $zx = 44.$ Then $x$ and $z$ are roots of $t^2 - 15t + 44 = (t - 4)(t - 11),$ so $x \in \{4, 11\}.$

If $x = z:$ the first equation reads $x(y + 4) = 60,$ so $y = \frac{60}{x} - 4,$ and the third reads $x^2 + 4y = 60.$ Substituting, $\begin{gathered} x^2 + \frac{240}{x} - 16 = 60 \\ \Longrightarrow x^3 - 76x + 240 = 0 \\ = (x - 4)(x - 6)(x + 10), \end{gathered}$ so $x \in \{4, 6, -10\},$ each with real $y$ and $z.$ Hence $S = \{-10, 4, 6, 11\}$ and the sum of squares is $100 + 16 + 36 + 121 = 273.$

5.

Sea $S$ el conjunto de todos los números racionales positivos $r$ tales que, cuando los dos números $r$ y $55r$ se escriben como fracciones irreducibles, la suma del numerador y el denominador de una fracción es igual a la suma del numerador y el denominador de la otra fracción. La suma de todos los elementos de $S$ puede expresarse en la forma $\frac{p}{q},$ donde $p$ y $q$ son enteros positivos primos entre sí. Halla $p + q.$

Let $S$ be the set of all positive rational numbers $r$ such that when the two numbers $r$ and $55r$ are written as fractions in lowest terms, the sum of the numerator and denominator of one fraction is the same as the sum of the numerator and denominator of the other fraction. The sum of all the elements of $S$ can be expressed in the form $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

Respuesta

Conceptos:fracción máximo común divisor análisis por casos

Nivel de dificultad: 2740

Solución:

Escribe $r = \frac{a}{b}$ en forma irreducible y sea $g = \gcd(b, 55).$ Entonces $55r$ en forma irreducible es $\frac{55a/g}{b/g}$ (no es posible una cancelación adicional, ya que $\gcd(a, b) = 1$ y $55$ es libre de cuadrados). La condición es $a + b = \frac{55a}{g} + \frac{b}{g}.$ Si $g = 1$ esto obliga a $a = 55a,$ imposible; si $g = 55$ obliga a $b = \frac{b}{55},$ imposible.

Si $g = 5:$ $a + b = 11a + \frac{b}{5}$ da $\frac{4b}{5} = 10a,$ así que $2b = 25a.$ Como $\gcd(a, b) = 1,$ necesitamos $a = 2$ y $b = 25,$ de modo que $r = \frac{2}{25}$ (en efecto $2 + 25 = 27 = 22 + 5$ a partir de $55r = \frac{22}{5}$ ). Si $g = 11:$ $a + b = 5a + \frac{b}{11}$ da $\frac{10b}{11} = 4a,$ así que $5b = 22a,$ obligando a $a = 5,$ $b = 22$ y $r = \frac{5}{22}$ (con $5 + 22 = 27 = 25 + 2$ a partir de $55r = \frac{25}{2}$ ).

Por lo tanto $S = \left\{\frac{2}{25}, \frac{5}{22}\right\}$ y la suma es $\frac{2}{25} + \frac{5}{22} = \frac{44 + 125}{550} = \frac{169}{550},$ que ya es irreducible. La respuesta es $169 + 550 = 719.$

Write $r = \frac{a}{b}$ in lowest terms and let $g = \gcd(b, 55).$ Then $55r$ in lowest terms is $\frac{55a/g}{b/g}$ (no further cancellation is possible since $\gcd(a, b) = 1$ and $55$ is squarefree). The condition is $a + b = \frac{55a}{g} + \frac{b}{g}.$ If $g = 1$ this forces $a = 55a,$ impossible; if $g = 55$ it forces $b = \frac{b}{55},$ impossible.

If $g = 5:$ $a + b = 11a + \frac{b}{5}$ gives $\frac{4b}{5} = 10a,$ so $2b = 25a.$ Since $\gcd(a, b) = 1,$ we need $a = 2$ and $b = 25,$ so $r = \frac{2}{25}$ (indeed $2 + 25 = 27 = 22 + 5$ from $55r = \frac{22}{5}$ ). If $g = 11:$ $a + b = 5a + \frac{b}{11}$ gives $\frac{10b}{11} = 4a,$ so $5b = 22a,$ forcing $a = 5,$ $b = 22$ and $r = \frac{5}{22}$ (with $5 + 22 = 27 = 25 + 2$ from $55r = \frac{25}{2}$ ).

Hence $S = \left\{\frac{2}{25}, \frac{5}{22}\right\}$ and the sum is $\frac{2}{25} + \frac{5}{22} = \frac{44 + 125}{550} = \frac{169}{550},$ already in lowest terms. The answer is $169 + 550 = 719.$

6.

Considera la región en forma de L formada por tres cuadrados unitarios unidos por sus lados, como se muestra abajo. Se eligen dos puntos $A$ y $B$ de manera independiente y uniforme al azar dentro de la región. La probabilidad de que el punto medio de $\overline{AB}$ también esté dentro de esta región en forma de L puede expresarse como $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m + n.$

Consider the L-shaped region formed by three unit squares joined at their sides, as shown below. Two points $A$ and $B$ are chosen independently and uniformly at random from inside the region. The probability that the midpoint of $\overline{AB}$ also lies inside this L-shaped region can be expressed as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Conceptos:probabilidad geométrica eventos independientes análisis por casos

Nivel de dificultad: 2740

Solución:

Coloca la región como $[0,1]^2 \cup \bigl([0,1] \times [1,2]\bigr)$ $\cup \bigl([1,2] \times [0,1]\bigr),$ de modo que es el cuadrado $2 \times 2$ al que se le quita el cuadrado unitario superior derecho. Ambas coordenadas del punto medio son promedios de números en $[0, 2],$ así que el punto medio siempre está en el cuadrado $2 \times 2$ ; no está en la región exactamente cuando cae en el cuadrado que falta, es decir, cuando $x_A + x_B \gt 2$ y $y_A + y_B \gt 2.$

Si ninguno de los puntos está en el cuadrado derecho, entonces $x_A + x_B \le 2;$ si ninguno está en el cuadrado superior, entonces $y_A + y_B \le 2.$ Así que el fallo requiere un punto en el cuadrado superior y el otro en el cuadrado derecho, lo que ocurre con probabilidad $2 \cdot \frac{1}{3} \cdot \frac{1}{3} = \frac{2}{9}.$ En ese caso, una coordenada $x$ es uniforme en $[0,1]$ y la otra en $[1,2],$ así que $x_A + x_B \gt 2$ con probabilidad $\frac{1}{2},$ e independientemente $y_A + y_B \gt 2$ con probabilidad $\frac{1}{2}.$

La probabilidad de fallo es $\frac{2}{9} \cdot \frac{1}{4} = \frac{1}{18},$ así que la probabilidad buscada es $\frac{17}{18}$ y $m + n = 17 + 18 = 35.$

Place the region as $[0,1]^2 \cup \bigl([0,1] \times [1,2]\bigr)$ $\cup \bigl([1,2] \times [0,1]\bigr),$ so it is the $2 \times 2$ square with the top-right unit square removed. Both coordinates of the midpoint are averages of numbers in $[0, 2],$ so the midpoint always lies in the $2 \times 2$ square; it fails to lie in the region exactly when it lands in the missing square, i.e. when $x_A + x_B \gt 2$ and $y_A + y_B \gt 2.$

If neither point is in the right square, then $x_A + x_B \le 2;$ if neither is in the top square, then $y_A + y_B \le 2.$ So failure requires one point in the top square and the other in the right square, which happens with probability $2 \cdot \frac{1}{3} \cdot \frac{1}{3} = \frac{2}{9}.$ In that case, one $x$ -coordinate is uniform on $[0,1]$ and the other on $[1,2],$ so $x_A + x_B \gt 2$ with probability $\frac{1}{2},$ and independently $y_A + y_B \gt 2$ with probability $\frac{1}{2}.$

The failure probability is $\frac{2}{9} \cdot \frac{1}{4} = \frac{1}{18},$ so the desired probability is $\frac{17}{18}$ and $m + n = 17 + 18 = 35.$

7.

Cada vértice de un dodecágono regular ( $12$ -gono) se colorea de rojo o de azul, por lo que hay $2^{12}$ coloraciones posibles. Halla el número de estas coloraciones con la propiedad de que no haya cuatro vértices del mismo color que sean los cuatro vértices de un rectángulo.

Each vertex of a regular dodecagon ( $12$ -gon) is to be colored either red or blue, and thus there are $2^{12}$ possible colorings. Find the number of these colorings with the property that no four vertices colored the same color are the four vertices of a rectangle.

Respuesta

Conceptos:arreglos con restricciones principio de multiplicación análisis por casos

Nivel de dificultad: 2600

Solución:

Los doce vértices están sobre una circunferencia, y un rectángulo inscrito en una circunferencia debe tener sus diagonales pasando por el centro. Así que los rectángulos con vértices entre los doce son exactamente las parejas de diámetros distintos, donde los diámetros unen los $6$ pares antipodales de vértices. Aparece un rectángulo monocromático exactamente cuando dos pares antipodales están coloreados por completo del mismo color.

Cada par antipodal es, de manera independiente, ambos rojos ( $1$ forma), ambos azules ( $1$ forma) o mixto ( $2$ formas). Una coloración es válida exactamente cuando a lo sumo un par es de ambos rojos y a lo sumo un par es de ambos azules. Contando según el número de pares totalmente rojos y totalmente azules: $\begin{gathered} 2^6 + 6 \cdot 2^5 \\ {}+ 6 \cdot 2^5 + 6 \cdot 5 \cdot 2^4 \\ = 64 + 192 + 192 + 480 \\ = 928. \end{gathered}$

The twelve vertices lie on a circle, and a rectangle inscribed in a circle must have its diagonals pass through the center. So the rectangles with vertices among the twelve are exactly the pairs of distinct diameters, where the diameters join the $6$ antipodal pairs of vertices. A monochromatic rectangle appears exactly when two antipodal pairs are each colored solidly in the same color.

Each antipodal pair is independently both red ( $1$ way), both blue ( $1$ way), or mixed ( $2$ ways). A coloring is valid exactly when at most one pair is both red and at most one pair is both blue. Counting by the numbers of solid red and solid blue pairs: $\begin{gathered} 2^6 + 6 \cdot 2^5 \\ {}+ 6 \cdot 2^5 + 6 \cdot 5 \cdot 2^4 \\ = 64 + 192 + 192 + 480 \\ = 928. \end{gathered}$

8.

Sea $\omega = \cos\frac{2\pi}{7} + i \cdot \sin\frac{2\pi}{7},$ donde $i = \sqrt{-1}.$ Halla el valor del producto $\prod_{k=0}^{6} \left(\omega^{3k} + \omega^k + 1\right).$

Let $\omega = \cos\frac{2\pi}{7} + i \cdot \sin\frac{2\pi}{7},$ where $i = \sqrt{-1}.$ Find the value of the product $\prod_{k=0}^{6} \left(\omega^{3k} + \omega^k + 1\right).$

Respuesta

Conceptos:raíces de la unidad polinomio número complejo

Nivel de dificultad: 2840

Solución:

Sea $P(x) = x^3 + x + 1,$ así que el producto es $\prod_{k=0}^{6} P(\omega^k),$ donde $\omega^0, \ldots, \omega^6$ son todas las raíces séptimas de la unidad. Como $x^7 - 1 = \prod_k (x - \omega^k),$ escribir $P(x)$ $= (x - \beta_1)(x - \beta_2)(x - \beta_3)$ e intercambiar el orden del producto doble da $\begin{gathered} \prod_{k=0}^{6} P(\omega^k) \\ = \prod_{j=1}^{3} \prod_{k=0}^{6} (\omega^k - \beta_j) \\ = \prod_{j=1}^{3} \bigl(-(\beta_j^7 - 1)\bigr) \\ = \prod_{j=1}^{3} (1 - \beta_j^7). \end{gathered}$

Para una raíz $\beta$ de $P,$ usar repetidamente $\beta^3 = -\beta - 1$ da $\beta^4 = -\beta^2 - \beta,$ $\beta^5 = -\beta^2 + \beta + 1,$ $\beta^6 = \beta^2 + 2\beta + 1,$ y $\beta^7 = 2\beta^2 - 1.$ Por lo tanto $1 - \beta^7 = 2(1 - \beta)(1 + \beta),$ y $\begin{gathered} \prod_{j} (1 - \beta_j^7) \\ = 2^3 \prod_j (1 - \beta_j) \prod_j (1 + \beta_j) \\ = 8 \cdot P(1) \cdot \bigl(-P(-1)\bigr) \\ = 8 \cdot 3 \cdot 1 = 24. \end{gathered}$

Así que el producto pedido es igual a $24.$

Let $P(x) = x^3 + x + 1,$ so the product is $\prod_{k=0}^{6} P(\omega^k),$ where $\omega^0, \ldots, \omega^6$ are all seventh roots of unity. Since $x^7 - 1 = \prod_k (x - \omega^k),$ writing $P(x)$ $= (x - \beta_1)(x - \beta_2)(x - \beta_3)$ and swapping the order of the double product gives $\begin{gathered} \prod_{k=0}^{6} P(\omega^k) \\ = \prod_{j=1}^{3} \prod_{k=0}^{6} (\omega^k - \beta_j) \\ = \prod_{j=1}^{3} \bigl(-(\beta_j^7 - 1)\bigr) \\ = \prod_{j=1}^{3} (1 - \beta_j^7). \end{gathered}$

For a root $\beta$ of $P,$ repeatedly using $\beta^3 = -\beta - 1$ gives $\beta^4 = -\beta^2 - \beta,$ $\beta^5 = -\beta^2 + \beta + 1,$ $\beta^6 = \beta^2 + 2\beta + 1,$ and $\beta^7 = 2\beta^2 - 1.$ Hence $1 - \beta^7 = 2(1 - \beta)(1 + \beta),$ and $\begin{gathered} \prod_{j} (1 - \beta_j^7) \\ = 2^3 \prod_j (1 - \beta_j) \prod_j (1 + \beta_j) \\ = 8 \cdot P(1) \cdot \bigl(-P(-1)\bigr) \\ = 8 \cdot 3 \cdot 1 = 24. \end{gathered}$

So the requested product equals $24.$

9.

Las circunferencias $\omega_1$ y $\omega_2$ se cortan en dos puntos $P$ y $Q,$ y su tangente común más cercana a $P$ corta a $\omega_1$ y $\omega_2$ en los puntos $A$ y $B,$ respectivamente. La recta paralela a $\overline{AB}$ que pasa por $P$ corta a $\omega_1$ y $\omega_2$ por segunda vez en los puntos $X$ y $Y,$ respectivamente. Supón que $PX = 10,$ $PY = 14,$ y $PQ = 5.$ Entonces el área del trapecio $XABY$ es $m\sqrt{n},$ donde $m$ y $n$ son enteros positivos y $n$ no es divisible por el cuadrado de ningún primo. Halla $m + n.$

Circles $\omega_1$ and $\omega_2$ intersect at two points $P$ and $Q,$ and their common tangent line closer to $P$ intersects $\omega_1$ and $\omega_2$ at points $A$ and $B,$ respectively. The line parallel to $\overline{AB}$ that passes through $P$ intersects $\omega_1$ and $\omega_2$ for the second time at points $X$ and $Y,$ respectively. Suppose $PX = 10,$ $PY = 14,$ and $PQ = 5.$ Then the area of trapezoid $XABY$ is $m\sqrt{n},$ where $m$ and $n$ are positive integers and $n$ is not divisible by the square of any prime. Find $m + n.$

Respuesta

Conceptos:potencia de un punto eje radical trapecio

Nivel de dificultad: 2920

Solución:

Como la tangente a $\omega_1$ en $A$ es paralela a la cuerda $XP,$ el punto $A$ es el punto medio del arco $XP,$ así que la perpendicular desde $A$ a la recta $XY$ cae en el punto medio de $\overline{XP};$ de forma similar, la perpendicular desde $B$ cae en el punto medio de $\overline{PY}.$ Como $X$ y $Y$ están en lados opuestos de $P,$ los lados paralelos del trapecio son $XY = 10 + 14 = 24$ y $AB = \frac{10}{2} + \frac{14}{2} = 12.$

La recta $PQ$ es el eje radical, así que su intersección $M$ con la tangente satisface $MA^2 = MP \cdot MQ = MB^2:$ $M$ es el punto medio de $\overline{AB},$ y con $MA = 6$ y $MQ = MP + 5,$ $\begin{gathered} 36 = MP(MP + 5), \\ MP = 4. \end{gathered}$

Establece coordenadas a lo largo de $AB:$ los pies de $A$ y $B$ son los puntos medios de $XP$ y $PY,$ así que $P$ está a $5$ unidades del primer pie, mientras que $M$ está a $6$ unidades de $A.$ Por lo tanto el desplazamiento horizontal entre $M$ y $P$ es $6 - 5 = 1,$ y la altura $h$ del trapecio satisface $h^2 = MP^2 - 1 = 15.$ El área es $\frac{24 + 12}{2}\sqrt{15} = 18\sqrt{15},$ así que $m + n = 18 + 15 = 33.$

Since the tangent to $\omega_1$ at $A$ is parallel to the chord $XP,$ the point $A$ is the midpoint of arc $XP,$ so the perpendicular from $A$ to line $XY$ lands at the midpoint of $\overline{XP};$ similarly the perpendicular from $B$ lands at the midpoint of $\overline{PY}.$ As $X$ and $Y$ are on opposite sides of $P,$ the parallel sides of the trapezoid are $XY = 10 + 14 = 24$ and $AB = \frac{10}{2} + \frac{14}{2} = 12.$

Line $PQ$ is the radical axis, so its intersection $M$ with the tangent line satisfies $MA^2 = MP \cdot MQ = MB^2:$ $M$ is the midpoint of $\overline{AB},$ and with $MA = 6$ and $MQ = MP + 5,$ $\begin{gathered} 36 = MP(MP + 5), \\ MP = 4. \end{gathered}$

Set up coordinates along $AB:$ the feet of $A$ and $B$ are the midpoints of $XP$ and $PY,$ so $P$ lies $5$ units from the first foot, while $M$ lies $6$ units from $A.$ Hence the horizontal offset between $M$ and $P$ is $6 - 5 = 1,$ and the height $h$ of the trapezoid satisfies $h^2 = MP^2 - 1 = 15.$ The area is $\frac{24 + 12}{2}\sqrt{15} = 18\sqrt{15},$ so $m + n = 18 + 15 = 33.$

10.

Sea $N$ el número de formas de colocar los enteros del $1$ al $12$ en las $12$ celdas de una cuadrícula de $2 \times 6$ de modo que, para cualesquiera dos celdas que comparten un lado, la diferencia entre los números de esas celdas no sea divisible por $3.$ Abajo se muestra una forma de hacerlo. Halla el número de divisores enteros positivos de $N.$

Let $N$ be the number of ways to place the integers $1$ through $12$ in the $12$ cells of a $2 \times 6$ grid so that for any two cells sharing a side, the difference between the numbers in those cells is not divisible by $3.$ One way to do this is shown below. Find the number of positive integer divisors of $N.$

Respuesta

Conceptos:aritmética modular permutaciones de multiconjuntos conteo de factores

Nivel de dificultad: 2920

Solución:

La condición dice que las celdas adyacentes tienen residuos distintos módulo $3.$ Cada clase de residuos entre $1, \ldots, 12$ tiene exactamente $4$ miembros, así que $N = K \cdot (4!)^3,$ donde $K$ es el número de formas de rellenar la cuadrícula con residuos $0, 1, 2,$ cada uno usado $4$ veces, con celdas adyacentes distintas.

Una columna es un par ordenado $(a, b)$ de residuos distintos. Si la columna actual es $(a, b)$ y $e$ es el tercer residuo, la siguiente columna debe ser una de $(b, a),$ $(b, e),$ $(e, a):$ cada uno de los tres pares no ordenados $\{a,b\},$ $\{b,e\},$ $\{a,e\}$ aparece en exactamente una orientación permitida. Así que un patrón de residuos queda determinado por la sucesión de seis pares no ordenados junto con la orientación de la primera columna. Como cada residuo debe aparecer $4$ veces, cada uno de los tres pares debe usarse exactamente dos veces, lo que da $\frac{6!}{2!\,2!\,2!} = 90$ sucesiones y $K = 2 \cdot 90 = 180.$

Por lo tanto $N = 180 \cdot 24^3$ $= 2{,}488{,}320$ $= 2^{11} \cdot 3^5 \cdot 5,$ que tiene $12 \cdot 6 \cdot 2 = 144$ divisores positivos.

The condition says adjacent cells have different residues mod $3.$ Each residue class among $1, \ldots, 12$ has exactly $4$ members, so $N = K \cdot (4!)^3,$ where $K$ is the number of ways to fill the grid with residues $0, 1, 2,$ each used $4$ times, with adjacent cells different.

A column is an ordered pair $(a, b)$ of distinct residues. If the current column is $(a, b)$ and $e$ is the third residue, the next column must be one of $(b, a),$ $(b, e),$ $(e, a):$ each of the three unordered pairs $\{a,b\},$ $\{b,e\},$ $\{a,e\}$ occurs in exactly one allowed orientation. So a residue pattern is determined by the sequence of six unordered pairs together with the orientation of the first column. Since each residue must appear $4$ times, each of the three pairs must be used exactly twice, giving $\frac{6!}{2!\,2!\,2!} = 90$ sequences and $K = 2 \cdot 90 = 180.$

Therefore $N = 180 \cdot 24^3$ $= 2{,}488{,}320$ $= 2^{11} \cdot 3^5 \cdot 5,$ which has $12 \cdot 6 \cdot 2 = 144$ positive divisors.

11.

Halla el número de familias de $16$ subconjuntos distintos de $\{1, 2, 3, 4, 5\}$ con la propiedad de que, para cualesquiera dos subconjuntos $X$ y $Y$ de la familia, $X \cap Y \neq \emptyset.$

Find the number of collections of $16$ distinct subsets of $\{1, 2, 3, 4, 5\}$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \neq \emptyset.$

Respuesta

Conceptos:subconjuntos teoría de grafos análisis por casos

Nivel de dificultad: 3060

Solución:

Los $32$ subconjuntos se dividen en $16$ pares complementarios $\{X, X^{\mathsf{c}}\},$ y ninguna familia puede contener ambos miembros de un par (son disjuntos). Por tanto, una familia de $16$ subconjuntos que se cortan dos a dos debe contener exactamente un miembro de cada par; en particular contiene $\{1,2,3,4,5\}$ y no $\emptyset.$

Si se elige algún conjunto unitario $\{x\},$ todo miembro debe cortar a $\{x\},$ es decir, contener $x.$ Exactamente un conjunto de cada par complementario contiene $x,$ así que la familia debe ser exactamente los $16$ subconjuntos que contienen $x:$ esto da $5$ familias. En caso contrario no se elige ningún conjunto unitario, así que los cinco conjuntos de $4$ elementos están en la familia. Dos subconjuntos cualesquiera de $3$ elementos de un conjunto de $5$ elementos se cortan, un conjunto de $4$ elementos es disjunto solo de su complemento, y un conjunto elegido de $2$ elementos y un conjunto elegido de $3$ elementos son disjuntos solo si son complementarios, lo cual no puede darse con ambos elegidos. Así que la única condición que queda es que los conjuntos elegidos de $2$ elementos se corten dos a dos.

Viendo los conjuntos de $2$ elementos como aristas de $K_5,$ una familia de aristas que se cortan dos a dos, o bien tiene todas las aristas pasando por un vértice común, o bien es un triángulo. El número de tales familias de aristas es: la familia vacía ( $1$ ), los triángulos ( $\binom{5}{3} = 10$ ), y las familias no vacías dentro de una estrella, $5(2^4 - 1) - 10 = 65$ (restando las $10$ aristas simples contadas en sus dos extremos). Eso da $1 + 10 + 65 = 76$ familias, para un total de $5 + 76 = 81.$

The $32$ subsets split into $16$ complementary pairs $\{X, X^{\mathsf{c}}\},$ and no collection can contain both members of a pair (they are disjoint). A collection of $16$ pairwise-intersecting subsets must therefore contain exactly one member of every pair; in particular it contains $\{1,2,3,4,5\}$ and not $\emptyset.$

If some singleton $\{x\}$ is chosen, every member must meet $\{x\},$ i.e. contain $x.$ Exactly one set in each complementary pair contains $x,$ so the collection must be exactly the $16$ subsets containing $x:$ this gives $5$ collections. Otherwise no singleton is chosen, so all five $4$ -element sets are in the collection. Any two $3$ -element subsets of a $5$ -element set intersect, a $4$ -element set is disjoint only from its complement, and a chosen $2$ -element set and a chosen $3$ -element set are disjoint only if they are complements, which cannot both be chosen. So the only remaining condition is that the chosen $2$ -element sets pairwise intersect.

Viewing $2$ -element sets as edges of $K_5,$ a pairwise-intersecting collection of edges either has all edges through one common vertex or is a triangle. The number of such edge families is: the empty family ( $1$ ), triangles ( $\binom{5}{3} = 10$ ), and nonempty families within a star, $5(2^4 - 1) - 10 = 65$ (subtracting the $10$ single edges counted at both endpoints). That is $1 + 10 + 65 = 76$ collections, for a total of $5 + 76 = 81.$

12.

En $\triangle ABC$ con longitudes de lado $AB = 13,$ $BC = 14,$ y $CA = 15,$ sea $M$ el punto medio de $\overline{BC}.$ Sea $P$ el punto de la circunferencia circunscrita de $\triangle ABC$ tal que $M$ está sobre $\overline{AP}.$ Existe un único punto $Q$ sobre el segmento $\overline{AM}$ tal que $\angle PBQ = \angle PCQ.$ Entonces $AQ$ puede escribirse como $\frac{m}{\sqrt{n}},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m + n.$

In $\triangle ABC$ with side lengths $AB = 13,$ $BC = 14,$ and $CA = 15,$ let $M$ be the midpoint of $\overline{BC}.$ Let $P$ be the point on the circumcircle of $\triangle ABC$ such that $M$ is on $\overline{AP}.$ There exists a unique point $Q$ on segment $\overline{AM}$ such that $\angle PBQ = \angle PCQ.$ Then $AQ$ can be written as $\frac{m}{\sqrt{n}},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Conceptos:geometría analítica potencia de un punto vector

Nivel de dificultad: 3160

Solución:

Coloca $B = (0, 0),$ $C = (14, 0),$ $A = (5, 12),$ así que $M = (7, 0)$ y $AM = \sqrt{4 + 144} = 2\sqrt{37}.$ Por la potencia del punto $M$ en la circunferencia circunscrita, $MA \cdot MP = MB \cdot MC = 49,$ así que $MP = \frac{49}{2\sqrt{37}}$ y prolongar $A \to M$ esa longitud da $P = \left(\frac{567}{74}, -\frac{147}{37}\right).$ La dirección de $\overrightarrow{BP}$ es proporcional a $(27, -14),$ y la dirección de $\overrightarrow{CP}$ es proporcional a $-(67, 42).$

Escribe $Q = (5 + 2t,\ 12 - 12t)$ para $t \in (0, 1),$ de modo que $AQ = t \cdot AM.$ Usando $\tan\theta = \frac{|u \times v|}{u \cdot v}$ para el ángulo entre semirrectas, $\begin{gathered} \tan\angle PBQ = \frac{394 - 296t}{222t - 33}, \\ \tan\angle PCQ = \frac{1182 - 888t}{370t + 99}, \end{gathered}$ y el segundo numerador es exactamente $3(394 - 296t).$ Igualar las dos tangentes cancela este factor común y deja $370t + 99 = 3(222t - 33),$ así que $296t = 198$ y $t = \frac{99}{148}.$

Entonces $AQ = \frac{99}{148} \cdot 2\sqrt{37}$ $= \frac{99}{148}\sqrt{148}$ $= \frac{99}{\sqrt{148}},$ y como $\gcd(99, 148) = 1,$ la respuesta es $99 + 148 = 247.$

Place $B = (0, 0),$ $C = (14, 0),$ $A = (5, 12),$ so $M = (7, 0)$ and $AM = \sqrt{4 + 144} = 2\sqrt{37}.$ By power of the point $M$ in the circumcircle, $MA \cdot MP = MB \cdot MC = 49,$ so $MP = \frac{49}{2\sqrt{37}}$ and extending $A \to M$ by that length gives $P = \left(\frac{567}{74}, -\frac{147}{37}\right).$ The direction of $\overrightarrow{BP}$ is proportional to $(27, -14),$ and the direction of $\overrightarrow{CP}$ is proportional to $-(67, 42).$

Write $Q = (5 + 2t,\ 12 - 12t)$ for $t \in (0, 1),$ so that $AQ = t \cdot AM.$ Using $\tan\theta = \frac{|u \times v|}{u \cdot v}$ for the angle between rays, $\begin{gathered} \tan\angle PBQ = \frac{394 - 296t}{222t - 33}, \\ \tan\angle PCQ = \frac{1182 - 888t}{370t + 99}, \end{gathered}$ and the second numerator is exactly $3(394 - 296t).$ Setting the two tangents equal cancels this common factor and leaves $370t + 99 = 3(222t - 33),$ so $296t = 198$ and $t = \frac{99}{148}.$

Then $AQ = \frac{99}{148} \cdot 2\sqrt{37}$ $= \frac{99}{148}\sqrt{148}$ $= \frac{99}{\sqrt{148}},$ and since $\gcd(99, 148) = 1,$ the answer is $99 + 148 = 247.$

13.

Sea $A$ un ángulo agudo tal que $\tan A = 2 \cos A.$ Halla el número de enteros positivos $n$ menores o iguales que $1000$ tales que $\sec^n A + \tan^n A$ sea un entero positivo cuyo dígito de las unidades es $9.$

Let $A$ be an acute angle such that $\tan A = 2 \cos A.$ Find the number of positive integers $n$ less than or equal to $1000$ such that $\sec^n A + \tan^n A$ is a positive integer whose units digit is $9.$

Respuesta

Conceptos:identidad trigonométrica recursión dígito de las unidades

Nivel de dificultad: 3060

Solución:

Sea $s = \sec A$ y $t = \tan A.$ La hipótesis $\tan A = 2\cos A$ dice que $\tan A \sec A = 2,$ es decir $st = 2,$ y siempre $s^2 - t^2 = 1.$ Entonces $(s^2 + t^2)^2$ $= (s^2 - t^2)^2 + 4s^2t^2$ $= 17,$ así que $u = s^2$ y $v = t^2$ satisfacen $u + v = \sqrt{17},$ $uv = 4.$ Las sumas $w_m = u^m + v^m$ cumplen $w_{m+1} = \sqrt{17}\,w_m - 4w_{m-1}$ con $w_0 = 2,$ $w_1 = \sqrt{17};$ por inducción, $w_m$ es un entero positivo para $m$ par y un entero por $\sqrt{17}$ para $m$ impar.

Para $n = 2m$ par, $s^n + t^n = w_m,$ que es entero exactamente cuando $m$ es par, es decir $4 \mid n.$ Para $n$ impar, $(s^n + t^n)^2$ $= w_n + 2 (st)^n$ $= w_n + 2^{n+1}$ es irracional, así que $s^n + t^n$ no es entero. Por tanto escribe $n = 4j$ y $x_j = w_{2j}.$ Como $u^2 + v^2 = 9$ y $u^2 v^2 = 16,$ los enteros $x_j$ satisfacen $\begin{gathered} x_{j+1} = 9x_j - 16x_{j-1}, \\ x_0 = 2, \\ x_1 = 9, \end{gathered}$ dando $9, 49, 297, 1889, \ldots$ cuyos dígitos de las unidades se repiten con periodo tres: $9, 9, 7.$ El dígito de las unidades es $7$ cuando $3 \mid j$ y $9$ en caso contrario.

Los $n \le 1000$ válidos son $n = 4j$ con $1 \le j \le 250$ y $3 \nmid j:$ hay $250 - 83 = 167$ de ellos.

Let $s = \sec A$ and $t = \tan A.$ The hypothesis $\tan A = 2\cos A$ says $\tan A \sec A = 2,$ i.e. $st = 2,$ and always $s^2 - t^2 = 1.$ Then $(s^2 + t^2)^2$ $= (s^2 - t^2)^2 + 4s^2t^2$ $= 17,$ so $u = s^2$ and $v = t^2$ satisfy $u + v = \sqrt{17},$ $uv = 4.$ The sums $w_m = u^m + v^m$ obey $w_{m+1} = \sqrt{17}\,w_m - 4w_{m-1}$ with $w_0 = 2,$ $w_1 = \sqrt{17};$ by induction $w_m$ is a positive integer for even $m$ and an integer times $\sqrt{17}$ for odd $m.$

For even $n = 2m,$ $s^n + t^n = w_m,$ an integer exactly when $m$ is even, i.e. $4 \mid n.$ For odd $n,$ $(s^n + t^n)^2$ $= w_n + 2 (st)^n$ $= w_n + 2^{n+1}$ is irrational, so $s^n + t^n$ is not an integer. Thus write $n = 4j$ and $x_j = w_{2j}.$ Since $u^2 + v^2 = 9$ and $u^2 v^2 = 16,$ the integers $x_j$ satisfy $\begin{gathered} x_{j+1} = 9x_j - 16x_{j-1}, \\ x_0 = 2, \\ x_1 = 9, \end{gathered}$ giving $9, 49, 297, 1889, \ldots$ whose units digits repeat with period three: $9, 9, 7.$ The units digit is $7$ when $3 \mid j$ and $9$ otherwise.

The valid $n \le 1000$ are $n = 4j$ with $1 \le j \le 250$ and $3 \nmid j:$ there are $250 - 83 = 167$ of them.

14.

Un contenedor con forma de cubo tiene vértices $A,$ $B,$ $C,$ y $D,$ donde $\overline{AB}$ y $\overline{CD}$ son aristas paralelas del cubo, y $\overline{AC}$ y $\overline{BD}$ son diagonales de caras del cubo, como se muestra. El vértice $A$ del cubo se apoya sobre un plano horizontal $\mathcal{P}$ de modo que el plano del rectángulo $ABDC$ es perpendicular a $\mathcal{P},$ el vértice $B$ está $2$ metros por encima de $\mathcal{P},$ el vértice $C$ está $8$ metros por encima de $\mathcal{P},$ y el vértice $D$ está $10$ metros por encima de $\mathcal{P}.$ El cubo contiene agua cuya superficie es paralela a $\mathcal{P}$ a una altura de $7$ metros por encima de $\mathcal{P}.$ El volumen de agua es $\frac{m}{n}$ metros cúbicos, donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m + n.$

A cube-shaped container has vertices $A,$ $B,$ $C,$ and $D,$ where $\overline{AB}$ and $\overline{CD}$ are parallel edges of the cube, and $\overline{AC}$ and $\overline{BD}$ are diagonals of faces of the cube, as shown. Vertex $A$ of the cube is set on a horizontal plane $\mathcal{P}$ so that the plane of the rectangle $ABDC$ is perpendicular to $\mathcal{P},$ vertex $B$ is $2$ meters above $\mathcal{P},$ vertex $C$ is $8$ meters above $\mathcal{P},$ and vertex $D$ is $10$ meters above $\mathcal{P}.$ The cube contains water whose surface is parallel to $\mathcal{P}$ at a height of $7$ meters above $\mathcal{P}.$ The volume of water is $\frac{m}{n}$ cubic meters, where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Conceptos:geometría del cubo volumen geometría analítica cálculo

Nivel de dificultad: 3270

Solución:

Da al cubo coordenadas de modo que $A$ sea el origen, las aristas vayan a lo largo de los ejes, y la longitud de la arista sea $s:$ entonces $B = (s, 0, 0),$ $C = (0, s, s),$ $D = (s, s, s)$ cumplen la descripción ( $\overline{AB} \parallel \overline{CD}$ son aristas y $\overline{AC},$ $\overline{BD}$ son diagonales de caras). La altura por encima de $\mathcal{P}$ es una función lineal $h(x, y, z) = u_1 x + u_2 y + u_3 z$ para algún vector unitario $u.$ El plano del rectángulo $ABDC$ tiene dirección normal $(0, 1, -1),$ y la perpendicularidad a $\mathcal{P}$ significa que la dirección vertical $u$ está en ese plano, así que $u_2 = u_3.$ Las alturas de $B$ y $C$ dan $s u_1 = 2$ y $s(u_2 + u_3) = 8,$ así que $su_2 = su_3 = 4,$ y $|u| = 1$ obliga a $s^2 = 2^2 + 4^2 + 4^2 = 36.$ Por tanto $s = 6$ y $u = \frac{1}{3}(1, 2, 2)$ (y en efecto $h(D) = 10$ ).

El agua es la región de $[0, 6]^3$ donde $h \le 7,$ es decir $x + 2y + 2z \le 21.$ Para $x = a$ fijo, la sección es $\{(y, z) \in [0,6]^2 : y + z \le \tfrac{21 - a}{2}\},$ y como $\frac{21 - a}{2}$ está entre $6$ y $12,$ su área es $36 - \frac{1}{2}\left(12 - \frac{21 - a}{2}\right)^2$ $= 36 - \frac{(3 + a)^2}{8}.$

Integrando, $\begin{gathered} V = \int_0^6 \left(36 - \frac{(3 + a)^2}{8}\right) da \\ = 216 - \frac{9^3 - 3^3}{24} \\ = 216 - \frac{702}{24} \\ = \frac{747}{4}, \end{gathered}$ así que $m + n = 747 + 4 = 751.$

Give the cube coordinates so that $A$ is the origin, the edges lie along the axes, and the edge length is $s:$ then $B = (s, 0, 0),$ $C = (0, s, s),$ $D = (s, s, s)$ satisfy the description ( $\overline{AB} \parallel \overline{CD}$ are edges and $\overline{AC},$ $\overline{BD}$ are face diagonals). Height above $\mathcal{P}$ is a linear function $h(x, y, z) = u_1 x + u_2 y + u_3 z$ for some unit vector $u.$ The plane of rectangle $ABDC$ has normal direction $(0, 1, -1),$ and perpendicularity to $\mathcal{P}$ means the vertical direction $u$ lies in that plane, so $u_2 = u_3.$ The heights of $B$ and $C$ give $s u_1 = 2$ and $s(u_2 + u_3) = 8,$ so $su_2 = su_3 = 4,$ and $|u| = 1$ forces $s^2 = 2^2 + 4^2 + 4^2 = 36.$ Thus $s = 6$ and $u = \frac{1}{3}(1, 2, 2)$ (and indeed $h(D) = 10$ ).

The water is the region of $[0, 6]^3$ where $h \le 7,$ i.e. $x + 2y + 2z \le 21.$ For fixed $x = a,$ the slice is $\{(y, z) \in [0,6]^2 : y + z \le \tfrac{21 - a}{2}\},$ and since $\frac{21 - a}{2}$ lies between $6$ and $12,$ its area is $36 - \frac{1}{2}\left(12 - \frac{21 - a}{2}\right)^2$ $= 36 - \frac{(3 + a)^2}{8}.$

Integrating, $\begin{gathered} V = \int_0^6 \left(36 - \frac{(3 + a)^2}{8}\right) da \\ = 216 - \frac{9^3 - 3^3}{24} \\ = 216 - \frac{702}{24} \\ = \frac{747}{4}, \end{gathered}$ so $m + n = 747 + 4 = 751.$

15.

Para cada entero positivo $n,$ sea $a_n$ el menor múltiplo entero positivo de $23$ tal que $a_n \equiv 1 \pmod{2^n}.$ Halla el número de enteros positivos $n$ menores o iguales que $1000$ que satisfacen $a_n = a_{n+1}.$

For each positive integer $n$ let $a_n$ be the least positive integer multiple of $23$ such that $a_n \equiv 1 \pmod{2^n}.$ Find the number of positive integers $n$ less than or equal to $1000$ that satisfy $a_n = a_{n+1}.$

Respuesta

Conceptos:aritmética modular base numérica orden multiplicativo

Nivel de dificultad: 3370

Solución:

Escribe $a_n = 23 b_n,$ donde $b_n$ es el único entero de $[1, 2^n]$ con $23 b_n \equiv 1 \pmod{2^n},$ es decir, el inverso de $23$ módulo $2^n.$ Reducir módulo $2^n$ muestra que $b_{n+1} \in \{b_n,\ b_n + 2^n\},$ así que $a_n = a_{n+1}$ exactamente cuando $b_{n+1} = b_n,$ lo que ocurre exactamente cuando el dígito binario de peso $2^n$ en $b_{n+1}$ es $0.$

Como $23 \cdot 89 = 2047 = 2^{11} - 1,$ poniendo $T_k = 1 + 2^{11} + 2^{22}$ ${}+ \cdots + 2^{11(k-1)}$ se obtiene $23 \cdot 89\,T_k = 2^{11k} - 1,$ así que $\begin{gathered} 23\left(2^{11k} - 89\,T_k\right) \\ \equiv 1 \pmod{2^{11k}}, \end{gathered}$ y todo $b_n$ con $n \le 11k$ es la reducción de $2^{11k} - 89\,T_k$ módulo $2^n.$ En binario, $89 = 1011001_{\text{two}}$ ocupa las posiciones $0, 3, 4, 6$ de cada bloque de $11$ bits de $89\,T_k.$ Como $89\,T_k$ es impar, $2^{11k} - 89\,T_k$ $= \bigl(2^{11k} - 1 - 89\,T_k\bigr) + 1$ mantiene el dígito $0$ igual a $1$ y complementa todos los dígitos en las posiciones $1$ hasta $11k - 1.$

Así que para $n \ge 1,$ el dígito de peso $2^n$ es $0$ exactamente cuando $n \equiv 0, 3, 4, 6 \pmod{11}.$ Entre $1 \le n \le 1000 = 90 \cdot 11 + 10,$ el residuo $0$ aparece $90$ veces y los residuos $3,$ $4,$ $6$ aparecen $91$ veces cada uno, para un total de $90 + 3 \cdot 91 = 363.$

Write $a_n = 23 b_n,$ where $b_n$ is the unique integer in $[1, 2^n]$ with $23 b_n \equiv 1 \pmod{2^n},$ i.e. the inverse of $23$ mod $2^n.$ Reducing mod $2^n$ shows $b_{n+1} \in \{b_n,\ b_n + 2^n\},$ so $a_n = a_{n+1}$ exactly when $b_{n+1} = b_n,$ which happens exactly when the binary digit of weight $2^n$ in $b_{n+1}$ is $0.$

Since $23 \cdot 89 = 2047 = 2^{11} - 1,$ setting $T_k = 1 + 2^{11} + 2^{22}$ ${}+ \cdots + 2^{11(k-1)}$ gives $23 \cdot 89\,T_k = 2^{11k} - 1,$ so $\begin{gathered} 23\left(2^{11k} - 89\,T_k\right) \\ \equiv 1 \pmod{2^{11k}}, \end{gathered}$ and every $b_n$ with $n \le 11k$ is the reduction of $2^{11k} - 89\,T_k$ mod $2^n.$ In binary, $89 = 1011001_{\text{two}}$ occupies positions $0, 3, 4, 6$ of each $11$ -bit block of $89\,T_k.$ Since $89\,T_k$ is odd, $2^{11k} - 89\,T_k$ $= \bigl(2^{11k} - 1 - 89\,T_k\bigr) + 1$ keeps digit $0$ equal to $1$ and complements every digit in positions $1$ through $11k - 1.$

So for $n \ge 1,$ the digit of weight $2^n$ is $0$ exactly when $n \equiv 0, 3, 4, 6 \pmod{11}.$ Among $1 \le n \le 1000 = 90 \cdot 11 + 10,$ the residue $0$ occurs $90$ times and the residues $3,$ $4,$ $6$ occur $91$ times each, for a total of $90 + 3 \cdot 91 = 363.$