ARML Scrimmage Power Question

As expected, the only really interesting part of the scrimmage was the “power question”. This is basically a proof-based problem the whole team of 15 (or so) works on for an hour. This was always what I was best at, and tonight’s was no exception. I’ll post the question here for you to chew on. I’m restating it somewhat for this forum. You can ask for clarifications in the comments, but I’d rather you not post solutions since I intend to come back to it in a week to give my own (cleaned-up) solutions.

I didn’t write them all the answers out myself, but I could have done within the hour if I didn’t have to write them out longhand. I also give credit to more fastidious members of the team reviewing some of my answers and writing them out in the actual competition.

This problem is concerned with “arrangements” of “bits”. A bit is just a symbol in one of two states: ${}0$ or $1$ . A configuration is a string of bits, considered to loop around from one end to the other. Actually the problem is written in terms of bits arranged around a circle, but I’ll just write them as strings to avoid having to draw circular configurations here.

We’re interested in the following transformation on arrangements: a string $a_1a_2...a_n$ becomes the string $b_1b_2...b_n$ , where $b_i=1$ if $a_i\neq a_{i+1}$ and $b_i=0$ if $a_i=a_{i+1}$ . Since we’re considering the strings to loop around, we have $b_n=1$ if $a_n\neq a_1$ and $b_n=0$ if $a_n=a_0$ . As an example, the string $1000$ becomes the string $1001$ .

Part I
1. What arrangements are created by starting with $1001$ and transforming it one, two, three, and four times?
2. Show the first 4 transformations of $100$ .
3. Justify why $100$ will never become all zeroes no matter how many transformations are applied.

Part II
4. Show that any arrangement of two bits becomes all zeroes within two transformations.
5. Let $a_ia_{i+1}a_{i+2}$ be any three consecutive bits in an arrangement, which may have any number of other bits (these three may also wrap from the end of a string to the beginning). Show that transforming the arrangements twice gives a ${}0$ or $1$ at position $i$ depending on whether $a_i$ and $a_{i+2}$ are the same or different.
6. Use problem 5 to prove the following statement: if an arrangement with an even number of bits is transformed twice, then the result is the same if every other bit was treated as an arrangement and transformed once. That is: $a_1a_2a_3a_4a_5a_6a_7a_8$ going to $b_1b_2b_3b_4b_5b_6b_7b_8$ in two transformations is equivalent to $a_1a_3a_5a_7$ and $a_2a_4a_6a_8$ going to $b_1b_3b_5b_7$ and $b_2b_4b_6b_8$ in one transformation each, and similarly for other even-length arrangements.
7. Extend the idea of problems 5 and 6 by proving the following. Let $a_1...a_{2^n}$ be an arrangement of length $2^n$ . Prove that after $2^k$ transformations, the value in position $1$ depends only on whether $a_1$ and $a_{2^k+1}$ were the same or different in the original arrangement for all $k<n$ .
8. Prove that, for any positive integer $k$ , any arrangement of $2^k$ bits becomes all zeros after $2^k$ transformations.
Part III
9. Justify why arrangements that are either all zeros or all ones are the only arrangements that give all zeros after one transformation.
10. Prove that one transformation on any arrangement of bits results in arrangement with an even number of ones.
11. Combine Problems 9 and 10 and prove that if an arrangement has an odd number of bits and is not all zeros and not all ones, then no number of transformations will result in all zeros.
12. Prove that if an arrangement has an even number of bits that is not a power of two, and exactly one bit is $1$ , then no number of transformations will result in an arrangement of all zeros.

[UPDATE] Somehow the post got clipped.. I’ve replaced the old material as close to my original wording as I remember

About these ads

May 23, 2007 - Posted by John Armstrong | Uncategorized

2 Comments »

There’s a typo in number 5. The last sentence should read “… depending on whether a_i and a_{i+2} are the same or different.”

Fun little problem. Now, of course, I feel the urge to work out how it generalizes–perhaps replacing {0,1} with an arbitrary (finite/abelian) group? In a crazier vein, I wonder what happens in higher dimensions–on the surface of a torus or a sphere, say?

Comment by Cat lover | May 23, 2007 | Reply
[...] to the ARML Scrimmage Power Question Today I’ll give my own solution to the power question I posted last week. I’m going to present it as I always wished I could have: as a whole with answers to the [...]

Pingback by Solution to the ARML Scrimmage Power Question « The Unapologetic Mathematician | May 31, 2007 | Reply

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects
Archives

May 2007

M T W T F S S

« Apr Jun »

1 2 3 4 5 6

7 8 9 10 11 12 13

14 15 16 17 18 19 20

21 22 23 24 25 26 27

28 29 30 31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider