20 people where each person bears a grudge against exactly one other person in the group

Answer:

Yes, it is always possible.

Also,

the size of the group is irrelevant (as long as it is finite).

Reasoning:

This is in essence a question of finding a vertex colouring in a directed graph.

As every vertex has a successor, there must be a cycle.

As every vertex has only one successor this cycle is unique for every vertex. In particular, there is exactly one cycle for each connected component. This connected component consists of the cycle and all vertices that "branch onto" the cycle.

If we break up the cycle by removing one edge, we are left with a tree. A tree can be coloured with two colours. If we reinsert the edge to repair the cycle we may create a single clash which can be corrected by using a third colour on one of the reconnected vertices.

We can therefore colour each connected component with three colours. As there is no "cross-talk" between these components we can use the same three colours for all of them.

Here’s an algorithmic way to do this.

We can associate a directed graph by assigning a vertex to each person and placing a directed edge from i to j if i has a grudge against j. So each vertex has exactly one outgoing edge.

First,

pick a vertex and follow its child vertex. Since every vertex has an outgoing edge, we can always find a child vertex, and since there are finitely many vertices, we must revisit a vertex. In other words, there’s a cycle in every connected component.

Next,

pick a connected component and pick a vertex v0 in a cycle in that component. Call it level 0. Place any parent vertex of v0 in level 1. And so on. This way, there is no edge within a level. In particular, a vertex at level k has an outgoing edge to some vertex at level k-1, except for v0, which has an outgoing edge to exactly one vertex in some level l>0. If l is odd, we can colour the vertices with two colours, alternating every level. Else, use two colours up to level l-1, then use a third colour at level l, and then continue using the first two colours from level l+1 and above.

Repeat the above algorithm for all connected components.

Added: Here’s an example diagram depicting the result of above algorithm when l=2. The cycle in this connected component is shown in red.

It is

always possible. Consider a group of any number of people, and add them sequentially to 3 groups. You're the next person to be added to a group, and there are a few options:

1) If no one holds a grudge against you, you can go into any group that doesn't contain your grudge. 2) If one person holds a grudge against you, three groups may be required if the person you begrudge begrudges the person who begrudges you. 3) If many people begrudge you, they can all go in the same group together, separate from you, and also in a separate group from the people who begrudge them (who don't begrudge each other). This also requires three groups. At no point are more than three groups required to handle any case.