10

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?

Lereu
  • 424
Nimish Joshi
  • 129
  • 7
    Hint: show that the number of pieces at most doubles with each cut. – Greg Martin Nov 02 '23 at 06:28
  • 2
    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. – paw88789 Nov 02 '23 at 15:06
  • 3
    @paw88789: I also wonder about the practical aspects of unbendable ribbon! – ruakh Nov 03 '23 at 01:51

3 Answers3

14

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.

WhatsUp
  • 22,201
  • 19
  • 48
  • 4
    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. – Stevish Nov 02 '23 at 16:11
1

$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

JMP
  • 21,771
1

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)$.

Dominique
  • 2,130
  • 2
    The question says you can't fold. – JMP Nov 02 '23 at 09:20
  • I had understood you can't fold the individual squares. – Dominique Nov 02 '23 at 10:22
  • @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? – Dominique Nov 02 '23 at 10:36
  • 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. – aschepler Nov 02 '23 at 13:43
  • @aschepler: You're so right! Please improve my answer as you see fit. – Dominique Nov 02 '23 at 13:56
  • If you can fold it can always be done in 1 cut. You can always bend the Ribbon so the next place to cut aligns with the one below (e.g. always folding right between two cuts). – Falco Nov 03 '23 at 08:42
  • @Falco: There are different ways to look at this: I was looking at the "ribbon" as a group of "uncuttable" squares, connected via flexible connections (like square stone tiles, inside a "vacuum-sucked" plastic wrapping). – Dominique Nov 03 '23 at 08:48