rant - train of thought of inspiration...
i was sitting in the guardstand a little while ago, and somehow my thoughts turned to ARML 2005 - more specifically, the last question of the power round that danny and I spent lots of time on but still couldnt solve. here's the gist of it:
Setup: in some illogically infinite town, there is an infinite number of buildings. Each building's address is represented by an infinite decimal number that only consists of 0's and 1's. For instance, .0000[0] (where [] denotes the repeating digits) is the post office, .101101101[01] is Joe's house, .011011[1] is Jane's house, etc. Every one of the infinite buildings has a unique address, and every possible address is assigned to a building.
Problem: the jerks at the post office decide to allow use of the digit "2" to make some new addresses. Find a way to change each building's address so that each building has a unique address, and every possible new address is assigned to a building.
Summary in math jargon: establish a 1-on-1 correspondence between the set of all infinite-digit strings of 0's or 1's and the set of all infinite-digit strings of 0's, 1's, or 2's
anyway... since it was still early morning and the only people in the pool are able-bodied lap swimmers, i could afford diverting some attention to the problem... when inspiration struck me.
the main problem i had at arml in doing this is that 2 and 3 are relatively prime, so i couldnt just block off digits and convert from base 2 to base 3 like we do from 2 to 8 or 16 in compsci. We haphazardly made a few random attempts, but none worked. it was only a few minutes ago that it occurred to me that i can vary the block size - observe:
block of size one : "0"
block of size two : "11" and "10"
total different blocks : 3!!!! - representable by 0, 1, and 2 in base 3!
example:
.01101010010111010100101010[0110] - original
.0 11 0 10 10 0 10 11 10 10 10 0 10 10 10 [0 11 0] - blocks
.0 2 0 1 1 0 1 2 1 1 1 0 1 1 1 [0 2 0] - new address
.10100110111100101001[011] - original
.10 10 0 11 0 11 11 0 0 10 10 0 10 11 [0 11]
.1 1 0 2 0 2 2 0 0 1 1 0 1 2 [0 2] - new address
backward:
.10211020102 - new
.10 0 11 10 10 0 11 0 10 0 11 - original! (blocks)
IT WORKS!!!!!
so simple... yet we never figured it out in time...
Setup: in some illogically infinite town, there is an infinite number of buildings. Each building's address is represented by an infinite decimal number that only consists of 0's and 1's. For instance, .0000[0] (where [] denotes the repeating digits) is the post office, .101101101[01] is Joe's house, .011011[1] is Jane's house, etc. Every one of the infinite buildings has a unique address, and every possible address is assigned to a building.
Problem: the jerks at the post office decide to allow use of the digit "2" to make some new addresses. Find a way to change each building's address so that each building has a unique address, and every possible new address is assigned to a building.
Summary in math jargon: establish a 1-on-1 correspondence between the set of all infinite-digit strings of 0's or 1's and the set of all infinite-digit strings of 0's, 1's, or 2's
anyway... since it was still early morning and the only people in the pool are able-bodied lap swimmers, i could afford diverting some attention to the problem... when inspiration struck me.
the main problem i had at arml in doing this is that 2 and 3 are relatively prime, so i couldnt just block off digits and convert from base 2 to base 3 like we do from 2 to 8 or 16 in compsci. We haphazardly made a few random attempts, but none worked. it was only a few minutes ago that it occurred to me that i can vary the block size - observe:
block of size one : "0"
block of size two : "11" and "10"
total different blocks : 3!!!! - representable by 0, 1, and 2 in base 3!
example:
.01101010010111010100101010[0110] - original
.0 11 0 10 10 0 10 11 10 10 10 0 10 10 10 [0 11 0] - blocks
.0 2 0 1 1 0 1 2 1 1 1 0 1 1 1 [0 2 0] - new address
.10100110111100101001[011] - original
.10 10 0 11 0 11 11 0 0 10 10 0 10 11 [0 11]
.1 1 0 2 0 2 2 0 0 1 1 0 1 2 [0 2] - new address
backward:
.10211020102 - new
.10 0 11 10 10 0 11 0 10 0 11 - original! (blocks)
IT WORKS!!!!!
so simple... yet we never figured it out in time...