Annie has a very long line of cards, numbered from 1 to $n$, such that every odd card is face-up and every even card is face-down. The only way she can modify the line is by taking any segment of consecutive cards that has an even number of face-up cards and reversing the order of the cards in this segment (note that none of the cards are flipped).
As a neat freak, she wants to get all the face-up cards to be next to each other. Tell her how to achieve this or show that it is impossible if:
- $n = 2014$
- $n = 2016$
Answer
For 2014, first execute the following operations:
$(1, 4)$ $(2, 8)$ $(3, 12)$ $(4, 16)$ ...
($(a, b)$ is reversing the segment starting with the $a$th card and ending with the $b$th one)
Then:
Arrange the blocks of 2 face-up cards together with the lone one and it's done.
For 2016,
I think it's impossible. Notice that the operation is invertible. The final state for 2016 cards is a contiguous block of 1008 face-up cards. However, the operation cannot make a block of odd length if there wasn't one to begin with, because the reversed segment should start and end with face-up blocks of the same parity (because in its middle can only be blocks of even length). And we are supposed to end up with a lot of separate face-up cards.
No comments:
Post a Comment