Otro problema de prueba por inducción fuerte

Question

Estoy tratando de resolver el siguiente problema utilizando la prueba por inducción fuerte. el problema es:

Supongamos que una tableta de chocolate está formada por n cuadrados dispuestos en forma rectangular. La barra entera, o cualquier trozo rectangular más pequeño de la barra, puede romperse a lo largo de una línea vertical u horizontal que separa los cuadrados. Suponiendo que sólo se puede romper un trozo a la vez, determina cuántas roturas debes hacer sucesivamente para romper la barra en n cuadrados separados

Lo más lejos que he llegado es el paso de base, pero ni siquiera sé si eso es correcto

Paso base potencial que lo tengo es P(n), pero aparte de eso no tengo ni idea

Answer 1

Demostramos que una barra rectangular con $n$ plazas siempre requiere $n-1$ se rompe.

Recuerde que una "ruptura" divide un rectángulo en dos rectángulos a lo largo de las líneas de puntuación.

Para el paso de inducción, supongamos que para todo $m\lt n$ un bar con $m$ cuadrados requiere $m-1$ se rompe. Demostramos que una barra con $n$ cuadrados requiere $n-1$ se rompe.

Romper el $n$ -barra en dos rectángulos, digamos de tamaño $a$ y $b$ donde $a+b=n$ y $a\lt n$ , $b\lt n$ .

La rotura utilizada $1$ ruptura. Por el supuesto de inducción, la disección de la $a$ -rectángulo en cuadrados unitarios utilizará $a-1$ se rompe, y el $b$ -rectángulo utilizará $b-1$ descansos, para un total de $1+(a-1)+(b-1)=n-1$ .

Answer 2

Sé que esto no es una prueba por inducción, pero realmente es una buena solución al problema. Supongamos que la barra consta de n piezas. Sabemos que cada corte siempre divide un rectángulo grande en dos piezas más pequeñas, creando así exactamente una nueva pieza con cada corte. Como empezamos con 1 barra grande y queremos n trozos, tenemos que romper la barra exactamente n-1 veces.

Answer 3

Para n=1, necesitamos 0 ruptura. Para n=2, necesitamos 1 pausa. Para n=3, necesitamos 2 pausas. Así que digamos que para n=j, es cierto y necesitamos j-1 pausas y es cierto para todo j>0&& j<=k. Así que una barra de k + 1 plazas se puede romper en 2 rectángulos con cuadrados < k , lo que ya es cierto. Por lo tanto demostrado.