Wednesday, December 8, 2010

Symbol Migration

I looked also at Symbol Migration.
This also seems deceptively easy to figure out. Since it takes three moves for the symbols to swap as shown in the problem outline, the number of moves needed for a field filled with n rows of '> <' should just be 3n.

Actually, I did read the problem wrong, so no wonder this seems so surprisingly easy.
n = 0 requires 0 moves, as there is nothing to move
n = 1 requires 3 moves
n = 2 requires 8 moves
>> <<
> ><<
> <><
> <<>
>< <>
<> <>
< ><>
< <>>
<< >>
n = 3 requires 15 moves
>>> <<<
>> ><<<
>> <><<
>> <<><
>> <<<>
>>< <<>
><> <<>
<>> <<>
<>>< <>
<><> <>
<<>> <>
<<> ><>
<<> <>>
<< ><>>
<< <>>>
<<< >>>
so where M(n) is the number of moves for n symbols on each side, as n increases by 1, M(n) seems to be increasing at an increasing rate: 3, 5, 7. So M(4) should be 24.
With this theory, M(n) = M(n-1) + 2(n+1) - 1 for n >= 1.

No comments:

Post a Comment