Jack has n amount of cards. At first, all cards are either green or red. However, Jack wants to transform all cards into black. He can only color the green card black. Additionally, when a card turns black, the adjacent card will turn red if they are green, green if they are red, and stay black if they are black. Any card that is colored to black will stay black. For example, “R”, “G”, “G”, “R” If Jack colors the second card from the left, “G”, “B”, “R”, “R” Prove that Jack can make all n card black if and only if the number of cards that are initially green is odd.
I have tried strong induction but I cannot figure out the induction step. can you give me some ideas?
Suppose that at the start the number of green cards is odd. Then there is at least one green card. Let's see what happens if we paint the leftmost green card black and for convenience we abbreviate this card as LGC. If there is only one card then we have succeeded in painting all cards black. If there are more cards then coloring the LGC black leaves us with two sets of cards: those at the left of LGC (turned into black now) and those at the right of LGC. Verify yourself that for both sets it is true that it is empty or contains an odd number of green cards and contains no black cards. Both sets contain less cards than the original set and can be handled separately so by induction we can conclude that all cards can be painted black.
The other side I leave to you.