This page provides my analysis of the puzzle Will Shortz gave to NPR listeners on 2003-03-30. If you would like to subscribe to my free email list to get a synopsis of this puzzle segment each week, send a blank email to: nprpuzzle-subscribe@igc.topica.com

Here is how I described this puzzle in my synopsis:

Last Challenge (given 20030330)

This is Sam Lloyd's Shipwreck Puzzle. It appeared in 1903 in the New York American. If you have a square biscuit, you can cut it into nine smaller squares. You would make two evenly spaced horizontal cuts, and two evenly spaced vertical cuts. Like a tic-tac-toe grid (or an octothorp, hash, hatch, number sign, or pound sign, #), you would have nine small squares, all the same size. The puzzle is how can you cut the biscuit into eight (8) smaller squares? All the squares have to have the same thickness, but they don't all have to be the same size.

Here is the rendering of this same puzzle by the NPR web page:

The Current Challenge (given March 30, 2003): This week's challenge is called Sam Lloyd's Shipwreck Puzzle. Sam Lloyd is the great puzzle maker from a century ago. This one-hundred-year-old puzzle appeared in an old newspaper called the New York American in 1903. Say you have a square biscuit. If I ask you to cut it into 9 smaller squares, you'd make two evenly-spaced horizontal cuts and two evenly-spaced vertical cuts like a tic-tac-toe grid. The result will be 9 small squares all the same size. The puzzle is: How can you cut a square biscuit into exactly 8 smaller squares? All the smaller squares have to be the same thickness as the original biscuit, but they don't all have to be the same size. If you can't illustrate your answer in an email, you can simply describe how it's done.

The official answer starts with two perpendicular cuts, each one-quarter of the way in from the edge. The result is one large square, 3/4 of the original side by 3/4 of the original size, one small square, 1/4 by 1/4, and two strips, each 1/4 by 3/4. Now cut each of the strips into three equal square to get the full complement of eight squares.

Here is another possible cut I proposed:

Draw a 5x5 grid on the square. Take a 3x3 square out of a corner. Take three (3) 2x2 squares out of the ends of the remaining L shape. Break the rest into the remaining four (4) 1x1 squares.
I suspect that there are a countable infinite set of possibilities. After all, how many ways are there to add eight squares (1, 4, 9, 16, etc.) to get another square? That's how many grids you can work with.

Regrettably, I just threw out my copy of the 1903 New York American. So, I don't know why Sam Lloyd called it the Shipwreck Puzzle. I found no reference to it on the Internet, yet. If you know, please let me know. Here's what David Sobelsohn thought:

Hi Richard! Regarding the "Shipwreck Puzzle," you proposed that "there are a countable infinite set of possibilities." How long does it take to count to infinity? That explains (along with the medium of division, a biscuit) why it's called the Shipwreck Puzzle. Shipwrecked people have plenty of spare time to ponder puzzles but probably no Internet access. If they're lucky, they might have salvaged biscuits from their wrecked ship. They might also have a pressing need to decide how to divide those biscuits to make them last.

That David is so perceptive!

I received this email with another solution:

Dear Richard,

Thanks for sharing your own and others' clever answers.

I came up with yet another way, which works for almost any number of
squares (so I suspected it wasn't Will's intended answer): Cut the biscuit
into 4 equal squares. Then cut each of the 4 squares into 2 concentric
squares. For example, cut an 8" X 8" biscuit into 4 equal 4" X 4" squares.
Then cut one 2" X 2" square from the center of each of the 4 squares.
The larger squares will have square holes in them but they will still be
squares. Thus you end up with 8 smaller squares from the original
biscuit. All the best in your pro-peace efforts. -- Linda Gritz of Somerville MA

Following Linda's idea, could you just cut eight "concentric" squares from the original biscuit? Here is Linda's reply

Thanks, Richard, I'm tickled that you've added my solution to your website. I'd prefer that you not list my e-mail address, but something like "Linda Gritz" or "Linda Gritz of Somerville MA" would be fine. By the way, you couldn't just cut 8 concentric squares from the original biscuit, because the puzzle asks for 8 SMALLER squares. If you just cut 8 concentric squares, then the largest concentric square would be the same size as the original biscuit, not smaller. Be well, and thanks again for all your efforts each week. -- Linda

Here is the Visual Basic computer program I wrote to see if I could find additional solutions:

Dim bs, sumsq, sleft, sleft1, s1, s2, s3, s4, s5, s6, s7, s8 As Integer

Dim ns, x, y, tx, ty As Integer

ReDim s(8) As Integer

For bs = 3 To 21 'big side length

filesave$ = "sum8sq2.txt"

s1 = bs

For s2 = 1 To s1 'Here we cycle through all possible combinations of small square sizes, starting with the biggest one, bs.

For s3 = 1 To s2

For s4 = 1 To s3

For s5 = 1 To s4

For s6 = 1 To s5

For s7 = 1 To s6

For s8 = 1 To s7

sumsq = s1 ^ 2 + s2 ^ 2 + s3 ^ 2 + s4 ^ 2 + s5 ^ 2 + s6 ^ 2 + s7 ^ 2 + s8 ^ 2

ns = Sqr(sumsq) '"new square" side; now, check to see if it is an integer

If ns = Int(ns) Then 'It is an integer! Now see if we can find a way to tight pack the eight squares

Cls

Print ns, s1, s2, s3, s4, s5, s6, s7, s8 'Show the user our progress

ReDim sq(ns + 1, ns + 1) As Integer

s(1) = bs

s(2) = s2

s(3) = s3

s(4) = s4

s(5) = s5

s(6) = s6

s(7) = s7

s(8) = s8

For x = 0 To ns 'Reset the new array to be all false

For y = 0 To ns

sq(x, y) = False

Next y

Next x

For u = 1 To 8

For x = 0 To ns - s(u)

For y = 0 To ns - s(u)

For tx = 0 To s(u) - 1

For ty = 0 To s(u) - 1

If sq(x + tx, y + ty) Then GoTo nexty 'If any of the tested array cells are "True" then that cell is already occupied, so try the next position

Next ty

Next tx 'At this point, we found a free space for square u.

For tx = 0 To s(u) - 1

For ty = 0 To s(u) - 1

sq(x + tx, y + ty) = True 'So, we mark all its cells as occupied

Next ty

Next tx

GoTo nextu

nexty:

Next y

Next x

Cls

Print ns, s1, s2, s3, s4, s5, s6, s7, s8

Print bs, ns, u

GoTo nexts8 'If we can't find anyway to make them fit, try the next set of small square sizes

nextu:

Next u 'If we pass this line, then they all fit, so we record our results.

Open filesave$ For Append As #1

Print #1, s1, s2, s3, s4, s5, s6, s7, s8, ns ^ 2, ns

Close #1

DoEvents

End If

nexts8:

DoEvents

Next s8

Next s7

Next s6

Next s5

Next s4

Next s3

Next s2

Next bs

Close

Print "Done."

Here are the results I got from running this program, showing the side measures of the eight component squares, the sum of their squares, and the measure of the combined square (being the square root of the sum of squares):

3 1 1 1 1 1 1 1 16 4

3 2 2 2 1 1 1 1 25 5

6 2 2 2 2 2 2 2 64 8

6 4 4 4 2 2 2 2 100 10

9 3 3 3 3 3 3 3 144 12

9 6 6 6 3 3 3 3 225 15

12 4 4 4 4 4 4 4 256 16

12 8 8 8 4 4 4 4 400 20

15 5 5 5 5 5 5 5 400 20

15 10 10 10 5 5 5 5 625 25

18 6 6 6 6 6 6 6 576 24

18 12 12 12 6 6 6 6 900 30

21 7 7 7 7 7 7 7 784 28

21 14 14 14 7 7 7 7 1225 35

From this pattern, I see that all the solutions are multiples of either Sam's (3, 1, 1, 1 ...) or mine (3, 2, 2, 2, 1, 1, 1, 1). I suspected that there are only three solutions, Sam's, mine and Linda's. To get infinitely many solutions, you would need to compose some of the component squares from smaller squares. There are many solutions if you disregard the need to fit the component squares, whole, into the shape of the original square biscuit. For example, if you cut a 9x9 component square from a 10x10 biscuit, you would have 19 1x1 squares left. You could make some 2x2 squares by joining together four 1x1 squares, but that does not fit the nature of a biscuit cutting puzzle.

Here is Dan's idea for viewing the problem in three dimensions:

The words "as the original biscuit" in NPR's statement of this
week's puzzle are significant. The way you stated the problem, that all the squares merely had to have the same thickness as each other, permits the biscuit to be bisected in all three dimensions to produce 8 squares, each half as thick, half as wide, and half as long as the original. Cheers! --Dan

Now for a serious proof:

From: Steve Portnoy <portnoy@stat.uiuc.edu>

To: rrenner@igc.org

Subject: shipwreck puzzle

Date sent: Tue, 8 Apr 2003 13:45:47 -0400 (EDT)

Dear Richard,

I am fairly sure there are only the two types you presented (plus
various rearrangements of the pieces). An argument begins by noting
that a partition of the whole square also partitions all of the 4 sides. I believe I can show the following:

(1) If the largest side of any partitioning square (subsquare) exceeds 1/2, then the partition will have more than 8 squares (and so won't work). Basically, there must be at least 3 subsquares along each side (making 8 along the perimeter) and one in the middle (which can not be covered by the edge subsquares since all sides are less than 1/2).

(2) Let x be the length of the side of a subsquare whose side is 1/2 or larger. Then any solution with x > 3/4 must have more than 8 parts. Start by putting a square of side x and one of side (1-x) along one side -- this minimizes the number of subsquares. Look at the rectangles remaining and note that a rectangular area whose sides are not in the ratios 2-to-1 or 3-to-1 or 3-2 must have at least 4 subsquares -- and this will make the total number exceed 8.

(3) Similarly, and partition with 3/5 < x < 3/4 or 1/2 <= x < 3/5 must have more than 8 parts.

(4) Lastly the pieces for x = 3/5 and x = 3/4 are the ones given. There are only finitely many rearrangements.

The arguments aren't trivial, and it is easy to overlook some gap in the argument. Basically, they rely on starting with the largest subsquare and addng squares that are as large as possible subject to lying in the original square. This will provide a lower bound on the number of subsquares in the partition. I really think a formal proof can be done in only a few pages, though I haven't actually written it out.

- Steve

________________________________________________

Professor Stephen Portnoy

email: portnoy@stat.uiuc.edu

________________________________________________

If you know any other thoughts on this puzzle, please let me know.

Richard Renner

New Philadelphia, Ohio

www.taterenner.com