P2.1 Colorful April
a
We model this problem as a graph . Each activity is a vertex, and two vertices have an edge if and only if there is a student who requested both activities. The problem now becomes if it is possible to color this graph with at most 30 colors (such that no edge has same color on both ends). If there is a such coloring strategy, it would mean that we can assign each activity to a corresponding evening in April, such that: if any two activities are requested by the same student, then they must be on two separate evenings, which satisfies the problem.
b
We choose an arbitrary pair of color wlog. we assume Since the greedy algorithm uses color , there is a first vertex that receives color . When is colored, greedy chooses the smallest available color, so color must all be unavailable for , which means for each color there is at least one neighbor of using that color. In particular, those colors includes . Suppose this neighbor with color is , then is an edge that has both as end-points color. Therefore, for every pair of color, there is an edge whose end-points have those colors.
c
In a graph with chromatic number there exists a coloring strategy with colors, and there exists a greedy coloring algorithm (with specific ordering) that produces this strategy. Using result from b) we know that every unordered pair of color in exists in this coloring strategy. Since each edge can only have one pair of colors, there are at least edges.
d
Since each student can pick at most two activities, each student can produce at most one edge in the graph. Therefore, graph has at most 450 edges. Suppose no strategy can be found, than it would mean has a chromatic number larger than . According to c) must have at least edges. However, has at most 450 edges, which leads to a contradiction. Therefore, has a chromatic number at most , and a suitable assignment strategy in April must exist.