Question

Sean

f(n)

y

g(n)

funciones que satisfacen

\begin{aligned} &f(n) = \\ &\quad \begin{cases} \sqrt{n} & \substack{\text{si } \sqrt{n} \text{ es} \\ \text{un entero}} \\ 1 + f(n+1) & \text{en otro caso} \end{cases} \end{aligned}

y

\begin{aligned} &g(n) = \\ &\quad \begin{cases} \sqrt{n} & \substack{\text{si } \sqrt{n} \text{ es} \\ \text{un entero}} \\ 2 + g(n+2) & \text{en otro caso} \end{cases} \end{aligned}

para enteros positivos

n.

Halle el menor entero positivo

n

tal que

\frac{f(n)}{g(n)} = \frac{4}{7}.

Let

f(n)

and

g(n)

be functions satisfying

\begin{aligned} &f(n) = \\ &\quad \begin{cases} \sqrt{n} & \substack{\text{if } \sqrt{n} \text{ is} \\ \text{an integer}} \\ 1 + f(n+1) & \text{otherwise} \end{cases} \end{aligned}

and

\begin{aligned} &g(n) = \\ &\quad \begin{cases} \sqrt{n} & \substack{\text{if } \sqrt{n} \text{ is} \\ \text{an integer}} \\ 2 + g(n+2) & \text{otherwise} \end{cases} \end{aligned}

for positive integers

n.

Find the least positive integer

n

such that

\frac{f(n)}{g(n)} = \frac{4}{7}.

Respuesta

Respuesta: 258

Conceptos:función cuadrado perfecto paridad

Nivel de dificultad: 3160

Pista pequeña:

Si

k

es el menor entero con

k^2 \ge n,

entonces

f(n) = k + k^2 - n,

y

g

sube en pasos de

2

hasta el menor cuadrado de la misma paridad que

n

If

k

is the least integer with

k^2 \ge n,

then

f(n) = k + k^2 - n,

and

g

climbs by

2

s to the least square of the same parity as

n

Pista grande:

La razón difiere de

1

solo cuando

k

y

n

tienen paridad opuesta; entonces

g - f = 2k + 2,

así que

7f = 4g

obliga a

3f = 8(k + 1)

The ratio differs from

1

only when

k

and

n

have opposite parity; then

g - f = 2k + 2,

so

7f = 4g

forces

3f = 8(k + 1)

Solución:

Sea

k

el menor entero con

k^2 \ge n.

La función

f

sube de a un paso hasta el siguiente cuadrado perfecto, así que

f(n) = k + (k^2 - n).

La función

g

sube en pasos de

2

, preservando la paridad de su argumento, y

j^2 \equiv j \pmod 2,

así que

g(n) = j + (j^2 - n)

, donde

j

es el menor entero con

j^2 \ge n

y

j \equiv n \pmod 2.

Si

k \equiv n \pmod 2

, entonces

j = k

y la razón es

1;

así que necesitamos

k \not\equiv n \pmod 2,

en cuyo caso

j = k + 1

y

g(n) - f(n) = (k+1)^2 - k^2 + 1

= 2k + 2.

Entonces

7f = 4g = 4f + 4(2k + 2)

da

f = \frac{8(k+1)}{3},

así que

k \equiv 2 \pmod 3

y

n = k^2 + k - \frac{8(k+1)}{3},

sujeto a

(k-1)^2 \lt n \le k^2

y

n \not\equiv k \pmod 2.

Para

k = 2, 5, 8, 11

la fórmula da

n = -2, 14, 48, 100,

cada uno fallando

n \gt (k-1)^2;

para

k = 14,

n = 170

está en el rango pero tiene la misma paridad que

k.

Para

k = 17,

n = 289 + 17 - 48 = 258,

que satisface

256 \lt 258 \le 289

y es par mientras que

k

es impar. En efecto,

f(258) = 17 + 31 = 48

y

g(258) = 18 + 66 = 84,

con

\frac{48}{84} = \frac{4}{7},

así que el menor

n

es

258.

Let

k

be the least integer with

k^2 \ge n.

The function

f

climbs one step at a time to the next perfect square, so

f(n) = k + (k^2 - n).

The function

g

climbs by

2

s, preserving the parity of its argument, and

j^2 \equiv j \pmod 2,

so

g(n) = j + (j^2 - n)

where

j

is the least integer with

j^2 \ge n

and

j \equiv n \pmod 2.

If

k \equiv n \pmod 2

then

j = k

and the ratio is

1;

so we need

k \not\equiv n \pmod 2,

in which case

j = k + 1

and

g(n) - f(n) = (k+1)^2 - k^2 + 1

= 2k + 2.

Then

7f = 4g = 4f + 4(2k + 2)

gives

f = \frac{8(k+1)}{3},

so

k \equiv 2 \pmod 3

and

n = k^2 + k - \frac{8(k+1)}{3},

subject to

(k-1)^2 \lt n \le k^2

and

n \not\equiv k \pmod 2.

For

k = 2, 5, 8, 11

the formula gives

n = -2, 14, 48, 100,

each failing

n \gt (k-1)^2;

for

k = 14,

n = 170

is in range but has the same parity as

k.

For

k = 17,

n = 289 + 17 - 48 = 258,

which satisfies

256 \lt 258 \le 289

and is even while

k

is odd. Indeed

f(258) = 17 + 31 = 48

and

g(258) = 18 + 66 = 84,

with

\frac{48}{84} = \frac{4}{7},

so the least

n

is

258.

2021 AIME II Problema 15

Respuesta: 258

Nivel de dificultad: 3160

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años