4
$\begingroup$

We have a strip of paper. We can cut and fold it. Allowed operations is:

1 - folding in half, when right-hand side is bent downward;

2 - folding in half, when left-hand side is bent downward;

3 - cut all in the middle, and all right-hand side placed under the left;

4 - cut all in the middle, and all left-hand side placed under the right;

Suppose we had 3 operations: first we did 1, then 3 and 2 (1,3,2). So, our strip now has 16 pages. We enumerate all pages from the top, and after that we return strip to its initial state.

Numbers on the top side of strips are: 16,1,12,5,8,9,14,3.
Numbers on the other side of strips: 4,13,10,7,6,11,2,15

So we have sequence $a_n$: 16,1,12,5,8,9,14,3,4,13,10,7,6,11,2,15 and $a_{10}$=13

Question is: After 16 operations (3,1,2,1,3,1,2,2,3,1,2,3,3,1,2,4) find $a_{1000}$-?

enter image description here

  • 1
    You write "$12$ operations", but the sequence contains $16$ operations?2012-08-02

1 Answers 1

2

$a_{1000}$ is the page number assigned to the $1000$-th of $2^{16}=65536$ pieces on the top side of the strip. The $16$-bit binary representation of $1000_{10}$ is $0000001111101000_2$, and we just need to track the folding operations with these $16$ bits determining where the desired piece goes. Its position is affected by the operations as follows: If it goes on top, the page number and the bits stay the same; if it goes on the bottom, then in case of operation $1$ or $2$ both the page number and the bits are complemented, and in case of operation $3$ or $4$ the page number increases by the total number of pages while the bits remain unchanged. The piece starts off on page $1$ of $2$, and then:

  1. operation $3$, bit $0$: left on top $\rightarrow$ page $1$ of $4$
  2. operation $1$, bit $0$: left on top $\rightarrow$ page $1$ of $8$
  3. operation $2$, bit $0$: left on bottom $\rightarrow$ page $16$ of $16$, bits complemented: $1110000010111_2$
  4. operation $1$, bit $1$: right on bottom $\rightarrow$ page $17$ of $32$, bits complemented: $001111101000_2$
  5. operation $3$, bit $0$: left on top $\rightarrow$ page $17$ of $64$
  6. operation $1$, bit $0$: left on top $\rightarrow$ page $17$ of $128$
  7. operation $2$, bit $1$: right on top $\rightarrow$ page $17$ of $256$
  8. operation $2$, bit $1$: right on top $\rightarrow$ page $17$ of $512$
  9. operation $3$, bit $1$: right on bottom $\rightarrow$ page $529$ of $1024$
  10. operation $1$, bit $1$: right on bottom $\rightarrow$ page $1520$ of $2048$, bits complemented: $010111_2$
  11. operation $2$, bit $0$: left on bottom $\rightarrow$ page $2577$ of $4096$, bits complemented: $01000_2$
  12. operation $3$, bit $0$: left on top $\rightarrow$ page $2577$ of $8192$
  13. operation $3$, bit $1$: right on bottom $\rightarrow$ page $10769$ of $16384$
  14. operation $1$, bit $0$: left on top $\rightarrow$ page $10769$ of $32768$
  15. operation $2$, bit $0$: left on bottom $\rightarrow$ page $54768$ of $65536$, bits complemented: $1_2$
  16. operation $4$, bit $1$: right on top $\rightarrow$ page $54768$ of $131072$

So unless I made a mistake, $a_{1000}=54768$.

  • 1
    I understand the main idea, thanks. I'll check it on computer.2012-08-02