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 ath card and ending with the bth 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