domingo, 21 de junio de 2015

Un par de problemas de la USAMO

Van dos problemas de la USAMO:

1. Sea $S=\{1,2,\ldots,n\}$ con $n\geq 1$ un entero. Cada uno de los $2^n$ subconjuntos de $S$ se pinta rojo o azul (el subconjunto, no sus elementos). Para cualquier subconjunto $T$ de $S$ denotamos con $f(T)$ a la cantidad de subconjuntos de $T$ que son azules.

Determina el número de coloraciones que satisfacen que para cualesquiera dos subconjuntos $R$ y $T$ de $S$ tenemos que $f(R)f(T)=f(R\cup T) \cdot f(R\cap T)$.

2. Sea $\lambda$ un real en el intervalo $(0,1)$ y $A$ un multiconjunto (i.e. puede tener elementos repetidos) de enteros positivos. Sea $A_n=\{a\in A: a\leq n\}$. Supongamos que para toda $n$ el conjunto $A_n$ tiene a lo más $n\lambda$ números. Muestra que hay una infinidad de enteros $n$ para los cuales la suma de los elementos en $A_n$ es a lo más $\frac{n(n+1)}{2} \lambda$.

2 comentarios:

Juan dijo...

Esta es mi solución de AOPS que me dio flojera traducir. Nótese que la condición $\lambda < 1$ es un estorbo. Solo se necesita que no esa entero.

I prove the problem for any non-integer positive $\lambda$. Rename $a=\lambda$ because I'm lazy. So let $x_n = na - (a_1+...+a_n) \ge 0$ where $a_k$ is the number of instances of $k$, and notice $\{ x_n \} = \{ na \}$. For $n>N$, notice that

$(1+...+n)a < 1a_1+...+na_n = $
$n(a_1+...+a_n)-((a_1)+(a_1+a_2)+...+(a_1+...+a_{n-1})) $
$= n(na - x_n)-((1a-x_1)+...+((n-1)a-x_{n-1}) $
$\implies nx_n < x_1+...+x_{n-1}$.

Let $S_n=(x_1+...+x_n)/n$ and notice $S$ is decreasing for $n>N$. Since $S_n>0$ always, we have that there exists a number

$0< \nu = \displaystyle\lim_{n \rightarrow \infty} S_n$,

and $\nu < S_n$ for all $n>N$.

Now, if $a$ is irrational, then look at the interval

$\mathcal{I}=(\{ nu\}+\epsilon_1, \{ nu\} + \epsilon_2)$

where $\{nu\}+\epsilon_1 < \{ nu \}+\epsilon_2 < 1$. By Kronecker's Theorem, there are infinitely many $n$, with a "constant frequency", that satisfy $\{ na \} \in \mathcal{I}$. Now choose an $M>N$ such that $S_n < \nu + \epsilon_1$ for all $n>M$. Then, for any $n>M$ that satisfies $\{ na \} \in \mathcal{I}$, we know $x_n < S_{n-1}$ and $\{ x_n \} > \{nu\}+\epsilon_1$, and therefore there's a positive constant $C$ such that there exist $n$'s with a constant frequency $F:=|\mathcal{I}|$ (and $n>M$) such that $x_n < \nu - C$, clearly impossible since then the limit is at most $\nu - CF$ (because even the $n$'s that don't satisfy $x_n < \nu -C$ still are arbitrarily close to $\nu$.)

If $a$ is rational, then notice $x_n$ takes on a finite amount of possible values for $x_n$ and thus with a linear frequency (since $a$ is not integer), it takes a value $< \nu - C$ for some positive constant $C$, so done.

Juan dijo...

el 1 es una potencia más uno, está muy fácil, haces inducción y ya.

Publicar un comentario