0

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?

nnn
  • 1
  • How about coloring black e.g. the utmost left green card? This in the case where the number of green cards is odd. I think strong induction can indeed help you further then. Two separate cases with less cards arise. – drhab Oct 02 '23 at 20:17
  • @drhab What about if the leftmost card is green? You'll be left with an even number of green cards. – Arthur Oct 02 '23 at 20:22
  • @drhab how would that work I got lost – nnn Oct 03 '23 at 02:44
  • @Arthur Starting with odd number of green cards the number of greens on right side of leftmost green is even before coloring. The card at right next to the lefmost green changes of color (at start there are no black cards) so after coloring the number of greens on right side of leftmost cards is odd. – drhab Oct 03 '23 at 06:44
  • @Arthur GRRGGR, BGRGGR, BBGGGR, BBBRGR, BBBGBG, BBBBBG, BBBBBB – drhab Oct 03 '23 at 06:58
  • This is identical to this coin flipping problem on Puzzling SE, where heads=green, tails=red, removed=black. – Jaap Scherphuis Oct 03 '23 at 09:17

1 Answers1

0

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.

drhab
  • 151,093