PUMaC 2022 · 组合（B 组） · 第 7 题
PUMaC 2022 — Combinatorics (Division B) — Problem 7
题目详情
- An n - folding process on a rectangular piece of paper with sides aligned vertically and horizon- tally consists of repeating the following process n times: • Take the piece of paper and fold it in half vertically (choosing to either fold the right side over the left, or the left side over the right). ◦ • Rotate the paper 90 degrees clockwise. A 10-folding process is performed on a piece of paper, resulting in a 1-by-1 square base consist- ing of many stacked layers of paper. Let d ( i, j ) be the Euclidean distance between the center of the i th square from the top and the center of the j th square from the top when the paper 1023 P is unfolded. Determine the maximum possible value of d ( i, i + 1). i =1 1
解析
- An n - folding process on a rectangular piece of paper with sides aligned vertically and horizon- tally consists of repeating the following process n times: • Take the piece of paper and fold it in half vertically (choosing to either fold the right side over the left, or the left side over the right). ◦ • Rotate the paper 90 degrees clockwise. A 10-folding process is performed on a piece of paper, resulting in a 1-by-1 square base consist- ing of many stacked layers of paper. Let d ( i, j ) be the Euclidean distance between the center of the i th square from the top and the center of the j th square from the top before the paper 1023 P was folded. Determine the maximum possible value of d ( i, i + 1). i =1 Proposed by Frank Lu Answer: 14043 3 We will determine the answer by inducting on n , the index of the folding process that results in a 1-by-1 square. Let S be the answer for n , so that our answer is S . Note that S = 1 n 10 1 since we have two adjacent squares, whose centers are clearly 1 apart. It is easy to see that S = 1, as we only have one pair of consecutive labels, and they are 1 adjacent. Now, consider a piece of paper P such that, after performing a k + 1-folding process, we get a 1-by-1 square. Let Q be another piece of paper with half the size of P , so that Q is identical to the top of P after the first step in the folding process. Perform the same remaining k steps in the folding process on both P and Q , label the i th square from the top with i , then unfold P and Q k times, so that Q is completely unfolded and P is still folded once. By preserving the orientations of P and Q and placing Q directly over P , each square labeled a in Q is directly over the squares labeled 2 a − 1 and 2 a in P . Furthermore, considering consecutive squares a and a + 1 on Q , if we flip P so that squares 2 a − 1 and 2 a are on opposite halves of the fold, and squares 2 a and 2 a + 1 are on the same half of the fold. Thus, the distance between the centers of squares 2 a and 2 a + 1 in P is the same as the distance between the centers of squares a and a + 1 in Q , and the distance between the centers of squares 2 a − 1 and 2 a is twice the distance from the center of square a in Q to the edge corresponding to the fold. k +1 P 2 − 1 Note that S = d ( i, i + 1) can be split up into two sums, one for all terms where k +1 i =1 i is odd and one for all terms where i is even. The sum where i is even is just S , and the k sum where i is odd is twice the sum of the distances from all centers of squares to the edge k k ⌊ ⌋ ⌈ ⌉ 2 2 of the fold. Since Q has dimensions 2 by 2 , and the fold is the edge of Q with length k ⌊ ⌋ P k k k k k k k 2 2 2 j − 1 ⌈ ⌉ ⌈ ⌉ ⌈ ⌉ ⌊ ⌋ 2 ⌈ ⌉ +2 ⌊ ⌋ k + ⌊ ⌋ 2 2 2 2 2 2 2 2 , we have that this sum is 2 · 2 = 2 (2 ) = 2 = 2 . Thus, j =1 2 k k + ⌊ ⌋ 2 S = S + 2 . k +1 k P P P j j 9 9 4 j + ⌊ ⌋ j + ⌊ ⌋ 3 l 2 2 Starting from S = 1, we see that S = 1 + 2 = 3 + 2 = 3 + 2 + 1 10 j =1 j =2 l =1 P P 15 4 4 3 l +1 3 l 3 l 2 − 1 32767 2 = 3 + 3 2 = 3 2 . This is 3 · = 3 · = 3 · 4681 = 14043. (In 3 l =1 l =0 2 − 1 7 particular, it doesn’t matter which sides were folded over at each step, the sum is always the same!)