Soluciones del 1998 AIME | LIVE by Po-Shen Loh

1.

¿Para cuántos valores de $k$ es $12^{12}$ el mínimo común múltiplo de los enteros positivos $6^6,$ $8^8,$ y $k$ ?

For how many values of $k$ is $12^{12}$ the least common multiple of the positive integers $6^6,$ $8^8,$ and $k?$

Respuesta

Conceptos:mínimo común múltiplo factorización en primos

Nivel de dificultad: 1890

Pista pequeña:

Factoriza todo en potencias de $2$ y $3:$ $12^{12} = 2^{24} 3^{12},$ $6^6 = 2^6 3^6,$ $8^8 = 2^{24}$

Factor everything into powers of $2$ and $3:$ $12^{12} = 2^{24} 3^{12},$ $6^6 = 2^6 3^6,$ $8^8 = 2^{24}$

Pista grande:

El mínimo común múltiplo de $6^6$ y $8^8$ ya aporta $2^{24}$ , pero solo $3^6,$ así que $k$ debe aportar exactamente $3^{12}$

The lcm of $6^6$ and $8^8$ already supplies $2^{24}$ but only $3^6,$ so $k$ must contribute exactly $3^{12}$

Solución:

Como $12^{12} = 2^{24} 3^{12},$ $6^6 = 2^6 3^6,$ y $8^8 = 2^{24},$ el número $k$ no puede contener primos distintos de $2$ y $3,$ así que escribimos $k = 2^a 3^b.$ El mínimo común múltiplo de los tres números es entonces $2^{\max(24,\,a)} \, 3^{\max(6,\,b)}.$

Igualarlo a $2^{24} 3^{12}$ exige $\max(24, a) = 24,$ es decir $0 \le a \le 24,$ y $\max(6, b) = 12,$ es decir $b = 12.$ Eso da $25$ opciones para $a$ y una para $b,$ así que hay $25$ valores de $k.$

Since $12^{12} = 2^{24} 3^{12},$ $6^6 = 2^6 3^6,$ and $8^8 = 2^{24},$ the number $k$ can involve no primes other than $2$ and $3,$ so write $k = 2^a 3^b.$ The least common multiple of the three numbers is then $2^{\max(24,\,a)} \, 3^{\max(6,\,b)}.$

Matching this to $2^{24} 3^{12}$ requires $\max(24, a) = 24,$ i.e. $0 \le a \le 24,$ and $\max(6, b) = 12,$ i.e. $b = 12.$ That gives $25$ choices for $a$ and one for $b,$ so there are $25$ values of $k.$

2.

Halla el número de pares ordenados $(x, y)$ de enteros positivos que satisfacen $x \le 2y \le 60$ y $y \le 2x \le 60.$

Find the number of ordered pairs $(x, y)$ of positive integers that satisfy $x \le 2y \le 60$ and $y \le 2x \le 60.$

Respuesta

Conceptos:conteo de pares desigualdad conteo complementario simetría

Nivel de dificultad: 2110

Pista pequeña:

Las cuatro restricciones juntas confinan a $(x, y)$ al cuadrado $1 \le x, y \le 30$

All four constraints together confine $(x, y)$ to the square $1 \le x, y \le 30$

Pista grande:

Dentro de ese cuadrado, resta los pares con $y \gt 2x$ y los que tienen $x \gt 2y;$ los dos conjuntos malos son disjuntos y tienen el mismo tamaño

Inside that square, subtract the pairs with $y \gt 2x$ and those with $x \gt 2y;$ the two bad sets are disjoint and have equal size

Solución:

Las cadenas se desglosan en cuatro condiciones: $x \le 2y,$ $2y \le 60,$ $y \le 2x,$ y $2x \le 60.$ Así que $(x, y)$ está en el cuadrado $1 \le x, y \le 30,$ y dentro de él debemos evitar $x \gt 2y$ y $y \gt 2x,$ que no pueden ocurrir a la vez.

Pares con $y \gt 2x:$ para cada $x$ de $1$ a $14$ , los valores $y = 2x + 1, \ldots, 30$ funcionan, lo que da $\sum_{x=1}^{14} (30 - 2x)$ $= 420 - 210$ $= 210$ pares. Por la simetría de intercambiar $x$ e $y,$ también hay $210$ pares con $x \gt 2y.$

Así que la respuesta es $30 \cdot 30 - 210 - 210 = 480.$

The chains unpack into four conditions: $x \le 2y,$ $2y \le 60,$ $y \le 2x,$ and $2x \le 60.$ So $(x, y)$ lies in the square $1 \le x, y \le 30,$ and within it we must avoid $x \gt 2y$ and $y \gt 2x,$ which cannot both happen.

Pairs with $y \gt 2x:$ for each $x$ from $1$ to $14$ the values $y = 2x + 1, \ldots, 30$ work, giving $\sum_{x=1}^{14} (30 - 2x)$ $= 420 - 210$ $= 210$ pairs. By the symmetry swapping $x$ and $y,$ there are also $210$ pairs with $x \gt 2y.$

The answer is $30 \cdot 30 - 210 - 210 = 480.$

3.

La gráfica de $y^2 + 2xy + 40|x| = 400$ divide el plano en varias regiones. ¿Cuál es el área de la región acotada?

The graph of $y^2 + 2xy + 40|x| = 400$ partitions the plane into several regions. What is the area of the bounded region?

Respuesta

Conceptos:valor absoluto geometría analítica factorización paralelogramo

Nivel de dificultad: 2340

Pista pequeña:

Para $x \ge 0$ , la ecuación se reordena como $2x(y + 20) = 400 - y^2,$ y el lado derecho se factoriza

For $x \ge 0$ the equation rearranges to $2x(y + 20) = 400 - y^2,$ and the right side factors

Pista grande:

Cada caso de signo produce dos rectas; los cuatro rayos acotan un paralelogramo con lados horizontales en $y = 20$ y $y = -20$

Each sign case yields two lines; the four rays bound a parallelogram with horizontal sides on $y = 20$ and $y = -20$

Solución:

Para $x \ge 0$ , reescribe la ecuación como $2x(y + 20)$ $= 400 - y^2$ $= (20 - y)(20 + y),$ de modo que $y = -20$ o $y = 20 - 2x.$ Para $x \le 0$ se vuelve $2x(y - 20) = -(y - 20)(y + 20),$ de modo que $y = 20$ o $y = -20 - 2x.$ Por lo tanto, la gráfica consta de dos rayos horizontales y dos rayos de pendiente $-2.$

Estos rayos acotan un paralelogramo: el lado superior va de $(-20, 20)$ a $(0, 20)$ a lo largo de $y = 20,$ el lado inferior de $(0, -20)$ a $(20, -20)$ a lo largo de $y = -20,$ y los dos lados inclinados de pendiente $-2$ los conectan.

El paralelogramo tiene base horizontal $20$ y altura $40$ entre las rectas $y = 20$ y $y = -20,$ así que su área es $20 \cdot 40 = 800.$

