IL-GROSSMAN 2001 Problem 3

We are given $2001$ lines in the plane, no two of which are parallel and no three of which are concurrent. These lines partition the plane into regions (not necessarily finite) bounded by segments of these lines. These segments are called sides, and the collection of the regions is called a map. Intersection points of the lines are called vertices. Two regions are neighborsif they share a side, and two vertices are neighbors if they lie on the same side. A legal coloring of the regions (resp. vertices) is a coloring in which each region (resp. vertex) receives one color, such that any two neighboring regions (vertices) have different colors. (a) What is the minimum number of colors required for a legal coloring of the regions? (b) What is the minimum number of colors required for a legal coloring of the vertices?