wu :: forums « wu :: forums - Strip Teez » Welcome, Guest. Please Login or Register. Sep 12th, 2024, 11:11am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Icarus, towr, SMQ, Eigenray, Grimbal, ThudnBlunder, william wu)    Strip Teez « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Strip Teez  (Read 2847 times)
Uberpuzzler

Posts: 1029
 Strip Teez   « on: Aug 5th, 2016, 9:24am » Quote Modify

Strip Teez

A strip of paper 2n 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 2n 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 21 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 22 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.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Strip Teez   « Reply #1 on: Aug 19th, 2016, 9:32am » Quote Modify

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.

For example:
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).

The 12th number is 6, the 6th number is 12.

 made meaning of 'reversed' less ambiguous [/edit]
 « Last Edit: Aug 21st, 2016, 8:01am by Grimbal » IP Logged
Uberpuzzler

Posts: 1029
 Re: Strip Teez   « Reply #2 on: Aug 20th, 2016, 8:34am » Quote Modify

That's right.

Purely for terminology sake:

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

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

(my order was: left shift, ~ if odd, reverse, six of one or half a dozen)
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Strip Teez   « Reply #3 on: Aug 21st, 2016, 8:06am » Quote Modify

I forgot to mention the surprising thing that that to reverse the transformation, just apply the process again.  Yet another meaning of reverse.
 « Last Edit: Aug 21st, 2016, 8:07am by Grimbal » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Strip Teez   « Reply #4 on: Aug 21st, 2016, 1:06pm » Quote Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Strip Teez   « Reply #5 on: Aug 22nd, 2016, 1:44am » Quote Modify

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

But now all the magic has gone.  Thanks, towr!
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Strip Teez   « Reply #6 on: Aug 22nd, 2016, 12:57pm » Quote Modify

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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Uberpuzzler

Posts: 1029
 Re: Strip Teez   « Reply #7 on: Aug 23rd, 2016, 8:09am » Quote Modify

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

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

6-fold: 9, 21, 29, 35, 43, 55, 63

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

etc. Feels like some weird cosine is waving through.
 IP Logged
Uberpuzzler

Posts: 1029
 Re: Strip Teez   « Reply #8 on: Aug 23rd, 2016, 9:16am » Quote Modify

HILL] []^LP

KTEF ^KLIS
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Strip Teez   « Reply #9 on: Aug 24th, 2016, 8:34am » Quote Modify

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, +, /.
 IP Logged
Uberpuzzler

Posts: 1029
 Re: Strip Teez   « Reply #10 on: Aug 24th, 2016, 9:25am » Quote Modify

on Aug 24th, 2016, 8:34am, Grimbal wrote:
 Instead of padding, you could cut the text in parts that are powers of 2 long

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

(how do we encode a 0-length string though?)
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »