# Checker-board Problems

Question 1:

Here is a $4\times4$ black and white checker-board.

You may fold the checker-board in any direction and times.

You may cut the checker-board along a straight line once. The cut needs to proceed all the way through and cannot change directions.

What is the minimum number of folds are needed to completely separate the white and black squares?

Note - The resulting squares do not have to be all connected.

Question 2:

Consider the below $5\times5$ checker-board.

Same rules from Question 1 apply here.

What is the minimum number of folds are needed to completely separate the white and black squares?

• Do you want to minimize the sum of the number of folds and number of cuts? Also, I feel like you are asking for too much in a question (your post is too long). Either ask for the general, rectangular case directly, or just leave your 4x4 example for the time being (and perhaps, post a follow-up question later). – Matsmath Sep 23 '16 at 13:26
• Minimise the sum, yes. About the follow up question, I might reduce it, yes. – Mildwood Sep 23 '16 at 13:27
• According to Martin Gardner, it's possible with a single cut. Not sure how many folds though. – Rand al'Thor Sep 23 '16 at 13:45
• "Completely separate" as in all white squares should not have any black square on the same strip, right ? – ABcDexter Sep 23 '16 at 14:15
• Yep, no black square should be attached. – Mildwood Sep 23 '16 at 14:20

If we have only one cut:

1. Our final folded board should contain one black and one white area.
2. Every layer in an area has to be the same color.
3. Rule 2 applies to every fold we make.

The 4x4 can be done in 6 folds and 1 cut:

Fold 1

Fold 2

Folds 3 and 4

Fold 5

Fold 6

The 5x5 can be done in 8 folds and 1 cut:

Fold 1

Fold 2

Folds 3 and 4

Folds 5 and 6

Fold 7

Fold 8

• Nice method! You can say this method 'even's out the 'odd's. ;) – Mildwood Sep 24 '16 at 0:52
• @MinusReputation I've now added a solution for 5x5 as well :) – Gintas K Sep 24 '16 at 8:32

## 4x4 Board

4 cuts no fold

You can achieve that in the following way:

Cut the board vertical in the middle. Put the the two part on top of each other and cut it vertical in the middle again. Now you have 4 strips with a length of 4. Put those strips on top of each other and cut horizontal in the middle. Put the parts on top of each other and make the final cut.

That solution is optimal because

each cut can at most double the number of parts.

## 5x5 Board

and 6 cuts

Solution:

Just do it the same way as the 4x4 solution.

• I tend to believe that the last part of your reasoning -- concerning optimality -- is incorrect, as it does not take into consideration that you can fold your board. – Matsmath Sep 23 '16 at 14:21
• Okay, your answer was correct on the unedited version, but now I realise that there is an extremely simple solution (not one I intended), I've switched the questions around; I still commend you for the contribution though! – Mildwood Sep 23 '16 at 14:22
• I think putting them on top of eachother to share a cut counts as a fold – Sconibulus Sep 23 '16 at 14:24

Partial:

The 4x4 can be done in

6 folds.

Process:

1. Fold bottom right to top left.
2. Fold top right edge to meet first vertical line from left.
3. Fold bottom left edge to meet first horizontal line from top.
4. Two black squares are visible. Fold one onto the other.

5+6. Fold the last square into quarters using diagonal folds.

C. Cut the excess.

I can't prove that this is optimal.

## 4x4 board

I believe you can do the 4x4 in 6 folds, as Gintas K said, but with different folds.

Something to note is that we just have to get the lines between the squares to line up. We don't need to fold edge to edge though. We can make all the vertical lines match with 2 folds, one in the middle of the second column of squares, and one in the third.

The first fold

Folds 2-4

The same follows for the rows, we need 2 folds to line up the three horizontal lines. From there, all the lines will form a plus shape in the middle of the paper.

Diagram after fold 4

Folds 5-6

Folding twice diagonally, like from folds 5 and 6 of Gintas K's answer will let you cut once.

## 5x5 board

Since all of the folds for the 4x4 board were aligned with the grid, it is easy to extend this to other board sizes. For the 5x5, you need one extra fold for each horizontal and vertical line. So, it can be done with 8 folds.

• Your 4x4 solution is the same as greenturtle3141's, though explained much better. For 5x5, although the paper needs to get 3 parallel folds in each direction, you can achieve the three folds by folding only twice - folding in half and then folding this doubled paper once more. Therefore 5x5 can also be done in 6 folds and 1 cut. – Jaap Scherphuis Sep 24 '16 at 17:51