¿Cuántos cuadrados en un rectángulo?

Question

Casi lo deseo yo nunca había pensado en este problema... me estaba tirando de los pelos durante toda la noche.

Supongamos que tenemos un rectángulo con longitudes de lado $a$ y $b$, $a,b \in \mathbb Z$, $GCD(a,b)=1$, y $b \gt a$. Quiero pack de plazas en este rectángulo de tal manera que, en cada paso, tengo un pack cuadrados que es grande como sea posible en ese paso, y que toca a la plaza metí en el último paso. Una plaza de embalaje de este tipo podría terminar buscando algo como esto:

Mi pregunta es esta: ¿puedo encontrar una fórmula para el número de plazas necesario para embalar en un rectángulo en términos de las longitudes de los lados $a$$b$?

Aquí es lo que he intentado:

En primer lugar me deje $f(a,b)$ denotar la función cuya salida es el número de plazas requeridas. En primer lugar, he tomado nota de algunas propiedades de $f(a,b)$: $$f(a,a)=1$$ $$f(ka,kb)=f(a,b)$$ $$f(a,a+1)=a+1$$ $$f(a,b)=\Big\lfloor \frac{a}{b} \Big\rfloor + f(b, a\mod b)$$ $$r \lt a \implies f(a,qa+r)=q+f(r,a)$$ A continuación he intentado esto: me decidí a dejar $b=q_1a+r_1$ donde $r_1 \lt a$. Entonces tendría $$f(a, q_1a+r_1)=q_1+f(r_1, a)$$ Entonces me decidí a dejar $a=q_2r_1+r_2$, por lo que tendríamos $$f(a, q_1a+r_1)=q_1+f(r_1, q_2r_1+r_2)$$ $$f(a, q_1a+r_1)=q_1+q_2+f(r_2, r_1)$$ y así sucesivamente. Puedo continuar este proceso hasta que me golpeó algunos $n$ que $r_n=0$, y voy a tener $$f(a, q_1a+r_1)=\sum_{i=1}^n q_i$$ ...y entonces me quedé atrapado. ¿Cómo puedo encontrar cada una de las $q_i$s? Alguien, por favor ayuda! La solución no tiene que ser de forma cerrada, sólo se necesita ser... algo. Sólo tengo ni idea de dónde ir con esto.

Gracias por cualquier ayuda!

Answer 1

$$f(a,b) = \begin{cases}1 & a= b\\b/a & (\gcd(a,b) = a) ∧ (a\neq b)\\ a/b & (\gcd(a,b) = b) ∧ (a\neq b) \\ f(b,a) & b>a\\ \frac{(a-(a \mod b))}{b} + f(b,(a\mod b)) &a>b\end{cases}$$

$$\gcd(x,y) =\begin{cases}x&x=y\\y & (x = 0)∧(x\neq y)\\x & (y=0)∧(x\neq y)\\\gcd(y,(x\mod y))&x>y\\\gcd((y\mod x),x)&y> x\end{cases}$$

(∧: AND logical operator)

$ f (a, b)$ is the function that solves your question, using $ \ gcd (x, y)$, Euclid's GCD function.

Here's also the code written in Swift that does the same thing:

import Foundation
func ourFunction (_ a: Int, _ b: Int) -> Int{
    if gcd(a,b) == a{
        return b/a
    }else if gcd(a,b) == b{
        return a/b
    }
    if b>a{
        // Force a to be bigger than b
        return ourFunction(b,a)
    }
    return (a-(a%b)) / b /*big squares*/ + ourFunction(b,a%b)
}

func gcd(_ x:Int, _ y:Int) -> Int{
    if x == 0 || x == y{
        return y
    }
    if y == 0{
        return x
    }
    if x > y{
        return gcd(y,x%y)
    }else{
        return gcd(y%x,x)
    }
}
print(ourFunction(8,3))

It can be run here, just change the $ 8$ and $ 3 $ a los números que desea poner en la función.

Answer 2

La respuesta por @MCCCS es grande, pero puedo ofrecer una respuesta alternativa con la intención de ser (un poco) más concisa.

El problema se puede resolver de forma recursiva mediante la incorporación como muchos de igual tamaño máximo de plazas como sea posible dentro del rectángulo y aumentar un contador con el número de plazas incrustado. Usted va a terminar con un pequeño rectángulo, por el que se puede incrustar otro (horizontal o vertical) de la pila de igual tamaño máximo de plazas como sea posible. Enjuaga y repite el proceso!

Este proceso recursivo puede ser descrito por la siguiente función recursiva:

$$f(a, b) = \begin{cases} 0 &\mbox{if } a =0 \lor b=0 \\ f(a, b-a\cdot\left \lfloor \frac{b}{a} \right \rfloor) + \left \lfloor \frac{b}{a} \right \rfloor & \mbox{if } a<b \\ f(a-b \cdot \left \lfloor \frac{a}{b} \right \rfloor, b) + \left \lfloor \frac{a}{b} \right \rfloor & \text{otherwise} \end{casos}$$

whose domain is $\{\forall(a,b)\in \mathbb{R}^2:\gcd(a,b)=1\}$.

Aquí es un C-programa de ejecución de la función descrita anteriormente:

#include <stdio.h>

int f(int w, int h) {
    return  w == 0 || h == 0 ? 0 :
            w < h ? f(w, h-w*(h/w)) + h/w :
            f(w-h*(w/h), h) + w/h;
}

int main(int argc, char** argv) {
    int i = 3, j = 7;
    printf("f(%i, %i)=%i\n", i, j, f(i, j));
    return 0;
}