Mama Penguin and Papa Penguin have 100 baby penguins. To help keep track of them all, they have written a (unique) number on each baby's belly, from 1 to 100. In preparation for dinner time, Mama Penguin put the baby penguins along the sides of their iceberg, where they will catch fish. The penguins numbered from 1 to 50 like the fish on the west side of the iceberg, and those numbered from 51 to 100 like the fish on the east side of the iceberg. However, due to a miscommunication, Mama Penguin placed the odd-numbered penguins on the west side, and the even-numbered penguins on the east side. Papa Penguin wants to sort them out, with these restrictions:
Will Papa Penguin be able to sort out all his babies, so those numbered from 1 to 50 finish on the west side, while those numbered 51-100 finish on the east side?
Did you determine if Papa Penguin can sort his Baby Penguins?
Solution
Yes, it is possible for Papa Penguin to sort all of his babies! We will present an algorithm which he can follow that is guaranteed to sort them (though it is possible that a faster algorithm exists).
Suppose we sort babies ranging from m to n, where m is odd and n is even. In the original problem, m=1 and n=100. If we can repeatedly increase m and decrease n until m=n, we will have completely sorted all the babies. Our goal is to run up through all the babies from m to n-1 and back down from n-1 to m+2, so that by the end of each up-and-down pass, the state is exactly the same as it was at the start of the pass, except with babies m and m+1 on the west side, and babies n and n-1 on the east side, so that we can then do another up-and-down pass, setting m=m+2 and n=n-2. We can repeat this process until m and n are close enough that the problem is trivial.
To do an up-and-down pass: Move baby m+2 to the east side, m+1 to the west side, m+4 to east, m+3 to west, …, n-3 to east, n-4 to west, n-1 to east, n-2 to west (this is the "up" half). At this point, babies m and m+1 are on the west (where we want them), babies n-1 and n are on the east (also where we want them), and of the babies between m+1 and n-1, the odd babies are on the east and the evens are on the west (the opposite of how they were before all the swapping). To do the "down" half, move baby n-4 to the east (this is legal since our last move was n-2 to the west), then n-5 to west, n-2 to east, n-3 to west, n-6 to east, n-7 to west, n-8 to east, n-9 to west, …, m+6 to west, m+5 to east, m+4 to west, m+3 to east, m+2 to west. After setting down baby m+2, we now have babies m, m+1, and m+2 on the west (where we want them), and babies n, n-1, and n-2 on the east (also where we want them), and of the babies between m+2 and n-2, the odds are on the west and the evens are on the east (as in the original problem). We are also in a position to move baby m+4 next, so we can now do another iteration of the up-and-down pass, setting our new boundaries to m+2 and n-2, effectively reducing the problem size by 4.
We can simply repeat this process until m=49 and n=52. At this point, we will have babies 1-49 on the west (where they should be), 52-100 on the east (also where they should be), and 51 on the west and 50 on the east. Now we just need to move 51 (our most recent baby put down was 49, so this is legal). Then move baby 50 and we have sorted all of the baby penguins.
A visual illustration of an up-and-down pass, starting with odd penguins from m through n-1 on the west, and even penguins from m+1 through n on the east:
The "up" half of one iteration:
10 circles (representing 10 penguins) are shown, divided into two rows of 5 each. The top row is labeled "west", and the bottom row is labeled "east". The first three circles in the top row (west) are labeled "m", "m+2", and "m+4". Between these three circles and the last two circles in this row is an ellipsis, indicating the omission of many more penguins. The last two circles in this row are labeled "n-3" and "n-1". On the bottom row (east), the first three circles are labeled "m+1", "m+3", and "m+5"; and the last two are labeled "n-2" and "n". Arrows indicate the movements of these circles between the two rows. An arrow labeled "first move" points from the m+2 circle to the east side; an arrow labeled "second move" points from the m+1 circle to the west side; an arrow labeled "third move" points from the m+4 circle to the east side; an arrow labeled "fourth move" points from the m+3 circle to the west side; an arrow labeled "sixth move" points from the m+5 circle to the west side; an arrow labeled "fourth-last move" points from the n-3 circle to the east side; an arrow labeled "second-last move" points from the n-1 circle to the east side; and an arrow labeled "last move" points from the n-2 circle to the west side. The arrows, circles, and text on the bottom row (east side) are colored in red to distinguish them from the black arrows, circles, and text on the top row (west side).
(Note that the 5th move is not shown, since the 5th move is to move m+6, which is somewhere in the …, to the east. Likewise, the 3rd-last move is not shown, since the 3rd-last move is to move n-4, which is in the …, to the east. All moves between the 6th move and the 4th-last move are moving penguins represented by the …'s, so they are not shown.)
The "down" half of one iteration:
14 circles (representing 14 penguins) are shown, divided into two rows of 7 each. The top row is labeled "west", and the bottom row is labeled "east". The first three circles in the top row (west) are labeled "m", "m+1", and "m+3". Between these three circles and the last four circles in this row is an ellipsis, indicating the omission of many more penguins. The last four circles in this row are labeled "n-8", "n-6", "n-4", and "n-2". On the bottom row (east), the first three circles are labeled "m+2", "m+4", and "m+6"; and the last four are labeled "n-5", "n-3", "n-1", and "n". Arrows indicate the movements of these circles between the two rows. An arrow labeled "first move" points from the n-4 circle to the east side; an arrow labeled "second move" points from the n-5 circle to the west side; an arrow labeled "third move" points from the n-2 circle to the east side; an arrow labeled "fourth move" points from the n-3 circle to the west side; an arrow labeled "fifth move" points from the n-6 circle to the east side; an arrow labeled "seventh move" points from the n-8 circle to the east side; an arrow labeled "fifth-last" points from the m+6 circle to the west side; an arrow labeled "third-last" points from the m+4 circle to the west side; an arrow labeled "second-last" points from the m+3 circle to the east side; and an arrow labeled "last move" points from the m+2 circle to the west side. The arrows, circles, and text on the bottom row (east side) are colored in red to distinguish them from the black arrows, circles, and text on the top row (west side).
(Note that the 6th move and the 4th-last move are not shown, because they are moving n-7 and m+5, respectively, which are in the …'s. All moves between the 7th move and the 5th-last move are moving penguins represented by the …'s, so they are not shown.)
State after a one full up-and-down pass:
15 circles (representing 15 penguins) are shown, divided into two rows, with 7 circles in the top row and 8 circles in the bottom row. The top row is labeled "west", and the bottom row is labeled "east". The first five circles in the top row (west) are labeled "m", "m+1", "m+2", "m+4", "m+6"; then there is an ellipsis to represent the omission of many more penguins; and then the last two circles in this row are labeled "n-5" and "n-3". The first two circles in the bottom row (east) are labeled "m+3" and "m+5"; then there is an ellipsis to represent the omission of many more penguins; and then the last six circles are labeled "n-8", "n-6", "n-4", "n-2", "n-1", and "n".