For $x \ge 0$ rewrite the equation as $2x(y + 20)$ $= 400 - y^2$ $= (20 - y)(20 + y),$ so either $y = -20$ or $y = 20 - 2x.$ For $x \le 0$ it becomes $2x(y - 20) = -(y - 20)(y + 20),$ so either $y = 20$ or $y = -20 - 2x.$ The graph therefore consists of two horizontal rays and two rays of slope $-2.$

These rays bound a parallelogram: the top edge runs from $(-20, 20)$ to $(0, 20)$ along $y = 20,$ the bottom edge from $(0, -20)$ to $(20, -20)$ along $y = -20,$ and the two slanted edges of slope $-2$ connect them.

The parallelogram has horizontal base $20$ and height $40$ between the lines $y = 20$ and $y = -20,$ so its area is $20 \cdot 40 = 800.$

4.

Nueve fichas están numeradas $1,$ $2,$ $3,$ $\ldots,$ $9,$ respectivamente. Cada uno de los tres jugadores selecciona al azar y conserva tres de las fichas, y suma esos tres valores. La probabilidad de que los tres jugadores obtengan una suma impar es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m + n.$

Nine tiles are numbered $1,$ $2,$ $3,$ $\ldots,$ $9,$ respectively. Each of three players randomly selects and keeps three of the tiles, and sums those three values. The probability that all three players obtain an odd sum is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Conceptos:probabilidad básica paridad combinaciones

Nivel de dificultad: 2350

Pista pequeña:

La suma de un jugador es impar exactamente cuando el jugador tiene un número impar de fichas impares; hay cinco fichas impares en total

A player’s sum is odd exactly when the player holds an odd number of odd tiles; there are five odd tiles in all

Pista grande:

Las fichas impares deben repartirse $3,$ $1,$ $1$ entre los jugadores. Cuenta por separado las formas de repartir las impares y las pares.

The odd tiles must split $3,$ $1,$ $1$ among the players. Count the ways to deal odds and evens separately.

Solución:

Las tres fichas de un jugador tienen suma impar exactamente cuando el jugador tiene un número impar de fichas impares, una o tres. Las nueve fichas incluyen cinco impares y cuatro pares, y la única manera de repartir cinco fichas impares en tres grupos de tamaño uno o tres es $3 + 1 + 1.$

Cuenta los repartos favorables: elige qué jugador recibe tres fichas impares ( $3$ formas), elige las fichas impares de ese jugador ( $\binom{5}{3} = 10$ formas), da una de las dos fichas impares restantes a cada uno de los otros dos jugadores ( $2$ formas), y luego reparte las cuatro fichas pares dos y dos entre esos jugadores ( $\binom{4}{2} = 6$ formas), lo que da $3 \cdot 10 \cdot 2 \cdot 6 = 360$ repartos. El número total de repartos es $\binom{9}{3}\binom{6}{3} = 84 \cdot 20 = 1680.$

La probabilidad es $\frac{360}{1680} = \frac{3}{14},$ así que $m + n = 3 + 14 = 17.$

A player’s three tiles have an odd sum exactly when the player holds an odd number of odd tiles — one or three. The nine tiles include five odd and four even, and the only way to split five odd tiles into three groups of size one or three is $3 + 1 + 1.$

Count favorable deals: choose which player gets three odd tiles ( $3$ ways), choose that player’s odd tiles ( $\binom{5}{3} = 10$ ways), give one of the two remaining odd tiles to each other player ( $2$ ways), then split the four even tiles two and two between those players ( $\binom{4}{2} = 6$ ways), for $3 \cdot 10 \cdot 2 \cdot 6 = 360$ deals. The total number of deals is $\binom{9}{3}\binom{6}{3} = 84 \cdot 20 = 1680.$

The probability is $\frac{360}{1680} = \frac{3}{14},$ so $m + n = 3 + 14 = 17.$

5.

Dado que $A_k = \frac{k(k - 1)}{2}\cos\frac{k(k - 1)\pi}{2},$ halla $|A_{19} + A_{20} + \cdots + A_{98}|.$

Given that $A_k = \frac{k(k - 1)}{2}\cos\frac{k(k - 1)\pi}{2},$ find $|A_{19} + A_{20} + \cdots + A_{98}|.$

Respuesta

Conceptos:número triangular paridad sumatoria emparejamiento y agrupación

Nivel de dificultad: 2400

Pista pequeña:

$\frac{k(k-1)}{2}$ es un entero, así que cada coseno es $\pm 1,$ con signo que depende solo de $k \bmod 4$

$\frac{k(k-1)}{2}$ is an integer, so each cosine is $\pm 1,$ with sign depending only on $k \bmod 4$

Pista grande:

Agrupa los $80$ términos en bloques consecutivos de cuatro empezando en $k = 19;$ los números triangulares consecutivos difieren en $k,$ así que cada bloque se simplifica

Group the $80$ terms into consecutive blocks of four starting at $k = 19;$ consecutive triangular numbers differ by $k,$ so each block collapses

Solución:

Como $k(k-1)$ es par, $n_k = \frac{k(k-1)}{2}$ es un entero y $\cos\frac{k(k-1)\pi}{2}$ $= \cos(n_k \pi)$ $= (-1)^{n_k}.$ La paridad del número triangular $n_k$ depende solo de $k \bmod 4:$ es par para $k \equiv 0, 1 \pmod 4$ e impar para $k \equiv 2, 3 \pmod 4.$ Así que $A_k = n_k$ cuando $k \equiv 0, 1 \pmod 4$ y $A_k = -n_k$ cuando $k \equiv 2, 3 \pmod 4.$

Agrupa los $80$ términos en $20$ bloques consecutivos de cuatro empezando en $k = 19 \equiv 3 \pmod 4.$ Usando $n_{j+1} - n_j = j,$ cada bloque con $k \equiv 3 \pmod 4$ se simplifica: $\begin{aligned} &A_k + A_{k+1} \\ &\quad {}+ A_{k+2} + A_{k+3} \\ &= (n_{k+1} - n_k) \\ &\quad {}- (n_{k+3} - n_{k+2}) \\ &= k - (k + 2) \\ &= -2. \end{aligned}$

El total es $20 \cdot (-2) = -40,$ así que el valor absoluto pedido es $40.$

Since $k(k-1)$ is even, $n_k = \frac{k(k-1)}{2}$ is an integer and $\cos\frac{k(k-1)\pi}{2}$ $= \cos(n_k \pi)$ $= (-1)^{n_k}.$ The parity of the triangular number $n_k$ depends only on $k \bmod 4:$ it is even for $k \equiv 0, 1 \pmod 4$ and odd for $k \equiv 2, 3 \pmod 4.$ So $A_k = n_k$ when $k \equiv 0, 1 \pmod 4$ and $A_k = -n_k$ when $k \equiv 2, 3 \pmod 4.$

