Problem 1619

Let's reformulate the problem in terms of graph theory. We can represent the workers as vertices of a graph, and an edge between two vertices indicates that the corresponding workers are enemies. The problem then becomes one of partitioning the vertices of this graph into cliques (complete subgraphs) such that no two enemies are in the same clique.

Given that the workers arrive in 100 buses, we can assume that each bus represents a clique (since no enemies are in the same bus). Therefore, we have 100 disjoint cliques. We need to prove that either we cannot partition the vertices into cliques of size at least 2, or if we can, we can do it in at most 100 cliques.

1. Initial Setup:
- Let $v_1, v_2, \ldots, v_t$ be the singletons (vertices that are not part of any clique of size at least 2).
- Let $(x_1, y_1), (x_2, y_2), \ldots, (x_l, y_l)$ be the cliques of size 2.
- Let $C_1, C_2, \ldots, C_m$ be the cliques of size at least 3.

2. Observations:
- Observation 1: $v_i$ and $v_j$ cannot be adjacent (i.e., they are not enemies), otherwise, we could combine them into a clique of size 2, reducing the number of singletons $t$.
- Observation 2: $v_1$ cannot be adjacent to any vertex $u \in C_j$ (where $C_j$ is a clique of size at least 3), otherwise, we could combine $v_1$ and $u$ into the same clique, reducing $t$.
- Observation 3: We cannot have $v_1$ adjacent to $x_1$ and $v_2$ adjacent to $y_1$, otherwise, we could form two groups and reduce $t$ by 2.

3. Inductive Argument:
- Suppose we have the groups as described. Then $v_1, v_2, \ldots, v_t$ are in different groups with (without loss of generality) $x_1, x_2, \ldots, x_t$. Now, $y_1, y_2, \ldots, y_t$ become singletons, which forces the same observations 1, 2, and 3 to hold for $y_1, y_2, \ldots, y_t$.
- One more observation is that $y_i$ cannot be in the first $t$ groups, otherwise, we would reduce $t$.

4. Contradiction:
- This process should create another $t$ groups with $x_{t+1}, x_{t+2}, \ldots, x_{2t}$, implying $l \ge 2t$.
- By the same reasoning, $l \ge nt$ for every $n \in \mathbb{N}$, which is a contradiction since $l$ is finite.

5. Conclusion:
- Therefore, we must be able to reduce $t$ and use induction because the total number of groups does not increase during the process. Hence, we can form at most $k$ groups, or we cannot form any groups at all.

$\blacksquare$