Question

Halla el número de funciones

f

de

\{0, 1, 2, 3, 4, 5, 6\}

a los enteros tales que

f(0) = 0,

f(6) = 12,

y

\begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned}

para todo

x

e

y

en

\{0, 1, 2, 3, 4, 5, 6\}.

Find the number of functions

f

from

\{0, 1, 2, 3, 4, 5, 6\}

to the integers such that

f(0) = 0,

f(6) = 12,

and

\begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned}

for all

x

and

y

in

\{0, 1, 2, 3, 4, 5, 6\}.

Respuesta

Respuesta: 185

Conceptos:particiones y composiciones permutaciones de multiconjuntos análisis por casos acotación a casos límite

Nivel de dificultad: 3370

Pista pequeña:

Los valores consecutivos difieren en

1,

2,

o

3

en valor absoluto y las seis diferencias suman

12;

demuestra que a lo sumo una diferencia puede ser negativa

Consecutive values differ by

1,

2,

or

3

in absolute value and the six differences sum to

12;

show at most one difference can be negative

Pista grande:

Trata tres casos: sin descenso; un descenso en algún extremo; un descenso interior, que se ve forzado a ser

-1

flanqueado por dos

+3

Handle three cases: no decrease; a decrease at either end; an interior decrease, which is forced to be

-1

flanked by two

+3

s

Solución:

Sea

d_i = f(i) - f(i-1),

de modo que cada

|d_i| \in \{1, 2, 3\}

y

d_1 + \cdots + d_6 = 12.

Si

k

de las diferencias fueran negativas, la suma sería a lo sumo

3(6 - k) - k = 18 - 4k,

así que

k \le 1.

Si ninguna diferencia es negativa, las soluciones de

a + b + c = 6,

a + 2b + 3c = 12

(con

a, b, c

contando los

1

, los

2

y los

3

) son

(0,6,0),

(1,4,1),

(2,2,2),

(3,0,3),

y todos esos ordenamientos satisfacen las condiciones para cada par, lo que da

\begin{aligned} &\binom{6}{0,6,0} + \binom{6}{1,4,1} \\ &\quad {}+ \binom{6}{2,2,2} + \binom{6}{3,0,3} \\ &= 1 + 30 + 90 + 20 = 141. \end{aligned}

Si

d_1 \lt 0,

entonces

|f(2)| \ge 2

junto con

f(2) \le d_1 + 3

obliga a

d_1 = -1

y

d_2 = 3;

las cuatro diferencias restantes son positivas y suman

10,

lo que da

\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10

funciones, y el caso

d_6 \lt 0

es simétrico:

20

en total. Por último, si

d_{n+1} \lt 0

para algún

n = 1, 2, 3, 4,

las condiciones de pares

|f(n+1) - f(n-1)| \ge 2

y

|f(n+2) - f(n)| \ge 2

obligan a

d_{n+1} = -1

y

d_n = d_{n+2} = 3.

Las otras tres diferencias son positivas y suman

7,

lo que se logra con dos

3

y un

1

o con un

3

y dos

2,

cada uno en

3

órdenes:

6

maneras para cada una de las

4

posiciones, o

24

funciones.

El total es

141 + 20 + 24 = 185.

Let

d_i = f(i) - f(i-1),

so each

|d_i| \in \{1, 2, 3\}

and

d_1 + \cdots + d_6 = 12.

If

k

of the differences were negative, the sum would be at most

3(6 - k) - k = 18 - 4k,

so

k \le 1.

If no difference is negative, the solutions of

a + b + c = 6,

a + 2b + 3c = 12

(with

a, b, c

counting

1

s,

2

s,

3

s) are

(0,6,0),

(1,4,1),

(2,2,2),

(3,0,3),

and all such orderings satisfy every pair condition, giving

\begin{aligned} &\binom{6}{0,6,0} + \binom{6}{1,4,1} \\ &\quad {}+ \binom{6}{2,2,2} + \binom{6}{3,0,3} \\ &= 1 + 30 + 90 + 20 = 141. \end{aligned}

If

d_1 \lt 0,

then

|f(2)| \ge 2

with

f(2) \le d_1 + 3

forces

d_1 = -1

and

d_2 = 3;

the remaining four differences are positive and sum to

10,

giving

\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10

functions, and the case

d_6 \lt 0

is symmetric:

20

in all. Finally, if

d_{n+1} \lt 0

for some

n = 1, 2, 3, 4,

the pair conditions

|f(n+1) - f(n-1)| \ge 2

and

|f(n+2) - f(n)| \ge 2

force

d_{n+1} = -1

and

d_n = d_{n+2} = 3.

The other three differences are positive and sum to

7,

achievable as two

3

s and a

1

or a

3

and two

2

s, each in

3

orders:

6

ways for each of the

4

positions, or

24

functions.

The total is

141 + 20 + 24 = 185.

2018 AIME II Problema 15

Respuesta: 185

Nivel de dificultad: 3370

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años