Group the $80$ terms into $20$ consecutive blocks of four starting at $k = 19 \equiv 3 \pmod 4.$ Using $n_{j+1} - n_j = j,$ each block with $k \equiv 3 \pmod 4$ collapses: $\begin{aligned} &A_k + A_{k+1} \\ &\quad {}+ A_{k+2} + A_{k+3} \\ &= (n_{k+1} - n_k) \\ &\quad {}- (n_{k+3} - n_{k+2}) \\ &= k - (k + 2) \\ &= -2. \end{aligned}$

The total is $20 \cdot (-2) = -40,$ so the requested absolute value is $40.$

6.

Sea $ABCD$ un paralelogramo. Prolonga $\overline{DA}$ más allá de $A$ hasta un punto $P,$ y supón que $\overline{PC}$ corta a $\overline{AB}$ en $Q$ y a $\overline{DB}$ en $R.$ Dado que $PQ = 735$ y $QR = 112,$ halla $RC.$

Let $ABCD$ be a parallelogram. Extend $\overline{DA}$ through $A$ to a point $P,$ and let $\overline{PC}$ meet $\overline{AB}$ at $Q$ and $\overline{DB}$ at $R.$ Given that $PQ = 735$ and $QR = 112,$ find $RC.$

Respuesta

Conceptos:semejanza paralelogramo cuadrática

Nivel de dificultad: 2510

Pista pequeña:

Dos pares de triángulos semejantes: $AQ \parallel DC$ da $\frac{PQ}{PC} = \frac{PA}{PD},$ y $BC \parallel PD$ da $\frac{RC}{RP} = \frac{BC}{PD}$

Two pairs of similar triangles: $AQ \parallel DC$ gives $\frac{PQ}{PC} = \frac{PA}{PD},$ and $BC \parallel PD$ gives $\frac{RC}{RP} = \frac{BC}{PD}$

Pista grande:

Con $a = \frac{PA}{AD},$ las razones dan $PQ : QR : RC$ $= a(a+2) : 1 : (a+1);$ usa $\frac{PQ}{QR} = \frac{735}{112}$ para hallar $a$

With $a = \frac{PA}{AD},$ the ratios give $PQ : QR : RC$ $= a(a+2) : 1 : (a+1);$ use $\frac{PQ}{QR} = \frac{735}{112}$ to find $a$

Solución:

Sea $a = \frac{PA}{AD}.$ Como $AQ \parallel DC,$ los triángulos $PAQ$ y $PDC$ son semejantes, así que $\frac{PQ}{PC} = \frac{PA}{PD} = \frac{a}{a+1}.$ Como $BC \parallel AD,$ es decir $BC \parallel PD,$ los triángulos $RBC$ y $RDP$ son semejantes, así que $\frac{RC}{RP} = \frac{BC}{PD} = \frac{1}{a+1},$ lo que da $\frac{RC}{PC} = \frac{1}{a+2}.$

Escribiendo $PC = L,$ obtenemos $PQ = \frac{a}{a+1}L,$ $RC = \frac{L}{a+2},$ y $\begin{aligned} QR &= L - PQ - RC \\ &= \frac{L}{(a+1)(a+2)}. \end{aligned}$ Por lo tanto $\frac{PQ}{QR} = a(a+2) = \frac{735}{112} = \frac{105}{16},$ así que $16a^2 + 32a - 105 = 0,$ que se factoriza como $(4a - 7)(4a + 15) = 0,$ dando $a = \frac{7}{4}.$

Finalmente $RC = (a + 1)\,QR$ $= \frac{11}{4} \cdot 112$ $= 308.$

Let $a = \frac{PA}{AD}.$ Since $AQ \parallel DC,$ triangles $PAQ$ and $PDC$ are similar, so $\frac{PQ}{PC} = \frac{PA}{PD} = \frac{a}{a+1}.$ Since $BC \parallel AD,$ i.e. $BC \parallel PD,$ triangles $RBC$ and $RDP$ are similar, so $\frac{RC}{RP} = \frac{BC}{PD} = \frac{1}{a+1},$ which gives $\frac{RC}{PC} = \frac{1}{a+2}.$

Writing $PC = L,$ we get $PQ = \frac{a}{a+1}L,$ $RC = \frac{L}{a+2},$ and $\begin{aligned} QR &= L - PQ - RC \\ &= \frac{L}{(a+1)(a+2)}. \end{aligned}$ Hence $\frac{PQ}{QR} = a(a+2) = \frac{735}{112} = \frac{105}{16},$ so $16a^2 + 32a - 105 = 0,$ which factors as $(4a - 7)(4a + 15) = 0,$ giving $a = \frac{7}{4}.$

Finally $RC = (a + 1)\,QR$ $= \frac{11}{4} \cdot 112$ $= 308.$

7.

Sea $n$ el número de cuádruplas ordenadas $(x_1, x_2, x_3, x_4)$ de enteros positivos impares que satisfacen $x_1 + x_2 + x_3 + x_4 = 98.$ Halla $\frac{n}{100}.$

Let $n$ be the number of ordered quadruples $(x_1, x_2, x_3, x_4)$ of positive odd integers that satisfy $x_1 + x_2 + x_3 + x_4 = 98.$ Find $\frac{n}{100}.$

Respuesta

Conceptos:estrellas y barras sustitución paridad

Nivel de dificultad: 2010

Pista pequeña:

Sustituye $x_i = 2y_i - 1$ para convertir las variables impares en enteros positivos arbitrarios

Substitute $x_i = 2y_i - 1$ to turn the odd variables into arbitrary positive integers

Pista grande:

La nueva ecuación es $y_1 + y_2 + y_3 + y_4 = 51;$ cuenta sus soluciones positivas con el método de estrellas y barras

The new equation is $y_1 + y_2 + y_3 + y_4 = 51;$ count its positive solutions with stars and bars

Solución:

Escribe $x_i = 2y_i - 1$ , donde cada $y_i$ es un entero positivo. Entonces $x_1 + x_2 + x_3 + x_4 = 98$ se vuelve $2(y_1 + y_2 + y_3 + y_4) - 4 = 98,$ así que $y_1 + y_2 + y_3 + y_4 = 51.$

Por estrellas y barras, el número de soluciones en enteros positivos es $\binom{50}{3} = 19600.$ Por lo tanto $\frac{n}{100} = 196.$

Write $x_i = 2y_i - 1$ where each $y_i$ is a positive integer. Then $x_1 + x_2 + x_3 + x_4 = 98$ becomes $2(y_1 + y_2 + y_3 + y_4) - 4 = 98,$ so $y_1 + y_2 + y_3 + y_4 = 51.$

By stars and bars, the number of solutions in positive integers is $\binom{50}{3} = 19600.$ Therefore $\frac{n}{100} = 196.$

8.

Salvo los dos primeros términos, cada término de la sucesión $1000,$ $x,$ $1000 - x,$ $\ldots$ se obtiene restando el término anterior del que le precede. El último término de la sucesión es el primer término negativo que aparece. ¿Qué entero positivo $x$ produce una sucesión de longitud máxima?

Except for the first two terms, each term of the sequence $1000,$ $x,$ $1000 - x,$ $\ldots$ is obtained by subtracting the preceding term from the one before that. The last term of the sequence is the first negative term encountered. What positive integer $x$ produces a sequence of maximum length?

Respuesta

Conceptos:Fibonacci recursión acotación a casos límite

Nivel de dificultad: 2510

Pista pequeña:

Escribe los términos: $1000 - x,$ $2x - 1000,$ $2000 - 3x,$ $5x - 3000, \ldots$ , los coeficientes son números de Fibonacci

Write out terms: $1000 - x,$ $2x - 1000,$ $2000 - 3x,$ $5x - 3000, \ldots$ — the coefficients are Fibonacci numbers

Pista grande:

Mantener no negativos los términos duodécimo y decimotercero fija $x$ entre $\frac{55000}{89}$ y $\frac{89000}{144},$ un intervalo que contiene exactamente un entero

Keeping the twelfth and thirteenth terms nonnegative pins $x$ between $\frac{55000}{89}$ and $\frac{89000}{144},$ an interval containing exactly one integer

Solución:

Calculando términos, $a_3 = 1000 - x,$ $a_4 = 2x - 1000,$ $a_5 = 2000 - 3x,$ $a_6 = 5x - 3000,$ y en general $\begin{aligned} a_{2k+1} &= 1000 F_{2k-1} - x F_{2k}, \\ a_{2k+2} &= x F_{2k+1} - 1000 F_{2k}, \end{aligned}$ donde $F_1 = F_2 = 1,$ $F_3 = 2, \ldots$ son los números de Fibonacci. La sucesión continúa exactamente mientras sus términos permanezcan no negativos, así que una sucesión larga requiere que $\frac{x}{1000}$ quede encajado entre las razones $\frac{F_{2k}}{F_{2k+1}}$ y $\frac{F_{2k-1}}{F_{2k}}$ para valores cada vez mayores de $k.$

Para que los primeros $13$ términos sean no negativos necesitamos $a_{12} = 89x - 55000 \ge 0$ y $a_{13} = 89000 - 144x \ge 0,$ es decir $617.9\ldots \le x \le 618.05\ldots,$ así que $x = 618.$ Si $x \le 617$ , la sucesión se vuelve negativa en $a_{12},$ y si $x \ge 619$ se vuelve negativa en $a_{13},$ así que cualquier otro entero da una sucesión más corta.

En efecto, $x = 618$ produce $1000, 618, 382, 236, 146,$ $90, 56, 34, 22, 12,$ $10, 2, 8, -6,$ una sucesión de $14$ términos, la máxima posible. La respuesta es $618.$

Computing terms, $a_3 = 1000 - x,$ $a_4 = 2x - 1000,$ $a_5 = 2000 - 3x,$ $a_6 = 5x - 3000,$ and in general $\begin{aligned} a_{2k+1} &= 1000 F_{2k-1} - x F_{2k}, \\ a_{2k+2} &= x F_{2k+1} - 1000 F_{2k}, \end{aligned}$ where $F_1 = F_2 = 1,$ $F_3 = 2, \ldots$ are the Fibonacci numbers. The sequence keeps going exactly as long as its terms stay nonnegative, so a long sequence requires $\frac{x}{1000}$ to be squeezed between the ratios $\frac{F_{2k}}{F_{2k+1}}$ and $\frac{F_{2k-1}}{F_{2k}}$ for larger and larger $k.$

For the first $13$ terms to be nonnegative we need $a_{12} = 89x - 55000 \ge 0$ and $a_{13} = 89000 - 144x \ge 0,$ i.e. $617.9\ldots \le x \le 618.05\ldots,$ so $x = 618.$ If $x \le 617$ the sequence turns negative by $a_{12},$ and if $x \ge 619$ it turns negative by $a_{13},$ so every other integer gives a shorter sequence.

Indeed $x = 618$ yields $1000, 618, 382, 236, 146,$ $90, 56, 34, 22, 12,$ $10, 2, 8, -6,$ a sequence of $14$ terms, the maximum possible. The answer is $618.$

9.

Dos matemáticos toman un descanso para el café cada mañana. Llegan a la cafetería de forma independiente, en momentos aleatorios entre las $9$ a.m. y las $10$ a.m., y se quedan exactamente $m$ minutos. La probabilidad de que uno de ellos llegue mientras el otro está en la cafetería es $40\%,$ y $m = a - b\sqrt{c},$ donde $a,$ $b,$ y $c$ son enteros positivos, y $c$ no es divisible por el cuadrado de ningún primo. Halla $a + b + c.$

Two mathematicians take a morning coffee break each day. They arrive at the cafeteria independently, at random times between $9$ a.m. and $10$ a.m., and stay for exactly $m$ minutes. The probability that either one arrives while the other is in the cafeteria is $40\%,$ and $m = a - b\sqrt{c},$ where $a,$ $b,$ and $c$ are positive integers, and $c$ is not divisible by the square of any prime. Find $a + b + c.$

Respuesta

Conceptos:probabilidad geométrica probabilidad complementaria

Nivel de dificultad: 2400

Pista pequeña:

Representa los dos tiempos de llegada como un punto en un cuadrado $60 \times 60$ ; se encuentran exactamente cuando $|x - y| \lt m$

Plot the two arrival times as a point in a $60 \times 60$ square; they meet exactly when $|x - y| \lt m$

Pista grande:

El complemento consta de dos triángulos rectángulos que encajan formando un cuadrado de lado $60 - m,$ así que $(60 - m)^2 = \frac{3}{5} \cdot 3600$

The complement consists of two right triangles that fit together into a square of side $60 - m,$ so $(60 - m)^2 = \frac{3}{5} \cdot 3600$

Solución:

Sean los tiempos de llegada $x$ e $y$ minutos después de las $9$ a.m., de modo que $(x, y)$ es uniforme en un cuadrado $60 \times 60$ . Las dos personas se encuentran exactamente cuando $|x - y| \lt m.$

La región de no encuentro $|x - y| \ge m$ consta de dos triángulos rectángulos con catetos $60 - m,$ con área total $(60 - m)^2.$ Encontrarse con probabilidad $40\%$ significa $(60 - m)^2 = 0.6 \cdot 3600 = 2160,$ así que $60 - m = \sqrt{2160} = 12\sqrt{15}.$

Por lo tanto $m = 60 - 12\sqrt{15},$ y $a + b + c = 60 + 12 + 15 = 87.$

Let the arrival times be $x$ and $y$ minutes after $9$ a.m., so $(x, y)$ is uniform in a $60 \times 60$ square. The two people meet exactly when $|x - y| \lt m.$

The non-meeting region $|x - y| \ge m$ consists of two right triangles with legs $60 - m,$ with total area $(60 - m)^2.$ Meeting with probability $40\%$ means $(60 - m)^2 = 0.6 \cdot 3600 = 2160,$ so $60 - m = \sqrt{2160} = 12\sqrt{15}.$

Thus $m = 60 - 12\sqrt{15},$ and $a + b + c = 60 + 12 + 15 = 87.$

10.

Ocho esferas de radio $100$ se colocan sobre una superficie plana de modo que cada esfera es tangente a otras dos y sus centros son los vértices de un octágono regular. Una novena esfera se coloca sobre la superficie plana de modo que es tangente a cada una de las otras ocho esferas. El radio de esta última esfera es $a + b\sqrt{c},$ donde $a,$ $b,$ y $c$ son enteros positivos, y $c$ no es divisible por el cuadrado de ningún primo. Halla $a + b + c.$

Eight spheres of radius $100$ are placed on a flat surface so that each sphere is tangent to two others and their centers are the vertices of a regular octagon. A ninth sphere is placed on the flat surface so that it is tangent to each of the other eight spheres. The radius of this last sphere is $a + b\sqrt{c},$ where $a,$ $b,$ and $c$ are positive integers, and $c$ is not divisible by the square of any prime. Find $a + b + c.$

Respuesta

Conceptos:esfera Geometría 3D polígono regular Teorema de Pitágoras

Nivel de dificultad: 2510

Pista pequeña:

Los ocho centros están a altura $100$ en los vértices de un octágono de lado $200;$ el noveno centro está a altura $r$ sobre el centro del octágono

All eight centers lie at height $100$ at the vertices of an octagon of side $200;$ the ninth center is at height $r$ above the octagon’s center

Pista grande:

La tangencia da $R^2 + (r - 100)^2 = (r + 100)^2,$ donde $R$ es el circunradio y $200 = 2R\sin 22.5^\circ$

Tangency gives $R^2 + (r - 100)^2 = (r + 100)^2,$ where $R$ is the circumradius and $200 = 2R\sin 22.5^\circ$

Solución:

Los ocho centros están a altura $100,$ en los vértices de un octágono regular de lado $200$ (las esferas adyacentes son tangentes). Si la novena esfera tiene radio $r,$ descansa sobre la superficie con su centro a altura $r$ directamente sobre el centro del octágono, y la tangencia con cada esfera da $\sqrt{R^2 + (r - 100)^2} = r + 100,$ donde $R$ es el circunradio del octágono. Por lo tanto $\begin{aligned} R^2 &= (r + 100)^2 - (r - 100)^2 \\ &= 400r. \end{aligned}$

Un lado de un octágono regular subtiende $45^\circ$ en el centro, así que $200 = 2R \sin 22.5^\circ$ y, usando $\sin^2 22.5^\circ = \frac{1 - \cos 45^\circ}{2} = \frac{2 - \sqrt{2}}{4},$ $\begin{aligned} R^2 &= \frac{10000}{\sin^2 22.5^\circ} \\ &= \frac{40000}{2 - \sqrt{2}} \\ &= 20000\,(2 + \sqrt{2}). \end{aligned}$

Entonces $r = \frac{R^2}{400}$ $= 50\,(2 + \sqrt{2})$ $= 100 + 50\sqrt{2},$ así que $a + b + c = 100 + 50 + 2 = 152.$

The eight centers are at height $100,$ at the vertices of a regular octagon of side $200$ (adjacent spheres are tangent). If the ninth sphere has radius $r,$ it rests on the surface with its center at height $r$ directly above the octagon’s center, and tangency to each sphere gives $\sqrt{R^2 + (r - 100)^2} = r + 100,$ where $R$ is the octagon’s circumradius. Hence $\begin{aligned} R^2 &= (r + 100)^2 - (r - 100)^2 \\ &= 400r. \end{aligned}$

A side of a regular octagon subtends $45^\circ$ at the center, so $200 = 2R \sin 22.5^\circ$ and, using $\sin^2 22.5^\circ = \frac{1 - \cos 45^\circ}{2} = \frac{2 - \sqrt{2}}{4},$ $\begin{aligned} R^2 &= \frac{10000}{\sin^2 22.5^\circ} \\ &= \frac{40000}{2 - \sqrt{2}} \\ &= 20000\,(2 + \sqrt{2}). \end{aligned}$

Then $r = \frac{R^2}{400}$ $= 50\,(2 + \sqrt{2})$ $= 100 + 50\sqrt{2},$ so $a + b + c = 100 + 50 + 2 = 152.$

11.

Tres de las aristas de un cubo son $\overline{AB},$ $\overline{BC},$ y $\overline{CD},$ y $\overline{AD}$ es una diagonal espacial. Los puntos $P,$ $Q,$ y $R$ están en $\overline{AB},$ $\overline{BC},$ y $\overline{CD},$ respectivamente, de modo que $AP = 5,$ $PB = 15,$ $BQ = 15,$ y $CR = 10.$ ¿Cuál es el área del polígono que forma la intersección del plano $PQR$ con el cubo?

Three of the edges of a cube are $\overline{AB},$ $\overline{BC},$ and $\overline{CD},$ and $\overline{AD}$ is an interior diagonal. Points $P,$ $Q,$ and $R$ are on $\overline{AB},$ $\overline{BC},$ and $\overline{CD},$ respectively, so that $AP = 5,$ $PB = 15,$ $BQ = 15,$ and $CR = 10.$ What is the area of the polygon that is the intersection of plane $PQR$ and the cube?

Respuesta

Conceptos:geometría del cubo geometría analítica fórmula del cordón

Nivel de dificultad: 2840

Pista pequeña:

Fija $B = (0,0,0),$ $A = (20,0,0),$ $C = (0,20,0),$ $D = (0,20,20),$ y halla el plano que pasa por $P,$ $Q,$ $R$

Set $B = (0,0,0),$ $A = (20,0,0),$ $C = (0,20,0),$ $D = (0,20,20),$ and find the plane through $P,$ $Q,$ $R$

Pista grande:

El plano $2x + 2y - z = 30$ corta un hexágono. Proyectar al plano $xy$ escala el área por $\frac{1}{3},$ la componente vertical del vector normal unitario.

The plane $2x + 2y - z = 30$ cuts a hexagon. Projecting to the $xy$ -plane scales area by $\frac{1}{3},$ the vertical component of the unit normal.

Solución:

El cubo tiene lado $20.$ Toma $B = (0,0,0),$ $A = (20,0,0),$ $C = (0,20,0),$ y $D = (0,20,20),$ de modo que $\overline{AD}$ es una diagonal espacial. Entonces $P = (15, 0, 0),$ $Q = (0, 15, 0),$ $R = (0, 20, 10),$ y el plano que pasa por ellos es $2x + 2y - z = 30.$

Evaluando $2x + 2y - z$ en los vértices del cubo y comprobando las doce aristas, el plano también cruza las aristas en $(5, 20, 20),$ $(20, 5, 20),$ y $(20, 0, 10),$ así que la sección transversal es el hexágono con vértices $(15,0,0),$ $(0,15,0),$ $(0,20,10),$ $(5,20,20),$ $(20,5,20),$ $(20,0,10)$ en orden. Su proyección sobre el plano $xy$ es el hexágono $(15,0),$ $(0,15),$ $(0,20),$ $(5,20),$ $(20,5),$ $(20,0),$ cuya área por la fórmula del zapatero es $175.$

