Doblar una tira de papel

Question

Tenemos una tira de papel. Podemos cortarla y doblarla. Las operaciones permitidas son:

1 - doblar por la mitad, cuando el lado derecho está doblado hacia abajo;

2 - doblar por la mitad, cuando el lado izquierdo está doblado hacia abajo;

3 - cortar todo en el centro, y todo el lado derecho colocado debajo del izquierdo;

4 - cortar todo en el centro, y todo el lado izquierdo colocado bajo el derecho;

Supongamos que tenemos 3 operaciones: primero hacemos 1, luego 3 y 2 (1,3,2). Entonces, nuestra tira tiene ahora 16 páginas. Enumeramos todas las páginas desde el principio, y después devolvemos la tira a su estado inicial.

Los números en la parte superior de las tiras son: 16,1,12,5,8,9,14,3.
Números en el otro lado de las tiras: 4,13,10,7,6,11,2,15

Así que tenemos la secuencia $a_n$ : 16,1,12,5,8,9,14,3,4,13,10,7,6,11,2,15 y $a_{10}$ =13

La pregunta es: Después de 16 operaciones (3,1,2,1,3,1,2,2,3,1,2,3,1,2,4) encuentre $a_{1000}$ -?

Answer 1

$a_{1000}$ es el número de página asignado al $1000$ -de $2^{16}=65536$ piezas en la parte superior de la tira. El $16$ -representación binaria de $1000_{10}$ es $0000001111101000_2$ y sólo tenemos que seguir las operaciones de plegado con estos $16$ bits que determinan dónde va la pieza deseada. Su posición se ve afectada por las operaciones de la siguiente manera: Si va en la parte superior, el número de página y los bits permanecen igual; si va en la parte inferior, entonces en caso de operación $1$ o $2$ tanto el número de página como los bits se complementan, y en caso de operación $3$ o $4$ el número de página aumenta en el número total de páginas mientras que los bits no cambian. La pieza comienza en la página $1$ de $2$ y luego:

1. operación $3$ , bit $0$ : izquierda en la parte superior $\rightarrow$ página $1$ de $4$
2. operación $1$ , bit $0$ : izquierda en la parte superior $\rightarrow$ página $1$ de $8$
3. operación $2$ , bit $0$ : a la izquierda en la parte inferior $\rightarrow$ página $16$ de $16$ , bits complementados: $1110000010111_2$
4. operación $1$ , bit $1$ : derecho en la parte inferior $\rightarrow$ página $17$ de $32$ , bits complementados: $001111101000_2$
5. operación $3$ , bit $0$ : izquierda en la parte superior $\rightarrow$ página $17$ de $64$
6. operación $1$ , bit $0$ : izquierda en la parte superior $\rightarrow$ página $17$ de $128$
7. operación $2$ , bit $1$ : justo en la parte superior $\rightarrow$ página $17$ de $256$
8. operación $2$ , bit $1$ : justo en la parte superior $\rightarrow$ página $17$ de $512$
9. operación $3$ , bit $1$ : derecho en la parte inferior $\rightarrow$ página $529$ de $1024$
10. operación $1$ , bit $1$ : derecho en la parte inferior $\rightarrow$ página $1520$ de $2048$ , bits complementados: $010111_2$
11. operación $2$ , bit $0$ : a la izquierda en la parte inferior $\rightarrow$ página $2577$ de $4096$ , bits complementados: $01000_2$
12. operación $3$ , bit $0$ : izquierda en la parte superior $\rightarrow$ página $2577$ de $8192$
13. operación $3$ , bit $1$ : derecho en la parte inferior $\rightarrow$ página $10769$ de $16384$
14. operación $1$ , bit $0$ : izquierda en la parte superior $\rightarrow$ página $10769$ de $32768$
15. operación $2$ , bit $0$ : a la izquierda en la parte inferior $\rightarrow$ página $54768$ de $65536$ , bits complementados: $1_2$
16. operación $4$ , bit $1$ : justo en la parte superior $\rightarrow$ página $54768$ de $131072$

Así que, a menos que haya cometido un error, $a_{1000}=54768$ .