# Optimizing the number of cuts for a $NxN$ square into $1x1$ squares

So today I had a square paper with McDonalds coupons on it from which you had to cut out one coupon to use it. That got me wondering, how could I cut this square paper with coupons in least number of cuts by folding the paper over such that I cut every coupon out.

So here are the rules I made.

Assume there is a $NxN$ square made out of $1x1$ squares. What is the least number of cuts you have to make to cut every $1x1$ square "out" of the bigger $NxN$ square. You can fold the square in any way you like that is physically possible in the real world.

For clarity, in this picture the square paper is $3x3$ or $N=3$ and you want to cut out the 9 little squares out. If I wasn't clear enough, please ask me to clarify more.

Certainly you can always do it in 2 cuts. First fold the coupons vertically like an accordion so that all of the vertical lines to be cut lie on top of each other. Then it only takes one vertical cut to cut all of the vertical lines. Do the same thing with the horizontal lines and make one horizontal cut.

So the real question is can we do it in one cut? We can! Make all of the horizontal and vertical accordion folds as above so that you have one horizontal and one vertical cut to make, as shown below in red. By making two diagonal folds, we can make those lines lie on top of each other and make them both with one cut.

Of course in reality the paper might get way too thick to make so many folds and cut through them, but at least in theory it is possible to cut out all of your coupons with a single cut. Note this doesn't even rely on your coupon page being $N \times N$. It could be $N \times M$ instead, and the coupons might have varying heights and widths, as long as all the cuts to be made are vertical and horizontal going across the entire page.

• Nicely done - neat method. – Mark Bennet Dec 16 '17 at 16:02

If you are allowed to fold the coupons, fold vertically concertina style so that all the vertical separations are lined up and then do the same horizontally for two cuts total.

With the example you have fold it in half vertically, which lines up the cut lines to separate the three columns of coupons.

• So if I understood you correctly, by this method you always do 4 cuts in total no matter what the size of the square is? – Ayy Lmao Dec 16 '17 at 14:33
• No, this answer shows how to do it in two cuts - one vertical and one horizontal. You can do even better, though. See my answer. – kccu Dec 16 '17 at 14:51
• @AyyLmao You can do two cuts - if you can see how this works with the example you gave - just fold it vertically in half, you should be able to see what to do. If you are only allowed to fold along existing dividing lines this method does do four cuts - you treat every other vertical and horizontal line as a main gridline so that most of your rectangle is cut into $2 \times 2$ portions and the rest is portions of these, then you stack them all up and cut them once horizontally and once vertically. – Mark Bennet Dec 16 '17 at 16:01

Bisection ... cut the coupouns in "half" and then double up ... You will need $\lceil \log_2 N \rceil^2$ cuts.

For a $4 \times 4$ coupon, cut vertically in the middle, double up, cut vertically, double up, cut horizotally in the middle, double up and finally cut.

• What do you mean by half and double up? Can you draw an example or somehow clarify? – Ayy Lmao Dec 16 '17 at 14:16
• You can do better than this because folding is allowed. – kccu Dec 16 '17 at 14:22