El vector normal unitario del plano $\frac{1}{3}(2, 2, -1)$ tiene componente vertical de magnitud $\frac{1}{3},$ así que proyectar sobre el plano $xy$ multiplica el área por $\frac{1}{3}.$ Por lo tanto, la sección transversal tiene área $3 \cdot 175 = 525.$

The cube has side $20.$ Take $B = (0,0,0),$ $A = (20,0,0),$ $C = (0,20,0),$ and $D = (0,20,20),$ so $\overline{AD}$ is an interior diagonal. Then $P = (15, 0, 0),$ $Q = (0, 15, 0),$ $R = (0, 20, 10),$ and the plane through them is $2x + 2y - z = 30.$

Evaluating $2x + 2y - z$ at the cube’s vertices and checking all twelve edges, the plane also crosses the edges at $(5, 20, 20),$ $(20, 5, 20),$ and $(20, 0, 10),$ so the cross-section is the hexagon with vertices $(15,0,0),$ $(0,15,0),$ $(0,20,10),$ $(5,20,20),$ $(20,5,20),$ $(20,0,10)$ in order. Its projection onto the $xy$ -plane is the hexagon $(15,0),$ $(0,15),$ $(0,20),$ $(5,20),$ $(20,5),$ $(20,0),$ whose area by the shoelace formula is $175.$

The plane’s unit normal $\frac{1}{3}(2, 2, -1)$ has vertical component of magnitude $\frac{1}{3},$ so projecting onto the $xy$ -plane multiplies area by $\frac{1}{3}.$ The cross-section therefore has area $3 \cdot 175 = 525.$

12.

Sea $ABC$ un triángulo equilátero, y sean $D,$ $E,$ y $F$ los puntos medios de $\overline{BC},$ $\overline{CA},$ y $\overline{AB},$ respectivamente. Existen puntos $P,$ $Q,$ y $R$ sobre $\overline{DE},$ $\overline{EF},$ y $\overline{FD},$ respectivamente, con la propiedad de que $P$ está en $\overline{CQ},$ $Q$ está en $\overline{AR},$ y $R$ está en $\overline{BP}.$ La razón entre el área del triángulo $ABC$ y el área del triángulo $PQR$ es $a + b\sqrt{c},$ donde $a,$ $b,$ y $c$ son enteros, y $c$ no es divisible por el cuadrado de ningún primo. ¿Cuánto vale $a^2 + b^2 + c^2$ ?

Let $ABC$ be equilateral, and $D,$ $E,$ and $F$ be the midpoints of $\overline{BC},$ $\overline{CA},$ and $\overline{AB},$ respectively. There exist points $P,$ $Q,$ and $R$ on $\overline{DE},$ $\overline{EF},$ and $\overline{FD},$ respectively, with the property that $P$ is on $\overline{CQ},$ $Q$ is on $\overline{AR},$ and $R$ is on $\overline{BP}.$ The ratio of the area of triangle $ABC$ to the area of triangle $PQR$ is $a + b\sqrt{c},$ where $a,$ $b,$ and $c$ are integers, and $c$ is not divisible by the square of any prime. What is $a^2 + b^2 + c^2?$

Respuesta

Conceptos:triángulo equilátero geometría analítica razón de áreas simetría

Nivel de dificultad: 2990

Pista pequeña:

Parametriza $P,$ $Q,$ y $R$ mediante fracciones distintas $x,$ $y,$ y $z$ a lo largo de $DE,$ $EF,$ y $FD$ ; convierte las tres colinealidades en ecuaciones

Parameterize $P,$ $Q,$ and $R$ by separate fractions $x,$ $y,$ and $z$ along $DE,$ $EF,$ and $FD$ ; translate the three collinearities into equations

Pista grande:

Las ecuaciones son $x(1+y)=1,$ $y(1+z)=1,$ y $z(1+x)=1;$ demuestra que obligan a que $x=y=z,$ y luego compara las distancias al cuadrado desde el centro común de los dos triángulos equiláteros

The equations are $x(1+y)=1,$ $y(1+z)=1,$ and $z(1+x)=1;$ show they force $x=y=z,$ then compare squared distances from the common center of the two equilateral triangles

Solución:

Coloquemos $A = (0, \sqrt{3}),$ $B = (-1, 0),$ $C = (1, 0),$ de modo que $D = (0, 0),$ $E = \left(\frac{1}{2}, \frac{\sqrt{3}}{2}\right),$ $F = \left(-\frac{1}{2}, \frac{\sqrt{3}}{2}\right).$ Escribamos $P=D+x(E-D),$ $Q=E+y(F-E),$ y $R=F+z(D-F),$ donde $0\le x,y,z\le1.$ Al calcular los tres productos cruzados bidimensionales, las colinealidades $C,P,Q;$ $A,Q,R;$ y $B,R,P$ dan, respectivamente, $\begin{gathered} x(1+y)=1,\\ y(1+z)=1,\\ z(1+x)=1. \end{gathered}$

Sea $f(u)=\frac{1}{1+u}.$ Las ecuaciones dicen $x=f(y),$ $y=f(z),$ y $z=f(x),$ así que $x=f(f(f(x)))=\frac{x+2}{2x+3}.$ Por tanto, $x^2+x-1=0,$ y la positividad da $x=\frac{\sqrt5-1}{2}.$ Las ecuaciones obligan entonces a que $y=z=x;$ llamemos $t$ a este valor común. Así, la configuración buscada es realmente simétrica y no se ha supuesto que lo fuera.

Con $P = \left(\frac{t}{2}, \frac{t\sqrt{3}}{2}\right)$ y $Q = \left(\frac{1}{2} - t, \frac{\sqrt{3}}{2}\right),$ ambos triángulos son equiláteros y tienen centro $G = \left(0, \frac{\sqrt{3}}{3}\right).$ Por tanto, la razón de áreas es $\frac{GA^2}{GP^2}.$ Usando $t^2 = 1 - t,$ $\begin{aligned} GP^2 &= \frac{t^2}{4} + 3\left(\frac{t}{2} - \frac{1}{3}\right)^2 \\ &= t^2 - t + \frac{1}{3} \\ &= \frac{7}{3} - \sqrt{5}, \\ GA^2 &= \frac{4}{3}. \end{aligned}$

Por consiguiente, $\begin{aligned} \frac{[ABC]}{[PQR]} &= \frac{\frac{4}{3}}{\frac{7}{3} - \sqrt{5}} \\ &= \frac{4}{7 - 3\sqrt{5}} \\ &= 7 + 3\sqrt{5}, \end{aligned}$ así que $a = 7,$ $b = 3,$ $c = 5,$ y $a^2 + b^2 + c^2 = 49 + 9 + 25 = 83.$

