Problem:
A long thin strip of paper is units in length, unit in width, and is divided into unit squares. The paper is folded in half repeatedly. For the first fold, the right end of the paper is folded over to coincide with and lie on top of the left end. The result is a by strip of double thickness. Next, the right end of this strip is folded over to coincide with and lie on top of the left end, resulting in a by strip of quadruple thickness. This process is repeated more times. After the last fold, the strip has become a stack of unit squares. How many of these squares lie below the square that was originally the nd square counting from the left?
Solution:
Number the squares from left to right, starting with for the leftmost square, and ending with for the rightmost square. The nd square is thus initially numbered . Represent the position of a square after folds as an ordered triple , where is the position of the square starting from the left, starting with as the leftmost position, is the number of paper levels below the square, and is the number of folds that have been made. For example, the ordered triple that initially describes square number is . The first indicates that at the start there are no squares under this one, and the second indicates that no folds have been made.
Note that the function , defined below, describes the position of a square after folds:
The top line in the definition indicates that squares on the left half of the strip do not change their position or height as a result of a fold. The second line indicates that, as a result of a fold, the position of a square on the right half of the strip is reflected about the center line of the strip, and that the stack of squares in that position is inverted and placed on the top of the stack that was already in that position's reflection.
Because of the powers of in the definition of , evaluating can be made easier if the position and height are expressed in base two. In particular, after folds, the strip has length , so the positions through are represented by all possible binary strings of digits. In this representation, if and only if the leading digit is , and if and only if the leading digit is . In the former case, the new position, now represented by the string of length , is obtained by deleting the leading . In the latter case, the new position is obtained by truncating the leading and for the remaining digits, changing each to a and each to a . Likewise, in this latter case, the new height is . When , the new height is obtained in the case by taking the -digit binary string representing the height, changing each to a and each to a , and then appending a on the left. In the case , the new -digit string representing the new height is obtained by appending a to the left of the string.
With these conditions, square number is initially described by . In the display below, an arrow is used to denote an application of . For the first fold
indicating that after the first fold, square is in position , and there is one layer under this square. Continue to obtain . After folds, the number of layers under square is .
If a square is to the left of the center after folds, its positions counting from the left and the bottom do not change after folds. Otherwise, its positions counting from the right and bottom after folds become its positions counting from the left and top after folds. Also, after folds the sum of the positions of each square counting from the left and right is , and the sum of the positions counting from the bottom and top is . The position of the nd square can be described in the table below.
Thus there are squares below the final position of the nd square.
The problems on this page are the property of the MAA's American Mathematics Competitions