5
$\begingroup$

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:

  1. $n = 2014$
  2. $n = 2016$
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

strategy:

On every move, flip cards from the first face down card up to the last 'legal' face up card, where legal means you have selected an even number of face up cards. Repeat the process until you have all face up cards on the left side, apart from 1 outlier. Then flip cards from 1 up to the card before the outlier. After this, all face up cards are next to eachother (although face down cards are not next to eachother). This works for any N>=5, although I'm not sure why it wouldn't for 2014 or 2016

$\endgroup$
  • $\begingroup$ This works so long as n is not divisible by 4 since in such cases you have an even number of face up cards, so cannot flip all but the outlier at the last step to bring them together (try it with n=8 or n=12). $\endgroup$ – Jonathan Allan Apr 11 '16 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.