Question

Llamamos a una permutación

a_1,

a_2,

\ldots,

a_n

de los enteros

1,

2,

\ldots,

n

casi creciente si

a_k \le a_{k+1} + 2

para cada

1 \le k \le n - 1.

Por ejemplo,

53421

y

14253

son permutaciones casi crecientes de los enteros

1,

2,

3,

4,

5,

pero

45123

no lo es. Halla el número de permutaciones casi crecientes de los enteros

1,

2,

\ldots,

7.

Call a permutation

a_1,

a_2,

\ldots,

a_n

of the integers

1,

2,

\ldots,

n

quasi-increasing if

a_k \le a_{k+1} + 2

for each

1 \le k \le n - 1.

For example,

53421

and

14253

are quasi-increasing permutations of the integers

1,

2,

3,

4,

5,

but

45123

is not. Find the number of quasi-increasing permutations of the integers

1,

2,

\ldots,

7.

Respuesta

Respuesta: 486

Conceptos:permutaciones conteo recursivo

Nivel de dificultad: 2890

Pista pequeña:

Intenta construir una permutación casi creciente de

1, \ldots, n

insertando

n

en una permutación casi creciente de

1, \ldots, n-1

Try building a quasi-increasing permutation of

1, \ldots, n

by inserting

n

into a quasi-increasing permutation of

1, \ldots, n-1

Pista grande:

El

n

puede ir inmediatamente antes de

n-1,

inmediatamente antes de

n-2,

o al final; siempre exactamente

3

lugares, así que el conteo se triplica con cada nuevo

n

The

n

can go immediately before

n-1,

immediately before

n-2,

or at the very end — always exactly

3

places, so the count triples with each new

n

Solución:

Sea

S_n

el número de permutaciones casi crecientes de

1, \ldots, n.

Inserta

n

en una permutación casi creciente de

1, \ldots, n - 1:

la entrada que sigue a

n

debe ser al menos

n - 2,

así que

n

puede ir inmediatamente antes de

n - 1,

inmediatamente antes de

n - 2,

o al final; exactamente

3

posiciones, y cada inserción mantiene intacta cada otra condición de adyacencia.

Recíprocamente, eliminar

n

de una permutación casi creciente de

1, \ldots, n

deja una permutación casi creciente de

1, \ldots, n - 1,

ya que las entradas alrededor del

n

eliminado cumplen

a_{k-1} \le n - 1 \le a_{k+1} + 2

cuando

n \ge 3.

Así que

S_n = 3S_{n-1}

para

n \ge 3.

Como

S_2 = 2,

obtenemos

S_7 = 2 \cdot 3^5 = 486.

Let

S_n

be the number of quasi-increasing permutations of

1, \ldots, n.

Insert

n

into a quasi-increasing permutation of

1, \ldots, n - 1:

the entry following

n

must be at least

n - 2,

so

n

can go immediately before

n - 1,

immediately before

n - 2,

or at the very end — exactly

3

positions, and each insertion keeps every other adjacent condition intact.

Conversely, deleting

n

from a quasi-increasing permutation of

1, \ldots, n

leaves a quasi-increasing permutation of

1, \ldots, n - 1,

since the entries around the deleted

n

satisfy

a_{k-1} \le n - 1 \le a_{k+1} + 2

when

n \ge 3.

So

S_n = 3S_{n-1}

for

n \ge 3.

Since

S_2 = 2,

we get

S_7 = 2 \cdot 3^5 = 486.

2015 AIME II Problema 10

Respuesta: 486

Nivel de dificultad: 2890

Pista pequeña:

Pista grande:

Solución:

El Problema 10 en otros años