Sam Lloyd's Shipwreck Puzzle

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