Olimpiada China de Selección de Equipos (TST) 2001 Problema 3

3 Sea $X$ un conjunto finito de números reales. Para cualesquiera $x,x' \in X$ con $x<x'$ , definimos una función $f(x,x')$ ; entonces $f$ se denomina función de pares ordenados sobre $X$ . Para cualquier función de pares ordenados $f$ dada sobre $X$ , si existen elementos $x_1 <x_2 <\cdots<x_k$ en $X$ tales que $f(x_1 ,x_2 ) \le f(x_2 ,x_3 ) \le \cdots \le f(x_{k-1} ,x_k )$ , entonces $x_1 ,x_2 ,\cdots,x_k$ se denomina una $f$ - sucesión ascendente de longitud $k$ en $X$ . Análogamente, defina una $f$ - sucesión descendente de longitud $l$ en $X$ . Para enteros $k,l \ge 3$ , sea $h(k,l)$ el menor entero positivo tal que para cualquier conjunto $X$ de $s$ números reales y cualquier función de pares ordenados $f$ sobre $X$ , existe una $f$ - sucesión ascendente de longitud $k$ en $X$ o una $f$ - sucesión descendente de longitud $l$ en $X$ si $s \ge h(k,l)$ . Demuestre: 1. Para $k,l>3,h(k,l) \le h(k-1,l)+h(k,l-1)-1$ ; 2 . $h(k,l) \le \binom{l-2}{k+l-4} +1$ .

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados