左から順に仕切りを入れるか入れないかを順に決めて行きます。このとき、「必要に迫られない限り、仕切りを入れることを先延ばしにする」という戦略を取ることで、仕切りの個数を \(N\) 個以下にすることができます。

具体的には、左から宝石を順に見て行き、以下のように仕切りを入れて行けば良いです。

• その宝石がこれまで見たことのない種類だった場合、何もしない。
• そうでなかった場合、区間の番号の偶奇が前に見た同じ種類の宝石と同じになってしまうのであれば、その左側に仕切りを入れる。

後者の場合になるのは \(N\) 回であるため、仕切りの個数は \(N\) 以下になります。