Place $A = (0, \sqrt{3}),$ $B = (-1, 0),$ $C = (1, 0),$ so $D = (0, 0),$ $E = \left(\frac{1}{2}, \frac{\sqrt{3}}{2}\right),$ $F = \left(-\frac{1}{2}, \frac{\sqrt{3}}{2}\right).$ Write $P=D+x(E-D),$ $Q=E+y(F-E),$ and $R=F+z(D-F),$ where $0\le x,y,z\le1.$ Computing the three two-dimensional cross products, the collinearities $C,P,Q;$ $A,Q,R;$ and $B,R,P$ give, respectively, $\begin{gathered} x(1+y)=1,\\ y(1+z)=1,\\ z(1+x)=1. \end{gathered}$

Let $f(u)=\frac{1}{1+u}.$ The equations say $x=f(y),$ $y=f(z),$ and $z=f(x),$ so $x=f(f(f(x)))=\frac{x+2}{2x+3}.$ Hence $x^2+x-1=0,$ and positivity gives $x=\frac{\sqrt5-1}{2}.$ The equations then force $y=z=x;$ call this common value $t.$ Thus the desired configuration really is the symmetric one, rather than merely being assumed to be.

With $P = \left(\frac{t}{2}, \frac{t\sqrt{3}}{2}\right)$ and $Q = \left(\frac{1}{2} - t, \frac{\sqrt{3}}{2}\right),$ both triangles are equilateral with center $G = \left(0, \frac{\sqrt{3}}{3}\right).$ Therefore the area ratio is $\frac{GA^2}{GP^2}.$ Using $t^2 = 1 - t,$ $\begin{aligned} GP^2 &= \frac{t^2}{4} + 3\left(\frac{t}{2} - \frac{1}{3}\right)^2 \\ &= t^2 - t + \frac{1}{3} \\ &= \frac{7}{3} - \sqrt{5}, \\ GA^2 &= \frac{4}{3}. \end{aligned}$

Hence $\begin{aligned} \frac{[ABC]}{[PQR]} &= \frac{\frac{4}{3}}{\frac{7}{3} - \sqrt{5}} \\ &= \frac{4}{7 - 3\sqrt{5}} \\ &= 7 + 3\sqrt{5}, \end{aligned}$ so $a = 7,$ $b = 3,$ $c = 5,$ and $a^2 + b^2 + c^2 = 49 + 9 + 25 = 83.$

13.

Si $\{a_1, a_2, a_3, \ldots, a_n\}$ es un conjunto de números reales, indexado de modo que $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_n,$ su suma compleja de potencias se define como $a_1 i + a_2 i^2 + a_3 i^3 + \cdots + a_n i^n,$ donde $i^2 = -1.$ Sea $S_n$ la suma de las sumas complejas de potencias de todos los subconjuntos no vacíos de $\{1, 2, \ldots, n\}.$ Dado que $S_8 = -176 - 64i$ y $S_9 = p + qi,$ donde $p$ y $q$ son enteros, halla $|p| + |q|.$

If $\{a_1, a_2, a_3, \ldots, a_n\}$ is a set of real numbers, indexed so that $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_n,$ its complex power sum is defined to be $a_1 i + a_2 i^2 + a_3 i^3 + \cdots + a_n i^n,$ where $i^2 = -1.$ Let $S_n$ be the sum of the complex power sums of all nonempty subsets of $\{1, 2, \ldots, n\}.$ Given that $S_8 = -176 - 64i$ and $S_9 = p + qi,$ where $p$ and $q$ are integers, find $|p| + |q|.$

Respuesta

Conceptos:número complejo recursión teorema del binomio

Nivel de dificultad: 2920

Pista pequeña:

Divide los subconjuntos de $\{1, \ldots, 9\}$ según contengan o no $9;$ los que no tienen $9$ contribuyen $S_8$

Split the subsets of $\{1, \ldots, 9\}$ by whether they contain $9;$ those without $9$ contribute $S_8$

Pista grande:

En $T \cup \{9\},$ el elemento $9$ es siempre el mayor y añade $9i^{|T|+1};$ sumando sobre todos los $T \subseteq \{1, \ldots, 8\}$ se obtiene $9i(1+i)^8$

In $T \cup \{9\},$ the element $9$ is always largest and adds $9i^{|T|+1};$ summing over all $T \subseteq \{1, \ldots, 8\}$ gives $9i(1+i)^8$

Solución:

Divide los subconjuntos no vacíos de $\{1, \ldots, 9\}$ según contengan o no $9.$ Los que no tienen $9$ contribuyen $S_8.$ Un subconjunto que contiene $9$ es $T \cup \{9\}$ para algún $T \subseteq \{1, \ldots, 8\},$ posiblemente vacío, y como $9$ es su elemento mayor, su suma compleja de potencias es la suma compleja de potencias de $T$ más $9i^{|T| + 1}.$ Sumando sobre todos los $T$ se obtiene otro $S_8$ más $\sum_{k=0}^{8} \binom{8}{k}\, 9\, i^{k+1} = 9i\,(1 + i)^8.$

Como $(1 + i)^2 = 2i,$ obtenemos $(1 + i)^8 = (2i)^4 = 16,$ así que $\begin{aligned} S_9 &= 2S_8 + 144i \\ &= 2(-176 - 64i) + 144i \\ &= -352 + 16i. \end{aligned}$

Por lo tanto $|p| + |q| = 352 + 16 = 368.$

Split the nonempty subsets of $\{1, \ldots, 9\}$ by whether they contain $9.$ Those without $9$ contribute $S_8.$ A subset containing $9$ is $T \cup \{9\}$ for a (possibly empty) $T \subseteq \{1, \ldots, 8\},$ and since $9$ is its largest element, its complex power sum is the complex power sum of $T$ plus $9i^{|T| + 1}.$ Summing over all $T$ gives another $S_8$ plus $\sum_{k=0}^{8} \binom{8}{k}\, 9\, i^{k+1} = 9i\,(1 + i)^8.$

Since $(1 + i)^2 = 2i,$ we get $(1 + i)^8 = (2i)^4 = 16,$ so $\begin{aligned} S_9 &= 2S_8 + 144i \\ &= 2(-176 - 64i) + 144i \\ &= -352 + 16i. \end{aligned}$

Therefore $|p| + |q| = 352 + 16 = 368.$

14.

Una caja rectangular de $m \times n \times p$ tiene la mitad del volumen de una caja rectangular de $(m + 2) \times (n + 2) \times (p + 2)$ , donde $m,$ $n,$ y $p$ son enteros, y $m \le n \le p.$ ¿Cuál es el mayor valor posible de $p$ ?

An $m \times n \times p$ rectangular box has half the volume of an $(m + 2) \times (n + 2) \times (p + 2)$ rectangular box, where $m,$ $n,$ and $p$ are integers, and $m \le n \le p.$ What is the largest possible value of $p?$

Respuesta

Conceptos:Ecuación diofántica Truco de factorización favorito de Simon acotación a casos límite

Nivel de dificultad: 2740

Pista pequeña:

Reescribe la condición de volumen como $\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) = 2$ y prueba valores pequeños de $m$

Rewrite the volume condition as $\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) = 2$ and test small $m$

Pista grande:

