In the question about cards, the binary observation is absolutely correct but gives the impression that you need more “structure” to solve the problem than you really do. I prefer (even though it maybe yields a textually longer proof) to do it this way: sort the possible configurations lexicographically (“dictionary order”, where things further left always take precedence) with up < down; and then note that every operation you do moves your configuration earlier in the order, at which point you’re done.
… Oh, and the problem as stated above isn’t quite right. In the configuration UUUUUUUUUUUUUUUUUUUD there is no legal move according to your statement of the problem, so you don’t terminate with all cards face up. More generally, your procedure always flips two cards at once so the parity of the number of D cards can’t change, so half of all starting configurations are unable to end with all cards up and in fact will end with UUUUUUUUUUUUUUUUUUUD. (To fix this, either just ask for a proof that the procedure always terminates, or else make flipping the card to the right of the one you turn face-up optional.)
half of all starting configurations are unable to end with all cards up and in fact will end with UUUUUUUUUUUUUUUUUUUD.
That is why the starting configuration is explicitly given as: “Twenty random cards are placed in a row all face down”.
If the number of starting face down cards is odd, then it will terminate with the last card as down and the rest as up. If the number of starting face down cards is even, then it will terminate with all the cards face up.
Oops, misread the problem statement. Of course you’re right. (Though I think the problem is made slightly more interesting if you allow starting with an arbitrary configuration.)
In the question about cards, the binary observation is absolutely correct but gives the impression that you need more “structure” to solve the problem than you really do. I prefer (even though it maybe yields a textually longer proof) to do it this way: sort the possible configurations lexicographically (“dictionary order”, where things further left always take precedence) with up < down; and then note that every operation you do moves your configuration earlier in the order, at which point you’re done.
… Oh, and the problem as stated above isn’t quite right. In the configuration UUUUUUUUUUUUUUUUUUUD there is no legal move according to your statement of the problem, so you don’t terminate with all cards face up. More generally, your procedure always flips two cards at once so the parity of the number of D cards can’t change, so half of all starting configurations are unable to end with all cards up and in fact will end with UUUUUUUUUUUUUUUUUUUD. (To fix this, either just ask for a proof that the procedure always terminates, or else make flipping the card to the right of the one you turn face-up optional.)
That is why the starting configuration is explicitly given as: “Twenty random cards are placed in a row all face down”. If the number of starting face down cards is odd, then it will terminate with the last card as down and the rest as up. If the number of starting face down cards is even, then it will terminate with all the cards face up.
Oops, misread the problem statement. Of course you’re right. (Though I think the problem is made slightly more interesting if you allow starting with an arbitrary configuration.)