10
$\begingroup$

My daughter has this question in her Math Club: Ann needs to cut a ribbon 1 in x 48 in into 48 1x1 squares. What is the minimal number of cuts Ann needs to make if she can stack together several pieces and cut them at once but cannot bend any piece?

She is getting 6 as the answer but she has done this with brute force. Is there a mathematical way around such questions?

$\endgroup$
3
  • 7
    $\begingroup$ Hint: show that the number of pieces at most doubles with each cut. $\endgroup$ Nov 2, 2023 at 6:28
  • 2
    $\begingroup$ I wonder about the practical aspects of this problem. How many stacked pieces can be cut simultaneously? It seems like you would have to be able to cut a stack of at least $16$ ribbons at some point. $\endgroup$
    – paw88789
    Nov 2, 2023 at 15:06
  • 3
    $\begingroup$ @paw88789: I also wonder about the practical aspects of unbendable ribbon! $\endgroup$
    – ruakh
    Nov 3, 2023 at 1:51

3 Answers 3

14
$\begingroup$

If your ribbon has length $n$ which lies between two powers of two: $2^{k - 1} < n \le 2^k$, then you need at least $k$ cuts because the "no bend" assumption implies that each cut at most doubles the number of pieces.

On the other hand if your ribbon has length equal to $2^k$, then it's pretty obvious how to cut it into $2^k$ unit pieces in $k$ cuts.

Finally if your ribbon has length $n < 2^k$, just imagine that it has an invisible part of length $(2^k - n)$ so that you can treat it as a ribbon of length $2^k$. This means that $k$ cuts are enough.

Applied to your original problem ($n = 48$) we have $2^5 < n \le 2^6$, therefore a minimum of $6$ cuts is needed.

$\endgroup$
1
  • 4
    $\begingroup$ This is a great answer. To say the "invisible part" in a different way, your first cut (assuming the length isn't a power of 2) just needs to be made so that the longer remaining piece is a power of 2. Because then when you stack the shorter piece on top of the longer piece, it doesn't matter where the end of shorter one falls (some cuts will affect it and other cuts won't). It's basically the same as the shorter one being as long as the longer one (at least in terms of how many cuts are needed). Any length from 33 - 64 will require 6 cuts. $\endgroup$
    – Stevish
    Nov 2, 2023 at 16:11
1
$\begingroup$

$48$ factors as $2^4\cdot3$, so as each factor of $2$ requires one cut to split, and the factor of $3$ requires two cuts, the answer is $6$.

As another example, $56=2^3\cdot7$, so $3$ cuts for the $2$'s and then $7\to4,3\to2,2,2,1\to1,1,1,1,1,1,1$ is another $3$ cuts for $6$ in total

$\endgroup$
3
  • 5
    $\begingroup$ Factorization doesn't help. $11$ requires $4$ cuts and $23$ requires $5$ cuts, but $11 \cdot 23 = 253$ can be done in $6$ cuts by pretending we're cutting $256$. $\endgroup$
    – aschepler
    Nov 2, 2023 at 13:57
  • 2
    $\begingroup$ @aschepler...$253$ needs $8$ cuts, not $6$. $\endgroup$
    – paw88789
    Nov 2, 2023 at 15:15
  • 1
    $\begingroup$ @paw88789 Oops, right. $\endgroup$
    – aschepler
    Nov 2, 2023 at 22:11
1
$\begingroup$

I would say the answer is $2$: just fold the ribbon in parts of $2$, so you get a "tower" of $24$ pieces of size 2x1, which you cut in the middle. Like that, you will end up with $2$ single squares and $23$ rectangles 2x1, which are currently folded (on the edges, not the squares themselves, which is forbidden). You unfold, put all those things one on another and cut in half, and you will have $48$ square pieces.

So my answer would be $2$, using a common-sense approach.

Edit, based on comment:

In case you can't fold at all, I believe that the solution would be based on the prime factorisation:

$n = \Pi_{i}(p_i^{a_i})$, where $p_i$ is the prime factor and $a_i$ the power of that prime factor.

I believe the solution would be something like:

$$f_n = \Pi_{i}(p_i-1)\max{(a_i-1,1})$$

For $48=2^4 \cdot 3^1$, this becomes:

$f_{48}=(2-1) \cdot \max(4-1,1) \cdot (3-1) \cdot \max(0,1)$

(This is most probably wrong, but I didn't know how to handle the zero, but it goes in the right direction)

Edit, based on comment of aschepler:
Apparently $f_n$ is not really based on $a_i$, but more on $\log_2(a_i)$.

$\endgroup$
7
  • 2
    $\begingroup$ The question says you can't fold. $\endgroup$
    – JMP
    Nov 2, 2023 at 9:20
  • $\begingroup$ I had understood you can't fold the individual squares. $\endgroup$
    – Dominique
    Nov 2, 2023 at 10:22
  • $\begingroup$ @JMP: you're right, I've adapted my answer but I just feel in my elbows that my "solution" for not getting zero is wrong. Do you know how to solve this? $\endgroup$
    – Dominique
    Nov 2, 2023 at 10:36
  • $\begingroup$ The factorization doesn't give the best solutions: 7 squares can be done in 3 cuts, by pretending we're cutting 8. If you are allowed to fold or bend, the answer is 1 cut. $\endgroup$
    – aschepler
    Nov 2, 2023 at 13:43
  • $\begingroup$ @aschepler: You're so right! Please improve my answer as you see fit. $\endgroup$
    – Dominique
    Nov 2, 2023 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .