wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Strip Teez
        
(Message started by: rloginunix on Aug 5^th, 2016, 9:24am)

Title: Strip Teez
Post by rloginunix on Aug 5^th, 2016, 9:24am

Strip Teez

A strip of paper 2ⁿ sequentially numbered unit squares long is placed on a table along the OX axis in such a way that its left-most square, numbered as 1, is fixed at origin in the XOY plane.

The strip then undergoes n like transformations as follows:

- the strip is folded in half upward in such a way that its current right-most square is rotated counterclockwise 180 degrees in the ZOX plane about the current strip's middle until it is placed on top of the strip's left-most square

After the n-th fold is complete, the strip is one square-long along the OX axis with 2ⁿ squares piled one on top of the other along the OZ axis*:

- if n = 1 fold is performed then the initial length of the strip is 2¹ and at the end of the transformation the distribution of numbers in the vertical direction is:

1 2

- if n = 2 folds are performed then the initial length of the strip is 2² and at the end of the transformation the distribution of numbers in the vertical direction is:

1 4 3 2

- for n = 3 folds:

1 8 5 4 3 6 7 2

- for n = 4 folds:

1 16 9 8 5 12 13 4 3 14 11 6 7 10 15 2

- for n = 5 folds:

1 32 17 ...

and so on.

- what type(s) of toy model emulating the actual folding process can be thought of?

- given a square in the original strip numbered with the current year, what will its position be in the folded strip after 30 folds are performed?

The actual answer to the last question is, of course, irrelevant - the idea here is to devise a way to compute the new position of an arbitrary number after an arbitrary number of foldings very fast - without modelling the actual folding process.

* A way to obtain the new sequence of numbers: holding the folded strip by its 'book' end, cut all the forward facing folds, thumb through the 'pages' to reveal their numbers.

PS
Conversely, the problem may be stated as follows: if the squares in the folded strip are numbered sequentially, from 1, what will the sequence of these numbers be when the strip is unfolded or, conversely, how the squares in the folded strip should be numbered so that after unfolding the strip they are sequential, etc.

Title: Re: Strip Teez
Post by Grimbal on Aug 19^th, 2016, 9:32am

[hide]Use 0-based numbering.
Take number X, write it in binary, reverse the order of the n digits, left-shift, if X is odd reverse all digits (0's become 1 and 1's become 0), convert to decimal.[/hide]

For example:
[hide]1 16 9 8 5 12 13 4 3 14 11 6 7 10 15 2
12th number:
0-based it is 11
in binary: 1011
reversed: 1101
left-shifted: 1010
not'd (11 is odd): 0101
That is 5 (0-based) or 6 (1-based).
[/hide]
The 12th number is 6, the 6th number is 12.

[edit] made meaning of 'reversed' less ambiguous [/edit]

Title: Re: Strip Teez
Post by rloginunix on Aug 20^th, 2016, 8:34am

That's right.

Purely for terminology sake:

[hide]reversing the digits = reversing the order (of digits) = geometrically rotating the binary digits about the (vertical) axis of the bit-pattern's symmetry, abcd -> dcba[/hide]

[hide]not'ting the digits = flipping the binary value of each digit to its binary counterpart = applying the C's one's complement operator ~[/hide]

(my order was: [hide]left shift, ~ if odd, reverse[/hide], six of one or half a dozen)

Title: Re: Strip Teez
Post by Grimbal on Aug 21^st, 2016, 8:06am

I forgot to mention the surprising thing that that [hide] to reverse the transformation, just apply the process again[/hide]. Yet another meaning of reverse.

Title: Re: Strip Teez
Post by towr on Aug 21^st, 2016, 1:06pm

It's not really surprising if you swap the x and y axis.

Title: Re: Strip Teez
Post by Grimbal on Aug 22^nd, 2016, 1:44am

Indeed, that explains it. (It is X and Z actually).

But now all the magic has gone. Thanks, towr! :P

Title: Re: Strip Teez
Post by towr on Aug 22^nd, 2016, 12:57pm

I wonder if it would work well as a sort of obfuscation/encryption like rot13. The necessary padding is a bit of a downside, though.

Title: Re: Strip Teez
Post by rloginunix on Aug 23^rd, 2016, 8:09am

Should work - upper case-trailing six characters are all printable: left square bracket [, backslash \, right square bracket ], caret ^, underscore _ and back tick `.

Another interesting thing I noticed about this transformation: [hide]stationary points[/hide].

For example, for towr-suggested 5-fold obfuscator: [hide]1-based: 8, 12, 13, 19, 22, 26, 31[/hide]

6-fold: [hide]9, 21, 29, 35, 43, 55, 63[/hide]

7-fold: [hide]16, 24, 25, 37, 44, 52, 61, 67, 78, 86, 91, 103, 106, 114, 127[/hide]

etc. Feels like some weird [hide]cosine[/hide] is waving through.

Title: Re: Strip Teez
Post by rloginunix on Aug 23^rd, 2016, 9:16am

HILL] []^LP

KTEF ^KLIS

Title: Re: Strip Teez
Post by Grimbal on Aug 24^th, 2016, 8:34am

I thought of scrambling the letters (anagram-like). That would require a length of a power of 2. Or padding to such a length.

Instead of padding, you could cut the text in parts that are powers of 2 long. (How this can be achieved is left as an exercise to the reader).

rloginunix proposed instead the encoding of each letter. I.e. use the scrambling not on the text, but on the alphabet to create a substitution table.

For that case, you could also use the 64 characters of base 64 encoding: A-Z, a-z, 0-9, +, /.

Title: Re: Strip Teez
Post by rloginunix on Aug 24^th, 2016, 9:25am

on 08/24/16 at 08:34:54, Grimbal wrote:

Instead of padding, you could cut the text in parts that are powers of 2 long

Beautiful: [hide]any (natural) number is representable as a sum of powers of 2; then it can be done left-to-right or vice versa[/hide]

(how do we encode a 0-length string though?)