5
$\begingroup$

I almost wish I'd never thought of this problem... I was tearing my hair out over it all night.

Suppose we have a rectangle with side lengths $a$ and $b$, $a,b \in \mathbb Z$, $GCD(a,b)=1$, and $b \gt a$. I want to pack squares in this rectangle in such a way that, at each step, I pack a squares that is large as possible at that step, and that touches the square I packed at the last step. A square packing of this type might end up looking something like this:

enter image description here

My question is this: can I find a formula for the number of squares needed to pack a rectangle in terms of its side lengths $a$ and $b$?

Here is what I tried:

First I let $f(a,b)$ denote the function whose output is the number of squares required. First, I noted a few properties of $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)$$ Next I tried this: I decided to let $b=q_1a+r_1$ where $r_1 \lt a$. Then I would have $$f(a, q_1a+r_1)=q_1+f(r_1, a)$$ Then I decided to let $a=q_2r_1+r_2$, so that we would then have $$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)$$ and so on. I keep continuing this process until I hit some $n$ for which $r_n=0$, and I will have $$f(a, q_1a+r_1)=\sum_{i=1}^n q_i$$ ...and then I got stuck. How can I find each of the $q_i$s? Somebody, please help! The solution need not be closed-form, it just needs to be... something. I just have no idea where to go with this.

Thanks for any and all help!

$\endgroup$
  • 3
    $\begingroup$ I think the Euclidean algorithm might be helpful here $\endgroup$ – abiessu May 31 '17 at 13:27
  • 1
    $\begingroup$ I also do believe that the Euclidian algorithm is the clue here: imagine that a=10 and b=54, then you get following steps : 54=5x10+4, 10=2x4+2, 4=2x2. Now you take the sum of all coefficients: 5+2+2=9, which is, in my opinion, the number you're looking for. Isn't it? $\endgroup$ – Dominique May 31 '17 at 13:34
  • $\begingroup$ @MCCCS Whoa there... how did you come up with that? Do you mind posting an answer and explaining it? $\endgroup$ – Franklin Pezzuti Dyer May 31 '17 at 13:35
  • $\begingroup$ @Dominique Yes, that is correct. How do I find the sum of the coefficients, though? $\endgroup$ – Franklin Pezzuti Dyer May 31 '17 at 13:37
  • 1
    $\begingroup$ @IvanNeretin: I don't think so neither: you should write the Euclidean algorithm in a form of iterative series (working with Qn for the quotients and Rn for the leftovers), and perform a Sum(Qn) at the end. $\endgroup$ – Dominique May 31 '17 at 13:45
5
$\begingroup$

$$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$ to the numbers you want to put into the function.

$\endgroup$
3
$\begingroup$

The answer by @MCCCS is great, but I provide an alternative answer with intent of being (slightly) more concise.

The problem can be solved recursively by embedding as many equally-sized maximal squares as possible within the rectangle and increasing a counter by the number of squares embedded. You'll end up with a smaller rectangle, for which you can embed another (horizontal or vertical) stack of equally-sized maximal squares as possible. Rinse repeat!

This recursive process can be described by the following recursive function:

$$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{cases}$$

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

Here is a C-program implementing the function described above:

#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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.