$m = 1, 2$ son imposibles y $m \ge 4$ mantiene $p$ pequeño; para $m = 3$ la ecuación se factoriza como $(n - 10)(p - 10) = 120$

$m = 1, 2$ are impossible and $m \ge 4$ caps $p$ low; for $m = 3$ the equation factors as $(n - 10)(p - 10) = 120$

Solución:

La condición $2mnp = (m + 2)(n + 2)(p + 2)$ se reescribe como $\begin{aligned} &\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) \\ &= 2. \end{aligned}$ Si $m = 1$ , el primer factor por sí solo es $3 \gt 2,$ y si $m = 2$ es igual a $2$ mientras que los otros factores superan $1;$ ambos son imposibles. Si $m \ge 5,$ entonces como $n \ge m$ , los dos primeros factores son a lo sumo $\left(\frac{7}{5}\right)^2 = \frac{49}{25},$ lo que obliga a $1 + \frac{2}{p} \ge \frac{50}{49},$ es decir $p \le 98.$

Para $m = 4$ la ecuación se vuelve $4np = 3(n + 2)(p + 2),$ es decir $(n - 6)(p - 6) = 48,$ así que $p \le 54.$ Para $m = 3$ se vuelve $6np = 5(n + 2)(p + 2),$ es decir $np - 10n - 10p - 20 = 0,$ o $(n - 10)(p - 10) = 120.$ Ambos factores deben ser positivos (si $n, p \lt 10$ , el producto $(10 - n)(10 - p)$ es a lo sumo $49$ ), así que el mayor $p$ proviene de $n - 10 = 1:$ $n = 11$ y $p = 130.$ En efecto, $2 \cdot 3 \cdot 11 \cdot 130 = 8580$ $= 5 \cdot 13 \cdot 132.$

Como todos los demás casos dan $p \le 98,$ el mayor valor posible es $p = 130.$

The condition $2mnp = (m + 2)(n + 2)(p + 2)$ rewrites as $\begin{aligned} &\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) \\ &= 2. \end{aligned}$ If $m = 1$ the first factor alone is $3 \gt 2,$ and if $m = 2$ it equals $2$ while the other factors exceed $1;$ both are impossible. If $m \ge 5,$ then since $n \ge m$ the first two factors are at most $\left(\frac{7}{5}\right)^2 = \frac{49}{25},$ forcing $1 + \frac{2}{p} \ge \frac{50}{49},$ i.e. $p \le 98.$

For $m = 4$ the equation becomes $4np = 3(n + 2)(p + 2),$ i.e. $(n - 6)(p - 6) = 48,$ so $p \le 54.$ For $m = 3$ it becomes $6np = 5(n + 2)(p + 2),$ i.e. $np - 10n - 10p - 20 = 0,$ or $(n - 10)(p - 10) = 120.$ Both factors must be positive (if $n, p \lt 10$ the product $(10 - n)(10 - p)$ is at most $49$ ), so the largest $p$ comes from $n - 10 = 1:$ $n = 11$ and $p = 130.$ Indeed $2 \cdot 3 \cdot 11 \cdot 130 = 8580$ $= 5 \cdot 13 \cdot 132.$

Since every other case yields $p \le 98,$ the largest possible value is $p = 130.$

15.

Define una ficha de dominó como un par ordenado de enteros positivos distintos. Una secuencia propia de fichas de dominó es una lista de fichas distintas en la que la primera coordenada de cada par después del primero es igual a la segunda coordenada del par inmediatamente anterior, y en la que $(i, j)$ y $(j, i)$ no aparecen ambos para ningún $i$ ni $j.$ Sea $D_{40}$ el conjunto de todas las fichas cuyas coordenadas no superan $40.$ Halla la longitud de la secuencia propia de fichas más larga que se puede formar usando las fichas de $D_{40}.$

Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i, j)$ and $(j, i)$ do not both appear for any $i$ and $j.$ Let $D_{40}$ be the set of all dominos whose coordinates are no larger than $40.$ Find the length of the longest proper sequence of dominos that can be formed using the dominos of $D_{40}.$

Respuesta

Conceptos:teoría de grafos paridad

Nivel de dificultad: 3160

Pista pequeña:

Las fichas de dominó son las aristas del grafo completo sobre $40$ vértices, y una secuencia propia es un recorrido que no repite ninguna arista

Dominos are the edges of the complete graph on $40$ vertices, and a proper sequence is a trail — a walk repeating no edge

Pista grande:

Los $40$ vértices tienen grado impar $39,$ pero tal recorrido permite solo dos vértices de grado impar, así que algunas aristas deben quedar sin usar; aristas sin usar disjuntas corrigen las paridades

All $40$ vertices have odd degree $39,$ but a trail allows only two odd-degree vertices, so some edges must go unused; disjoint unused edges fix the parities

Solución:

Una ficha de dominó $(i, j)$ es una arista orientada del grafo completo sobre los vértices $1, \ldots, 40,$ y la regla de que $(i, j)$ y $(j, i)$ no pueden aparecer ambos significa que cada una de las $\binom{40}{2} = 780$ aristas está disponible a lo sumo una vez. Una secuencia propia es exactamente un recorrido que no repite ninguna arista. En cualquier recorrido de este tipo, todo vértice distinto de los dos extremos se entra y se sale el mismo número de veces, así que tiene grado par en el conjunto de aristas usadas.

En el grafo completo, todo vértice tiene grado impar $39,$ así que al menos $38$ vértices deben tener grado impar en el conjunto de aristas sin usar, y un grafo con $38$ vértices de grado impar tiene al menos $\frac{38}{2} = 19$ aristas. Por lo tanto, a lo sumo se pueden usar $780 - 19 = 761$ fichas de dominó.

Recíprocamente, aparta las $19$ aristas disjuntas $(3,4),$ $(5,6),$ $\ldots,$ $(39,40).$ El grafo restante es conexo y solo los vértices $1$ y $2$ tienen grado impar, así que tiene un camino euleriano que recorre las $761$ aristas restantes; orientando cada arista en la dirección del recorrido se obtiene una secuencia propia de longitud $761.$

A domino $(i, j)$ is an oriented edge of the complete graph on vertices $1, \ldots, 40,$ and the rule that $(i, j)$ and $(j, i)$ cannot both appear means each of the $\binom{40}{2} = 780$ edges is available at most once. A proper sequence is exactly a trail: a walk that repeats no edge. In any trail, every vertex other than the two endpoints is entered and left equally often, so it has even degree in the set of edges used.

In the complete graph every vertex has odd degree $39,$ so at least $38$ vertices must have odd degree in the set of unused edges, and a graph with $38$ odd-degree vertices has at least $\frac{38}{2} = 19$ edges. Hence at most $780 - 19 = 761$ dominos can be used.

Conversely, set aside the $19$ disjoint edges $(3,4),$ $(5,6),$ $\ldots,$ $(39,40).$ The remaining graph is connected and only vertices $1$ and $2$ have odd degree, so it has an Euler trail traversing all $761$ remaining edges; orienting each edge in the direction of travel gives a proper sequence of length $761.$