Corte de varillas: solicitud de una prueba para $2^{n-1}$ formas posibles

Question

El problema del corte de la varilla establece que: Dada una varilla de longitud $n$ pulgadas y una tabla de precios $P_i$ para $i=1,\dots,n$ determinar los ingresos máximos $R_n$ .

En CLRS capítulo 15 Corte de varilla página 360:

Podemos cortar una varilla de longitud $n$ en $2^{n-1}$ diferentes maneras

Puedo entender intuitivamente por qué esto es así; básicamente podemos construir un árbol binario de altura $\log N$ . Pero, ¿alguien puede darme una prueba de por qué esto es así?

Answer 1

Una varilla de longitud $n$ puede cortarse en cualquiera de las posiciones $1$ pulgadas, $2$ pulgadas, hasta $n-1$ pulgadas. Por lo tanto, para cada forma de cortar la varilla, hay una secuencia correspondiente de $0$ s y $1$ s de longitud $n-1$ con un $1$ en el $i$ ª posición, lo que significa que la varilla se corta en esta posición y a $0$ lo que significa que no se corta.

Dado que existen $2^{n-1}$ tales secuencias, debe haber $2^{n-1}$ formas de cortar la varilla.

Answer 2

For Example:- n = 4
 --- --- --- --- 
|   |   |   |   |  --> Rod of length 4 inches
 --- --- --- ---       ^ is showing where we can make cuts
    ^   ^   ^     

Ahora, sobre una posición ^ dada, hacemos un corte o no, es decir, 0 para no hacer un corte y 1 para hacer un corte. Obtenemos $ 2^3 $ combinaciones binarias son las siguientes:

           ---     --- --- ---
1 0 0 --> |   |   |   |   |   |
           ---     --- --- ---
           --- ---     --- ---
0 1 0 --> |   |   |   |   |   |
           --- ---     --- ---
           --- --- ---     ---
1 0 0 --> |   |   |   |   |   |
           --- --- ---     ---
           ---     ---     --- ---
1 1 0 --> |   |   |   |   |   |   |
           ---     ---     --- ---
           ---     --- ---     ---
1 0 1 --> |   |   |   |   |   |   |
           ---     --- ---     ---
           --- ---     ---     ---
0 1 1 --> |   |   |   |   |   |   |
           --- ---     ---     ---
           ---     ---     ---     ---
1 1 1 --> |   |   |   |   |   |   |   |
           ---     ---     ---     ---
           --- --- --- ---
1 1 1 --> |   |   |   |   |
           --- --- --- ---

Por lo tanto, Una varilla de longitud "n" pulgadas se puede cortar en $ 2^{n-1} $ piezas.

Answer 3

Esto se puede demostrar utilizando el teorema de Binomio $(1 + x)^n$ .

$(1 + x)^n = nC_0*(x^0) + nC_1*(x^1) + nC_2*(x^2) + .... + nC_{n-1}*(x^n-1) + nC_n*(x^n)$

Número total de Cortes que se pueden realizar = $(n - 1)$ Así que.., $n ==> (n - 1)$ & $x = 1$

• 0 Corte NO CUT - $(n-1)C0$
• 1 El corte puede hacerse de diferentes maneras - $(n-1)C1$
• 2 El corte puede hacerse de diferentes maneras - $(n-1)C2$ .....

• n-1 El corte se puede hacer de diferentes maneras - $(n-1)Cn-1$

  Por lo tanto, Total de posibles formas de recortar $= (n-1)C_0 + (n-1)C_1 + (n-1)C_2 + ... + (n-1)C_{n-1}$

  Eso será igual a -> $(1 + 1)^n-1 ==> 2^(n-1)$

Por lo tanto, probado.