Question

There are N cards in a row and they can be face up or face down. A turn consists of taking two adjacent cards where the left one is face up and the right one can be face up or face down and flipping them both. Show that this process terminates

Answer 1

you will have to flip the left most face up card and it migrates to the right most side resulting in everything except the right most card being face down and hence the process terminates


Each move is moving face ups to the right, the process terminates when (or before) all fact up cards are on the right

 Let F(i) be the ith fibonnaci number, F(0)=1, F(1)=1. With some algebra and induction show that a = F(2k) and b = F(2k+2) works