Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I don't understand the question. When you say "cut all in the middle" are you referring to actually cutting with scissors. If so, how could you ever return something to an initial state that's already been cut? –  Grumpy Parsnip Apr 6 '12 at 12:59
1  
Is it clear now with this image? –  Mike Apr 6 '12 at 14:07
    
Thanks for adding that. –  Grumpy Parsnip Apr 6 '12 at 16:09
1  
You write "$12$ operations", but the sequence contains $16$ operations? –  joriki Aug 2 '12 at 7:03
    
Thanks, you right. Fixed. –  Mike Aug 2 '12 at 8:07

1 Answer 1

up vote 2 down vote accepted

$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$.

share|improve this answer
1  
I understand the main idea, thanks. I'll check it on computer. –  Mike Aug 2 '12 at 9:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.