These questions are about a shuffled deck of finitely-many playing cards. Each card in the deck is either red or black. We don't necessarily assume that there are equally many reds as there are blacks. The physical order of cards inside the shuffled deck is linear.
A "block" is a largest-possible contiguous set of equally-colored cards in the deck. For example, if the red/black cards come up (red, red, black, black, black, red, black, red, red, ...), we have a block of 2 red cards, then a block of 3 black cards, then a block of 1 red card, and so on.
1. You could determine the number of blocks by looking at each card in sequence, comparing it against the previous card. Can you design an algorithm to determine number of blocks such that, at least with high likelyhood, the algorithm need not examine every card?
2. Now we're only interested in whether the number of blocks is even or odd. What's the most efficient algorithm?
Both were solved by Proxima in IRC, but I found it interesting enough to give everyone a try. :-)
-- Simon