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.

Author: ^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 Comments

  1. Creía que lo tenía, pero me acabo de dar cuenta de que influye el orden de colocación de las pesas 🙁

    Post a Reply
  2. 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

    Post a Reply
  3. A mí el resultado me sale (2n-1)!!

    https://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)!!

    Post a Reply
  4. 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

    Post a Reply

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.

Submit a Comment

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

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.