IMO 2011 en Amsterdam – Problema nº 4

Nueva entrega de los problemas de la IMO 2011 celebrada en Amsterdam durante el mes de julio. Os dejo el enunciado del cuarto:

Sea n un entero. Se dispone de una balanza de dos platillos y de n pesas cuyos pesos son 2^0,2^1, \ldots, 2^{n-1}. Debemos colocar cada una de las n pesas en la balanza, una tras otra, de manera tal que el platillo de la derecha nunca sea más pesado que el platillo de la izquierda. En cada paso, elegimos una de las pesas que no ha sido colocada en la balanza y la colocamos ya sea en el platillo de la izquierda o en el platillo de la derecha, hasta que todas las pesas hayan sido colocadas. Determinar el número de formas en las que esto se puede hacer.

A por él.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

4 Comentarios

  1. Tengo cotas:
    Si solo pusiéramos las pesas en el platillo izquierdo, las formas posibles serían n!
    Si las pudieramos poner sin restricciones, las formas serían n!2^n
    Por la fórmula geométrica: \sum_{i=0}^{n-1} 2^i = 2^n-1
    Por lo que 2^{n-1} > \sum_{i=0}^{n-2} 2^i
    Entonces debemos poner siempre la pesa 2^{n-1} en el platillo izquierdo.
    Si la pusiéramos la primera, tendríamos (n-1)!2^{n-1}
    Esto es: (n-1)!2^{n-1} \le formas \le (n-1)!2^{n-1}*2n

    Publica una respuesta
  2. A mí el resultado me sale (2n-1)!!

    http://gaussianos.com/doble-factorial-y-subfactorial/

    😀

    Supongamos que ya hemos resuelto el problema para n-1 pesas.

    Podemos suponer que la nueva pesa es la más pesada, pero el cálculo se complica excesivamente. Es mucho más sencillo suponer que la nueva pesa, es la menos pesada, es decir, la pesa 2^0.

    Esto supone que para n-1 pesas, los pesos eran 2^1, 2^2, … 2^n, pero es fácil ver que esto no tiene ninguna importancia, porque no altera el resultado.

    Bien, dada una combinación válida para el caso de n-1 pesas, ¿de cuantas formas se puede intercalar la pesa 2^0 de modo que siga resultando en una combinación válida?

    Bueno, pues como es la menos pesada, podemos intercalar la colocación de la pesa 2^0 en cualquier posición de la combinación y en cualquier platillo, con una única excepción: si colocamos la pesa 2^0 en primer lugar, entonces debe ir al platillo de la izquierda.

    Esto quiere decir que para combinación válida para n-1 pesas, tenemos 2n-1 combinaciones válidas para n pesas.

    Para el caso de una sóla pesa, tenemos que sólo la podemos colocar de una forma.

    Si son dos pesas, según lo expuesto anteriormente serían: (2 \cdot 2-1) \cdot 1 = 3.

    Si son tres pesas, (2 \cdot 3-1) \cdot 3 \cdot 1 = 5 \cdot 3 \cdot 1 = 15.

    Si son cuatro, (2 \cdot 4-1) \cdot 5 \cdot 3 \cdot 1 = 7 \cdot 5 \cdot 3 \cdot 1 = 105.

    Y en general, lo que puse al principio: (2n-1)!!

    Publica una respuesta
  3. Perdón, aunque puse el enlace, debí aclarar que el doble factorial de n, si n es impar, es:

    n!! = n \cdot (n-2) \cdot (n-4) \cdots 7 \cdot 5 \cdot 3 \cdot 1

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Nueva entrega de los problemas de la IMO 2011 celebrada en Amsterdam durante el…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *