Check circular coloring

Logical thinking · Suggested grades 4

Check circular coloring

Download video
Open Chinese transcript
  1. 四个座位围成一圈,颜色依次是红、蓝、红、蓝。环形中首尾也相邻。
  2. 先查1号和2号,是红与蓝,不同色。
  3. 再查2号和3号,是蓝与红;3号和4号是红与蓝,也都不同。
  4. 最后不能漏掉4号与1号。它们是蓝与红,仍然不同。
  5. 四条相邻边:一号和二号、二号和三号、三号和四号、四号和一号,全部通过。
  6. 因此这组颜色安排可行。检查环形约束时,必须补上最后一个与第一个的边。线性序列只查三条边,环形还必须多查首尾这一条边。
Sources for this explanation

Logical thinking

Check every cycle edge, including the last-to-first edge.

Worked example

Four circular seats are red, blue, red, blue. Adjacent seats, including 4 and 1, must differ. Is it valid?

All four edges 1–2, 2–3, 3–4 and 4–1 connect different colors.

Try one question

Three circular seats are red, blue, red. Adjacent colors must differ. Valid?